C17 : Exercices

Complexité d'un algorithme

C17.E1 : Liste de liste

1) Écrire une fonction qui prend un nombre entier positif n comme paramètre et renvoie une liste de liste de n sur n, contenant uniquement des 0.

2) Déterminer le coût de cet algorithme.

C17.E2 : Amplitude des valeurs d'une liste

Dans cet exercice, toutes les fonctions seront écrites avec une docstring et des doctests.

On appelle amplitude des valeurs d'une liste la différence entre la plus grande et la plus valeur de cette liste.

1) Écrire une fonction min_liste qui prend une liste en paramètre et renvoie la plus petite valeur de cette liste.

2) Écrire une fonction max_liste qui prend une liste en paramètre et renvoie la plus grande valeur de cette liste.

3) En utilisant les deux fonctions précédentes, écrire une fonction amplitude_liste_v1 qui prend une liste en paramètre et renvoie l'amplitude de cette liste.

4) Sans utiliser les fonctions des questions 1 et 2, et en utilisant qu'une seule boucle, écrire une fonction amplitude_liste_v2 qui prend une liste en paramètre et renvoie l'amplitude de cette liste.

5) Laquelle des fonctions amplitude_liste_v1 et amplitude_liste_v2 utilise le moins le processeur ? Justifier.

Correction d'un algorithme

C17.E11 : Somme des n premiers entiers

1) Écrire une fonction qui prend un nombre entier positif comme paramètre et renvoie la somme des nombres entier de 1 jusqu'à ce nombre (on utilisera une boucle while).

2) Faire la preuve de l'algorithme utilisé en trouvant :

• - un variant convergeant de boucle,
• - un invariant de boucle.

C17.E12 : Plus grande valeur d'une liste

1) Écrire une fonction qui prend une liste en paramètre et renvoie la valeur maximale de la liste.

2) Faire la preuve de l'algorithme utilisé en trouvant :

• - un variant convergeant de boucle,
• - un invariant de boucle.

C17.E13 : Multiplication avec des additions

1) Écrire une fonction qui prend deux nombres entiers positifs a et b comme paramètres et renvoie le produit a×b. La fonction ne devra pas utiliser l'opérateur *.

2) Faire la preuve de l'algorithme utilisé en trouvant :

• - un variant convergeant de boucle,
• - un invariant de boucle.

3) Améliorer la fonction pour que les paramètres a et b puissent être positifs ou négatifs.