Exercices corrigés Python (complexité)
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é
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é.
La suite de Fibonacci est définie comme suit :
1. Ecrire un programme récursif calculant Fib(n)
2. Déterminer sa complexité
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é.
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.
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é.
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.
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.
Partager ce cours avec tes amis :
