Langage Python

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

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 M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :