Langage Python

Exercices corrigés Python (complexité)

Exercice 1:

Un tableau X est trié par ordre croissant si x(i) <= x(i+1)pour tout i

1.     Elaborer un programme récursif permettant de vérifier qu’un tableau X est trié ou non

2.     Estimer sa complexité

Exercice 2:

Pour convertir unnombre entier positif N de la base décimale à la base binaire, il faut opérer par des divisions successives du nombre N par 2. Les restes des divisions constituent la représentation binaire.

1.     Ecrire une fonction récursive « Binaire » permettant d’imprimer à l’écran la représentation binaire d’un nombre N;

2.     Donner la formule récurrente exprimant sa complexité en nombre de divisions. Estimer cettecomplexité.

Exercice 3:

La suite de Fibonacci est définie comme suit :

 1.    Ecrire un programme récursif calculant Fib(n)

2.    Déterminer sa complexité

Exercice 4:

Soit la suite définie par :

1.     Ecrire un programme récursif permettant de calculer le nième terme de la suite.

2.     Estimer sa complexité.

Exercice 5:

Un nombre N est pair si (N-1) est impair, et un nombre N est impairsi (N-1) est pair.

1.     Ecriredeux fonctions récursives mutuelles pair (N) et impair (N) permettant de savoir si un nombre N est pair et si un nombre N est impair.

2.     Estimer la complexité de la fonction Pair (N) en nombre d’appels récursifs. 


Exercice 6:

Etant donné un tableau X composé de N éléments entiers. On voudrait déterminer son maximum par un programme récursif basé sur le paradigme« diviser pour régner » :

1.     En considérant que le maximum est le plus grand entre le dernier terme et le maximum des (n-1) premiers termes. Estimer sa complexité.

2.     En considérant que le maximum est le plus grand entre les maximums des deux moitiés du tableau. Estimer sa complexité.

Exercice 7:

Soit un tableau X composé de N entiers pouvant être 0 ou 1. Une coupe (i,j) de X est le sous tableau commençant à i et finissant à j. on voudrait déterminer la plus longue coupe ne contenant que des 1.

Exemple : dans le tableau suivant, la coupe (7,14) est équilibrée.

1.     Ecrire une fonction « PlusLongueCoupe » récursive basée sur le paradigme « diviser pour régner » qui détermine la plus longue coupe ne contenant que des 1 d’un tableau X.

2.     Estimer sa complexité moyenne en nombre de comparaisons des éléments du tableau.

Exercice 8:

On voudrait écrire une fonction « multiplier » permettant de multiplier deux entiers positifs ou nuls a et b (ce n’est pas la peine de vérifier la validité des données) en utilisant uniquement des opérations d’addition. Le prototype de la fonction doit être « def multiplier (a, b) ».

1.     Proposer une version récursive de la fonction « multiplier ». Estimer sa complexité ennombre d’additions après avoir déterminé une formule récurrente de lacomplexité.

2.     Proposer une autre version récursive de la fonction « multiplier » basée sur le paradigme «diviser pour régner». Donner une formule récurrente de sa complexité en nombre d’additions et estimer la.

Télécharger le corrigé

Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Professeur d'Informatique dans les CPGE

Cours Similaires :