Terminaison d’un algorithme
Boucle finie/infinie
Tester le programme suivant dans les deux cas n = 12
et n = 10
:
n = int(input("n : ")) q = 0 while n != 0: n -= 3 q += 1 print(q)
À quelle condition la boucle s’arrête-elle ?
En présence d’une boucle while ...
qui ne se termine jamais, on parle de divergence, ou boucle infinie.
Il faut donc impérativement vérifier, par un raisonnement plus ou moins simple, que tôt ou tard, la condition derrière l’instruction while
deviendra FAUSSE afin que la boucle se termine.
Une des techniques possibles est celle qui consiste à trouver un variant de boucle.
Variant de boucle
Un variant de boucle est une expression :
- entière
- positive
- qui décroît strictement à chaque itération
Variants usuels
i
pour une boucle du typefor i in range(deb, fin, -1)
n−i
pour une boucle du typefor i in range(n)
j−i
pour deux variablesi
croissante etj
décroissante- . . .
Il n’y a pas de technique « systématique » …
Exercices
Liste sans doublon
Compléter la fonction suivante :
from random import randint def liste_uniques(N, d, f): """ Renvoie une liste de N nombres aléatoires (entiers entre d et f) sans aucun doublons """ l = [] i = 0 while ...... : ...... return l
Que se passe-t-il si on exécute liste_uniques(20, 1, 10)
?
Ajouter au début de la fonction une assertion qui doit permettre d’éviter ce comportement.
Affirmation catégorique de quelque chose qu’il n’est pas possible de vérifier. (Larousse)
En informatique, une assertion est un moyen de s’assurer qu’une condition est respectée avant de commencer (ou continuer) l’exécution d’un algorithme.
L’objectif est d’éviter des erreurs qui ne devraient pas se produire, ou bien des comportement non désirés, en arrêtant prématurément le programme. Si une telle erreur survient, c’est que le programme doit être modifié pour qu’elle n’arrive plus.
En Python, on utilise l’instruction assert
:
exemple : assert x*a >= 0
(cette assertion peut éviter par exemple de provoquer une erreur lors de l’appel de la fonction sqrt()
)
Séparation de liste
separe(lst, v)
qui sépare les éléments de la liste lst
en plaçant les éléments inférieurs à v
au début et les éléments supérieurs à v
à la fin. La liste doit être modifiée en place (la fonction ne retourne rien).