Un programme est une suite d'instructions exécutées dans l'ordre où elles sont écrites. Une instruction composée (if, for, while, def, try) se termine par un deux-points et commande un bloc : les lignes qui suivent, toutes décalées du même nombre d'espaces vers la droite. Ce décalage s'appelle l'indentation, et vaut par convention quatre espaces par niveau. En Python, l'indentation n'est pas une mise en page : c'est elle, et elle seule, qui dit où un bloc commence et où il finit. Deux lignes également indentées appartiennent au même bloc ; la première ligne moins indentée referme le bloc.
temperature = 120
if temperature > 100:
etat = "vapeur"
print(etat)
print("fin")
Ici print(etat) appartient au bloc du if et n'est exécuté que si la condition est vraie, tandis que print("fin"), revenu à la marge, est exécuté dans tous les cas : ce programme affiche vapeur puis fin, et il n'afficherait que fin pour une température de 20. Une indentation incohérente ne donne pas un résultat faux : elle donne une erreur, IndentationError.
Définition
L'instruction conditionnelle if, elif, else
L'instruction conditionnelle exécute un bloc selon la valeur d'une condition, c'est-à-dire d'une expression dont la valeur est True ou False (les booléens et les opérateurs de comparaison sont vus dans le thème Python : types, variables et expressions). Sa forme complète est :
# extrait : forme générale, les conditions et les blocs restant à écrire
if condition_1:
bloc_1
elif condition_2:
bloc_2
else:
bloc_3
Le mot elif abrège « sinon, si » ; il peut être répété autant de fois qu'il y a de cas intermédiaires, ou absent. Le bloc else, facultatif, n'a pas de condition : il recueille tout ce que les conditions précédentes ont laissé passer. Lu en français : « si la condition 1 est vraie, exécuter le bloc 1 ; sinon, si la condition 2 est vraie, exécuter le bloc 2 ; sinon, exécuter le bloc 3 ».
Propriété
Ce que garantit une cascade if, elif, else
Propriété : dans une cascade if / elif / … / else, les conditions sont évaluées dans l'ordre d'écriture, et l'évaluation s'arrête à la première condition vraie : le bloc correspondant est exécuté, et lui seul ; les conditions suivantes ne sont même pas évaluées. Si aucune condition n'est vraie, le bloc else est exécuté s'il existe, et aucun bloc ne l'est sinon. Deux conséquences. D'abord, au plus un des blocs est exécuté, et exactement un lorsqu'un else termine la cascade : la cascade réalise donc une disjonction de cas au sens des mathématiques. Ensuite, comme le premier test vrai l'emporte, l'ordre des tests fait partie du programme : écrire if note >= 12 avant elif note >= 14 rend le second test inatteignable pour une note de 17, qui est déjà supérieure à 12.
Méthode
Traduire une disjonction de cas en cascade de tests
Quand l'utiliser : l'énoncé définit un résultat selon les cas (fonction définie par morceaux, barème, classement, discussion selon le signe d'un discriminant), ou le mot « selon que », « suivant que », « si … sinon » figure dans le texte. 1) Écrire les cas en français, avec leurs conditions exactes, et vérifier deux choses : qu'ils couvrent toutes les entrées autorisées par la spécification, et qu'ils sont deux à deux incompatibles. S'ils se recouvrent, la cascade tranchera par l'ordre. 2) Les ordonner du plus restrictif au plus large. Un cas plus large placé en premier absorbe tous ceux qui le suivent. 3) Écrire le premier cas après if, chacun des suivants après un elif, et le dernier après else. On n'écrit jamais la condition du else : elle est exactement la négation de toutes les précédentes. 4) Traduire chaque condition en respectant les bornes : « au moins », « supérieur ou égal » donnent >= ; « strictement plus grand » donne >. Une borne mal choisie ne se voit que sur la valeur de la borne. 5) Tester le programme sur une valeur par cas et sur chaque borne, puis sur une valeur que la spécification interdit, pour vérifier que l'assertion de précondition la refuse.
Exemple
Rédaction modèle : nombre de racines réelles d'un trinôme
Écrire une fonction qui renvoie le nombre de racines réelles du trinôme ax2+bx+c, les coefficients étant entiers et a non nul. Spécification. Entrées : trois entiers a, b, c, avec a non nul. Sortie : l'entier 0, 1 ou 2, égal au nombre de racines réelles distinctes du trinôme. Les trois cas sont donnés par le signe du discriminant Δ=b2−4ac : deux racines si Δ>0, une racine double si Δ=0, aucune si Δ<0. Ils sont deux à deux incompatibles et couvrent tous les réels, donc la cascade se termine par un else sans condition.
def nombre_de_racines(a, b, c):
"""Renvoie le nombre de racines réelles du trinôme a x^2 + b x + c.
Entrées : a, b, c entiers, avec a non nul.
Sortie : un entier valant 0, 1 ou 2.
"""
assert a != 0, "le coefficient dominant doit être non nul"
discriminant = b * b - 4 * a * c
if discriminant > 0:
return 2
elif discriminant == 0:
return 1
else:
return 0
Jeu de tests, un par cas. nombre_de_racines(1, -3, 2) renvoie 2, car Δ=1>0 ; nombre_de_racines(1, -2, 1) renvoie 1, car Δ=0 ; nombre_de_racines(1, 0, 1) renvoie 0, car Δ=−4<0. Test de la précondition : nombre_de_racines(0, 1, 1) s'interrompt sur AssertionError: le coefficient dominant doit être non nul, ce qui est le comportement voulu, l'expression ax2+bx+c n'étant pas un trinôme du second degré pour a=0. Pourquoi des entiers. Le test discriminant == 0 ne décide le cas de la racine double que si le discriminant est calculé exactement, ce que des coefficients entiers assurent. Sur des flottants, l'égalité se manque : le trinôme 0,1x2+0,7x+1,225, qui vaut 0,1(x+3,5)2 et admet donc la racine double −3,5, a un discriminant calculé égal à -1.1102230246251565e-16, et nombre_de_racines(0.1, 0.7, 1.225) renvoie 0. Comparer deux flottants par l'égalité est le piège de la fin du thème : une spécification à coefficients entiers l'écarte d'un mot. À retenir : une disjonction de cas mathématique se transcrit en une seule cascade, les cas dans l'ordre de l'énoncé, le dernier sous else, et se teste avec une valeur par cas plus les bornes.
Δ=b2−4ac
le discriminant, calculé une fois et rangé dans une variable nommée
Piège
Enchaîner des if indépendants au lieu d'une cascade
Ligne fautive : une suite de tests indépendants, chacun introduit par if, pour distribuer une mention selon une note.
def mention(note):
if note >= 12:
return "assez bien"
if note >= 14:
return "bien"
return "sans mention"
Pour note = 17, la fonction renvoie "assez bien" : le premier test est vrai, return interrompt l'appel, et la ligne if note >= 14 n'est jamais atteinte. L'erreur n'est pas dans les conditions, qui sont exactes, mais dans leur ordre : un cas large a été placé avant un cas plus restrictif. Deux corrections possibles, toutes deux correctes. Ordonner du plus restrictif au plus large et enchaîner par elif :
Ou rendre les conditions deux à deux incompatibles en écrivant les intervalles en entier : if 12 <= note < 14 pour la première, if note >= 14 pour la seconde. Les deux corrections rendent bien les mêmes trois mentions l'une que l'autre, et en particulier "bien" toutes deux pour note = 17, là où la fonction de départ répondait "assez bien" : c'est la condition pour qu'on puisse les dire correctes toutes deux. Réflexe : dès qu'il y a plus de deux cas, écrire elif, et tester le programme sur la plus grande des valeurs, celle qui vérifie toutes les conditions à la fois.
Définition
La boucle for et la fonction range
La boucle for répète un bloc une fois pour chaque valeur d'une suite de valeurs donnée d'avance : le nombre de tours est connu avant d'entrer dans la boucle. La variable de boucle prend successivement chacune de ces valeurs.
for k in range(1, 5):
print(k)
affiche 1, 2, 3, 4. La fonction range fabrique la suite des entiers d'une progression arithmétique : range(b) donne 0,1,…,b−1 ; range(a, b) donne a,a+1,…,b−1 ; range(a, b, p) donne a,a+p,a+2p,…, sans jamais atteindre b. Ses trois arguments sont des entiers : un pas décimal, comme 0,1, échoue sur TypeError: 'float' object cannot be interpreted as an integer. Le parcours d'une liste ou d'une chaîne par for relève du thème Python : listes, tuples, chaînes et dictionnaires.
Propriété
Ce que parcourt range et combien de tours il donne
Propriété : soient a, b, p trois entiers avec p>0. La boucle for k in range(a, b, p) exécute son bloc une fois pour chaque entier de la forme a+jp avec j∈N et a+jp<b, dans l'ordre croissant. La borne a est donc la première valeur prise dès que la boucle fait au moins un tour, la borne b n'est jamais atteinte, et le nombre de tours vaut max(0,⌈pb−a⌉). Pour p<0, l'énoncé est le même à deux changements près : la condition a+jp<b devient a+jp>b, et le parcours se fait dans l'ordre décroissant ; la formule du nombre de tours, elle, ne change pas, et range(10, 0, -3) donne les quatre valeurs 10, 7, 4 et 1. En particulier, range(a, b) donne b−a tours si b≥a, aucun sinon : for k in range(3, 3) et for k in range(5, 2) n'exécutent leur bloc aucune fois, sans produire la moindre erreur. Une boucle qui ne tourne pas est le cas limite qu'un jeu de tests doit contenir : c'est lui qui révèle si le résultat initial de l'accumulateur est le bon.
max(0,⌈pb−a⌉)
nombre de tours d'une boucle de pas strictement positif
a+jp<b,j∈N
les valeurs prises par la variable de boucle, borne de droite exclue
Piège
Oublier que range s'arrête un cran avant la borne
Ligne fautive : for k in range(1, n): pour calculer 1+2+⋯+n. La borne de droite est exclue : la boucle s'arrête à n−1 et le dernier terme manque. Pour n=5, la fonction fautive renvoie 10 au lieu de 15 : l'écart, égal au terme oublié, grandit avec n, et le résultat reste plausible, ce qui rend l'erreur difficile à voir. Version correcte : for k in range(1, n + 1):. Réflexe : après avoir écrit un range, dire à voix haute la première et la dernière valeur parcourues, et les comparer aux bornes de la somme de l'énoncé. Pour parcourir k de a à binclus, on écrit toujours range(a, b + 1).
Définition
L'accumulateur : somme et produit
Un accumulateur est une variable qui conserve, d'un tour de boucle à l'autre, le résultat partiel déjà calculé. Le schéma comporte trois temps : l'initialisation avant la boucle, la mise à jour dans le corps de la boucle, et le renvoi après la boucle. Pour une somme, l'accumulateur est initialisé à 0 ; pour un produit, à 1. Ce ne sont pas deux conventions arbitraires : ce sont les éléments neutres de l'addition et de la multiplication, ceux qui donnent au cas limite d'une boucle sans aucun tour la valeur exacte de la somme vide, nulle, et du produit vide, égal à 1. Initialiser une somme au premier terme est possible, mais oblige à traiter à part le cas où il n'y a pas de terme.
S=k=a∑buk
la somme à calculer, un terme ajouté par tour de boucle
k∈∅∑uk=0,k∈∅∏uk=1
somme vide et produit vide, qui fixent la valeur initiale de l'accumulateur
Méthode
Calculer une somme ou un produit par accumulation
Quand l'utiliser : l'énoncé demande une somme ∑k=abuk, un produit ∏k=abuk, un comptage, un maximum, bref une quantité obtenue en parcourant une plage d'indices connue d'avance. 1) Nommer l'accumulateur d'après ce qu'il contient : total, produit, compteur, jamais x ni s. 2) L'initialiser avant la boucle, à l'élément neutre de l'opération : 0 pour une somme, 1 pour un produit, 0 pour un compteur. Écrire en commentaire, ou dans la spécification, ce que vaut l'accumulateur après le tour d'indice k : c'est la phrase qui deviendra l'invariant de boucle dans le thème Algorithmes élémentaires et preuve de programmes. 3) Écrire l'en-tête de boucle avec les bornes exactes : pour k allant de a à b inclus, for k in range(a, b + 1). 4) Dans le corps, une seule instruction de mise à jour, total = total + terme ou produit = produit * terme, où terme est l'expression de uk en fonction de k. 5) Après la boucle, à la marge du for, renvoyer l'accumulateur. Un return écrit dans le corps de la boucle interromprait le calcul au premier tour. 6) Vérifier sur un cas où la somme est connue : une formule fermée du cours, ou un calcul à la main sur trois termes ; et sur le cas limite d'une plage vide, où la fonction doit renvoyer 0 ou 1.
k=1∑nk2=6n(n+1)(2n+1)
formule fermée qui sert de témoin pour tester la fonction
n!=k=1∏nk
produit des entiers de un à n, le produit vide valant un
Exemple
Rédaction modèle : somme des carrés et factorielle
Écrire deux fonctions : l'une renvoie ∑k=1nk2, l'autre renvoie n!, pour n entier naturel. Spécification de la première. Entrée : n entier naturel. Sortie : l'entier 12+22+⋯+n2, et 0 si n vaut 0. L'accumulateur total contient, après le tour d'indice k, la somme des carrés des entiers de 1 à k ; initialisé à 0, il vaut donc la somme demandée après le dernier tour.
def somme_carres(n):
"""Renvoie la somme des carrés des entiers de 1 à n.
Entrée : n entier naturel.
Sortie : l'entier 1^2 + 2^2 + ... + n^2, et 0 si n vaut 0.
"""
assert n >= 0, "n doit être un entier naturel"
total = 0
for k in range(1, n + 1):
total = total + k * k
return total
Vérification par la formule du cours : pour n=5, 65×6×11=55, et somme_carres(5) renvoie 55. Cas limite : somme_carres(0) renvoie 0, la boucle ne tournant pas, ce qui est la valeur de la somme vide. Spécification de la seconde. Entrée : n entier naturel. Sortie : l'entier 1×2×⋯×n, et 1 si n vaut 0.
def factorielle(n):
"""Renvoie n!.
Entrée : n entier naturel.
Sortie : l'entier 1 * 2 * ... * n, et 1 si n vaut 0.
"""
assert n >= 0, "n doit être un entier naturel"
produit = 1
for k in range(2, n + 1):
produit = produit * k
return produit
La boucle part de 2, car multiplier par 1 ne change rien. factorielle(5) renvoie 120 et factorielle(0) renvoie 1, valeur du produit vide. À retenir : initialiser à l'élément neutre, mettre à jour une fois par tour, renvoyer après la boucle, et vérifier le résultat sur une formule fermée et sur la plage vide.
Définition
La boucle while et sa condition d'arrêt
La boucle while répète un bloc tant qu'une condition reste vraie :
# extrait : forme générale, la condition et le bloc restant à écrire
while condition:
bloc
La condition est évaluée avant chaque tour, le bloc compris. Si elle est vraie, le bloc est exécuté puis la condition est évaluée de nouveau ; si elle est fausse, la boucle s'arrête et l'exécution reprend à la première ligne revenue à la marge. On l'emploie quand le nombre de tours n'est pas connu d'avance : il dépend de ce que le calcul produit. La condition d'arrêt est la négation de la condition écrite après while : while somme <= seuil s'arrête dès que somme > seuil. Rien, dans le langage, ne garantit qu'elle finisse par être réalisée : c'est au programmeur de s'en assurer, et à la preuve de terminaison de l'établir, par un variant de boucle, entier positif strictement décroissant, étudié dans le thème Algorithmes élémentaires et preuve de programmes.
Propriété
Ce que garantit une boucle while
Propriété : si l'exécution d'une boucle while dont le corps ne contient ni break ni return se termine, alors, à l'instant où l'on passe à la ligne suivante, la condition écrite après while est fausse. C'est la seule chose que la sortie de boucle garantisse, et c'est déjà beaucoup : elle donne gratuitement une inégalité sur les variables, dont la conclusion se déduit souvent d'une ligne. Deux remarques qui tombent sous le même énoncé. La condition étant testée avant le premier tour, une boucle while peut ne tourner aucune fois : n = 10 puis while n < 5: laisse n inchangé. Et si le corps ne modifie aucune des variables de la condition, celle-ci garde sa valeur : vraie, elle le reste, et la boucle ne s'arrête jamais. Ce que la propriété ne dit pas, c'est que la boucle termine : cela se démontre à part. Quant à l'hypothèse sur le corps, elle ne se retire pas : après n = 10, une boucle while n > 0: dont le corps se réduit à break se termine aussitôt, et la condition n > 0 est encore vraie à la ligne suivante.
Méthode
Écrire une boucle while : état initial, condition, mise à jour
Quand l'utiliser : le nombre de tours n'est pas connu avant l'exécution. Signal dans l'énoncé : « le plus petit entier tel que », « jusqu'à ce que », « tant que », « atteindre une précision », « répéter jusqu'à stabilisation ». Quand le nombre de tours est connu, c'est une boucle for qu'il faut écrire : les bornes sont alors lisibles sur l'en-tête, et l'oubli de la mise à jour est impossible. 1) Nommer les variables qui décrivent l'état du calcul, et dire en une phrase ce que chacune contient à tout instant. 2) Les initialiser avant la boucle, de sorte que la phrase de l'étape 1 soit déjà vraie avant le premier tour. 3) Écrire la condition de continuation, c'est-à-dire ce qui doit rester vrai pour qu'un tour de plus soit nécessaire. La condition d'arrêt de l'énoncé s'y écrit niée : « s'arrêter dès que la somme dépasse le seuil » donne while somme <= seuil. 4) Dans le corps, faire progresser l'état : toute variable qui figure dans la condition doit pouvoir être modifiée par le corps, sans quoi la boucle est infinie. 5) Après la boucle, écrire ce que l'on sait : la condition est fausse, et l'état vérifie la phrase de l'étape 1. Renvoyer la variable demandée. 6) Vérifier sur un cas où l'on sait compter les tours à la main, et sur un cas où la boucle ne doit pas tourner du tout.
Exemple
Rédaction modèle : premier dépassement d'un seuil
Écrire une fonction qui renvoie le plus petit entier n≥1 tel que 1+21+⋯+n1 dépasse un seuil donné. Spécification. Entrée : seuil flottant positif. Sortie : le plus petit entier n≥1 tel que Hn>s, où s est la valeur du seuil et Hn la somme des inverses des entiers de 1 à n. État du calcul : n est le nombre de termes déjà ajoutés, et somme vaut Hn. Avant le premier tour, aucun terme n'a été ajouté : on pose n = 0 et somme = 0.0, et la phrase est vraie, H0 étant la somme vide. Condition de continuation : tant que la somme n'a pas dépassé le seuil, il faut un terme de plus, donc while somme <= seuil.
def premier_depassement(seuil):
"""Renvoie le plus petit entier n >= 1 tel que 1 + 1/2 + ... + 1/n dépasse seuil.
Entrée : seuil flottant positif.
Sortie : un entier n >= 1.
"""
assert seuil >= 0, "le seuil doit être positif"
somme = 0.0
n = 0
while somme <= seuil:
n = n + 1
somme = somme + 1 / n
return n
À la sortie, la condition est fausse : somme > seuil, c'est-à-dire Hn>s. Et comme la boucle n'a pas pu s'arrêter au tour précédent, Hn−1≤s : l'entier renvoyé est bien le plus petit qui convienne. Vérification à la main pour un seuil de 2 : H1=1, H2=1,5, H3≈1,8333, H4≈2,0833. Le premier dépassement a lieu au rang 4, et premier_depassement(2) renvoie 4. Autres appels vus : premier_depassement(1) renvoie 2 et premier_depassement(0) renvoie 1, la boucle tournant alors une seule fois. À retenir : une boucle while s'écrit en trois temps, initialisation avant, condition de continuation, mise à jour dans le corps ; et ce que l'on sait après la boucle, c'est que sa condition est fausse.
Hn=k=1∑nk1
la somme partielle que l'accumulateur contient après n tours
Hn−1≤s<Hn
ce que l'on sait du rang renvoyé, au seuil s, en sortie de boucle
Piège
Une boucle while dont la condition ne peut pas devenir fausse
Lignes fautives : une boucle dont le corps ne touche à aucune des variables de la condition.
# extrait : programme fautif, il ne s'arrête jamais
n = 10
while n > 0:
print(n)
La variable n n'est jamais modifiée : la condition n > 0, vraie au premier test, le reste indéfiniment, et le programme n'affiche jamais rien d'autre que des 10. Il ne produit pas une erreur : il ne s'arrête pas, ce qui, en devoir sur machine, coûte l'exercice entier. La même faute se rencontre avec une mise à jour qui va dans le mauvais sens, n = n + 1 au lieu de n = n - 1. Version correcte : n = n - 1 dans le corps, après l'affichage. Réflexe : après avoir écrit un while, relire la condition, souligner chaque variable qui y figure, et vérifier que le corps en modifie au moins une dans le sens qui rend la condition fausse. La quantité qui décroît strictement à chaque tour est le variant de la boucle : elle se cherche à l'écriture, pas à la relecture.
Méthode
Calculer les termes d'une suite récurrente
Quand l'utiliser : l'énoncé donne une suite par son premier terme et une relation un+1=f(un), ou par deux premiers termes et une relation un+2=g(un+1,un), et demande un terme de rang donné, ou le premier terme qui vérifie une condition. 1) Repérer l'ordre de la récurrence : une variable suffit pour l'ordre 1, il en faut deux pour l'ordre 2. La variable ne porte pas d'indice : elle contient le terme courant, et non toute la suite. 2) L'initialiser avec le ou les premiers termes de l'énoncé, exactement comme ils sont donnés. 3) Écrire une boucle for de n tours quand le rang est donné, une boucle while quand c'est une condition qui arrête le calcul. 4) Traduire la relation en une affectation : u = f(u) pour l'ordre 1. Pour l'ordre 2, les deux nouvelles valeurs se calculent à partir des deux anciennes, donc soit on les écrit d'un coup par une affectation simultanée u, v = v, g(v, u), soit on garde l'ancienne valeur dans une variable temporaire. Le membre de droite est évalué en entier avant toute affectation : c'est ce qui rend l'écriture simultanée correcte (l'affectation multiple est détaillée dans le thème Python : listes, tuples, chaînes et dictionnaires). 5) Après la boucle, renvoyer la variable qui contient le terme demandé, et dire lequel c'est : après n tours partis de u0, la variable contient un. 6) Vérifier sur les premiers rangs, calculés à la main, et si possible sur une forme close connue.
u0=a,un+1=f(un)
récurrence d'ordre un : une seule variable, mise à jour une fois par tour
un+2=g(un+1,un)
récurrence d'ordre deux : deux variables, mises à jour ensemble
Exemple
Rédaction modèle : méthode de Héron
Soit a>0. On pose u0=a et, pour tout k∈N, uk+1=21(uk+uka). Écrire une fonction qui renvoie un. Spécification. Entrées : a flottant strictement positif, n entier naturel. Sortie : le flottant un. La récurrence est d'ordre 1 : une seule variable, u, qui contient le terme courant. Elle est initialisée à a, c'est-à-dire à u0. Chaque tour de boucle remplace uk par uk+1, donc après n tours la variable contient un. Le rang étant donné, la boucle est un for de n tours, dont la variable ne sert pas : on la note _.
def heron(a, n):
"""Renvoie le terme u_n de la suite u_0 = a, u_(k+1) = (u_k + a / u_k) / 2.
Entrées : a flottant strictement positif, n entier naturel.
Sortie : le flottant u_n.
"""
assert a > 0, "a doit être strictement positif"
assert n >= 0, "n doit être un entier naturel"
u = a
for _ in range(n):
u = (u + a / u) / 2
return u
La précondition a>0 n'est pas décorative : elle interdit la division par zéro, et assure que tous les termes restent strictement positifs. Vérification pour a=2, passé en flottant comme la spécification le demande : au rang n=0 la boucle ne tourne pas et la fonction renvoie son argument tel quel, si bien qu'un 2 entier donnerait ici un entier, contre le type annoncé en sortie. Les appels heron(2.0, 0) à heron(2.0, 4) renvoient successivement 2.0, 1.5, 1.4166666666666665, 1.4142156862745097 et 1.4142135623746899, à comparer à math.sqrt(2), qui vaut 1.4142135623730951 : le quatrième terme donne déjà dix décimales exactes. À retenir : pour une récurrence d'ordre 1 et un rang donné, une variable, une boucle for de n tours, une affectation par tour, et le terme demandé est dans la variable à la sortie.
uk+1=21(uk+uka)
la relation de récurrence, transcrite en une affectation
Exemple
Rédaction modèle : suite récurrente d'ordre deux
Soit la suite définie par u0=1, u1=2 et, pour tout k∈N, uk+2=3uk+1−2uk. Écrire une fonction qui renvoie un. Spécification. Entrée : n entier naturel. Sortie : l'entier un. La récurrence est d'ordre 2 : il faut garder deux termes consécutifs. On tient donc deux variables u et v, avec la phrase suivante, vraie à chaque passage en tête de boucle : après j tours, u contient uj et v contient uj+1. Avant le premier tour, u vaut 1 et v vaut 2, c'est-à-dire u0 et u1 : la phrase est vraie.
def terme_ordre_deux(n):
"""Renvoie u_n pour u_0 = 1, u_1 = 2 et u_(k+2) = 3 u_(k+1) - 2 u_k.
Entrée : n entier naturel.
Sortie : l'entier u_n.
"""
assert n >= 0, "n doit être un entier naturel"
u, v = 1, 2
for _ in range(n):
u, v = v, 3 * v - 2 * u
return u
L'affectation u, v = v, 3 * v - 2 * u évalue d'abord les deux expressions de droite, avec les anciennes valeurs, puis affecte : u reçoit uj+1 et v reçoit 3uj+1−2uj=uj+2, donc la phrase reste vraie d'un tour au suivant. Après n tours, u contient un. Vérification. Les appels pour n de 0 à 5 renvoient 1, 2, 4, 8, 16, 32, et terme_ordre_deux(10) renvoie 1024. C'est cohérent avec la forme close : la suite de terme général 2n vérifie les mêmes premiers termes et la même relation, car 3×2k+1−2×2k=(6−2)×2k=2k+2, donc un=2n pour tout n, par une récurrence à deux termes (bloc Fondamental). À retenir : à l'ordre 2, on tient deux variables et on les met à jour ensemble, en disant quelle variable contient quel terme.
uk+2=3uk+1−2uk,u0=1,u1=2
la suite de l'énoncé, dont le terme général vaut deux puissance n
Piège
Écraser un terme avant de s'en servir
Lignes fautives : mettre à jour les deux variables d'une récurrence d'ordre 2l'une après l'autre.
# extrait : mise à jour fautive, hors de sa boucle
u = v
v = 3 * v - 2 * u
À la seconde ligne, u ne contient plus uj : il vient d'être écrasé par uj+1. Le calcul effectué est donc 3uj+1−2uj+1=uj+1, et la suite calculée stagne. Sur la suite u0=1, u1=2, uk+2=3uk+1−2uk, la fonction fautive renvoie, pour n de 0 à 5, les valeurs 1, 2, 2, 2, 2, 2, au lieu de 1, 2, 4, 8, 16, 32. Deux versions correctes. L'affectation simultanée, u, v = v, 3 * v - 2 * u, dont le membre de droite est évalué en entier avec les anciennes valeurs. Ou une variable temporaire, qui rend la manoeuvre visible :
# extrait : mise à jour correcte, hors de sa boucle
ancien_u = u
u = v
v = 3 * v - 2 * ancien_u
Réflexe : dès qu'une mise à jour utilise deux anciennes valeurs, se demander laquelle a déjà été écrasée, et vérifier sur les rangs 2 et 3, calculés à la main.
Définition
Les instructions break et continue
L'instruction break, écrite dans le corps d'une boucle, interrompt cette boucle immédiatement : les tours restants n'ont pas lieu et l'exécution reprend après la boucle. L'instruction continue abandonne seulement le tour courant et passe au tour suivant, la condition du while ou la valeur suivante du for étant reprise normalement. Toutes deux n'agissent que sur la boucle la plus intérieure qui les contient : dans deux boucles imbriquées, un break du bloc intérieur ne quitte pas la boucle extérieure, qui poursuit ses tours.
somme = 0
for k in range(1, 21):
if k % 3 != 0:
continue
somme = somme + k
Ce programme ajoute les multiples de 3 inférieurs à 21 et laisse somme égale à 63. Un break dans une boucle while affaiblit ce que l'on sait à la sortie : la condition du while n'y est plus nécessairement fausse.
Méthode
S'arrêter dès qu'on a trouvé
Quand l'utiliser : l'énoncé demande le premier élément qui vérifie une condition, ou seulement si un tel élément existe. Continuer la boucle après l'avoir trouvé est inutile, et parfois faux, si la suite du parcours écrase la réponse. 1) Décider ce que la fonction renvoie quand rien ne convient : c'est la moitié de la spécification, et l'oublier laisse la fonction renvoyer None sans que personne l'ait voulu. Les choix usuels sont -1 pour un indice, None pour un objet, False pour une réponse par oui ou non. 2) Dans une fonction, préférer return à break : return quitte la boucle et l'appel, en une ligne, sans variable supplémentaire, et l'on ne peut pas oublier d'arrêter le parcours. 3) Hors d'une fonction, ou quand un calcul doit suivre la boucle, écrire break après avoir rangé la réponse dans une variable initialisée à la valeur du cas « rien ne convient ». 4) Écrire la valeur du cas « rien ne convient » après la boucle, à la marge du for : on n'y arrive que si aucun tour n'a déclenché le return. 5) Tester les trois situations : la réponse au premier tour, la réponse au dernier tour, et aucune réponse.
Exemple
Rédaction modèle : premier rang où une somme dépasse un seuil
Écrire une fonction qui renvoie le plus petit entier k compris entre 1 et nmax tel que 1+2+⋯+k dépasse un seuil, et −1 si aucun ne convient. Spécification. Entrées : seuil nombre, n_max entier naturel. Sortie : le plus petit entier k∈{1,…,nmax} tel que 2k(k+1)>s, où s est la valeur du seuil, et −1 s'il n'en existe pas. Le nombre de tours est borné par n_max : on écrit donc une boucle for, et l'on sort dès que la condition est remplie. Comme le calcul se fait dans une fonction, return est préférable à break.
def premier_depassement_somme(seuil, n_max):
"""Renvoie le plus petit k de 1 à n_max tel que 1 + 2 + ... + k dépasse seuil.
Entrées : seuil nombre, n_max entier naturel.
Sortie : cet entier k, ou -1 si aucun k de 1 à n_max ne convient.
"""
assert n_max >= 0, "n_max doit être un entier naturel"
total = 0
for k in range(1, n_max + 1):
total = total + k
if total > seuil:
return k
return -1
Le dernier return est à la marge du for : on ne l'atteint qu'après avoir épuisé tous les tours sans jamais dépasser le seuil. Vérification. Les sommes valent 1, 3, 6, 10, 15 : le premier dépassement de 10 a lieu pour k=5, et premier_depassement_somme(10, 100) renvoie 5. Avec n_max égal à 3, la boucle s'achève sans dépassement et l'appel renvoie -1. Enfin, premier_depassement_somme(0, 5) renvoie 1 : la réponse est au premier tour. Variante sans return, utile hors d'une fonction : initialiser reponse = -1, remplacer return k par reponse = k suivi de break, et lire reponse après la boucle. Les deux versions renvoient les mêmes valeurs sur les trois tests. À retenir : décider d'abord ce que l'on renvoie quand rien ne convient, l'écrire après la boucle, et sortir par return dès que la réponse est trouvée.
Piège
Confondre l'indice et la valeur dans une boucle for
Ligne fautive : for i in notes: suivi, dans le corps, de notes[i]. La variable de boucle d'un for prend les valeurs de ce qui est parcouru, pas leurs rangs. Pour notes = [12, 8, 15], la variable i vaut successivement 12, 8 puis 15, et notes[i] tente d'atteindre le rang 12 d'une liste qui en compte trois : IndexError: list index out of range. Le nom i, hérité des indices mathématiques, est la moitié de l'erreur ; il faut le nommer note. Versions correctes, selon ce dont on a besoin. Pour les valeurs seules : for note in notes:, et l'on utilise note. Pour les rangs : for i in range(len(notes)):, et l'on utilise notes[i]. Une troisième forme, enumerate, donne les deux ; elle relève du thème Python : listes, tuples, chaînes et dictionnaires. Même famille, et aussi trompeur : réaffecter la variable de boucle dans le corps. for k in range(3): suivi de k = 10 exécute quand même trois tours, car le nombre de tours est fixé par le range ; seule la valeur de k à la sortie est changée, et vaut 10 au lieu de 2. La variable de boucle survit d'ailleurs à la boucle : après for k in range(3): pass, k vaut 2.
Définition
Fonction : définition, paramètres et appel
Une fonction est un morceau de programme nommé, qui reçoit des données et renvoie un résultat. Sa définition commence par def, suivi du nom, de la liste des paramètres entre parenthèses et d'un deux-points ; son corps est le bloc indenté qui suit.
import math
def aire_du_disque(rayon):
return math.pi * rayon ** 2
La définition n'exécute rien : elle range la fonction sous son nom. C'est l'appel, aire_du_disque(3), qui exécute le corps après avoir donné aux paramètres les valeurs écrites entre parenthèses, les arguments. Les paramètres sont les noms de la ligne def ; les arguments sont les valeurs de l'appel : la distinction est constamment exigée à l'oral. Écrire aire_du_disque sans parenthèses n'appelle rien et désigne l'objet fonction lui-même : print(aire_du_disque) affiche une ligne du genre <function aire_du_disque at 0x0000020A82F39080>, où le nombre est une adresse en mémoire qui change d'une exécution à l'autre.
Propriété
Ce que fait return
Propriété : l'instruction return expressiontermine immédiatement l'appel en cours, où qu'elle se trouve dans le corps, y compris au milieu d'une boucle, et remplace l'appel par la valeur de l'expression dans le calcul qui l'a demandé. Aucune ligne du corps située après le return exécuté n'est évaluée. Si l'exécution atteint la fin du corps sans rencontrer de return, ou si l'on écrit return seul, l'appel renvoie la valeur spéciale None. Une fonction renvoie donc toujours quelque chose : valeur = afficher(4) range None dans valeur, ce qui ne provoque aucune erreur sur le moment, mais en provoquera une à la première opération faite sur valeur. C'est la raison pour laquelle une spécification dit ce que la fonction renvoie dans tous les cas, y compris ceux où rien ne convient.
Définition
Spécification d'une fonction et docstring
La spécification d'une fonction est le contrat qu'elle remplit : ce qu'elle exige de l'appelant et ce qu'elle lui garantit en retour. Elle comporte trois parties. Les entrées : le nom, le type et le sens de chaque paramètre. Les préconditions : ce que les entrées doivent vérifier pour que l'appel ait un sens (a non nul, liste non vide, entier positif). La postcondition, ou sortie : le type et la valeur de ce qui est renvoyé, exprimé en fonction des entrées, dans tous les cas admis par les préconditions. En Python, on l'écrit dans une docstring : une chaîne entre triples guillemets, placée juste après la ligne def, avant toute instruction. Elle n'est pas un commentaire mais une donnée attachée à la fonction, que help(nom_de_la_fonction) affiche. Une spécification décrit ce que la fonction fait, jamais comment elle le fait : elle ne change pas quand on remplace l'algorithme par un autre.
Méthode
Écrire la spécification d'une fonction avant de la programmer
Quand l'utiliser : toujours, avant la première ligne de code, et en particulier dès que l'énoncé dit « écrire une fonction qui… ». La spécification écrite d'abord fixe le nom, le nombre d'arguments et la valeur renvoyée, c'est-à-dire tout ce sur quoi les autres questions du sujet s'appuieront. 1) Nommer la fonction par ce qu'elle renvoie, pas par ce qu'elle fait de compliqué : nombre_de_racines, moyenne_ponderee, est_premier pour une réponse par oui ou non. 2) Lister les paramètres dans l'ordre où l'énoncé les donne, avec un nom parlant et un type. Une donnée qui ne varie pas d'un appel à l'autre est un paramètre quand même : jamais une variable prise à l'extérieur. 3) Écrire les préconditions, une par contrainte, en relisant l'énoncé : les mots « non nul », « strictement positif », « trié », « de même longueur » y figurent presque toujours. 4) Écrire la postcondition : le type renvoyé et sa valeur en fonction des paramètres. Se demander explicitement ce que vaut le résultat dans les cas limites, entrée vide, rang nul, aucune solution. Si la réponse est « rien », choisir une valeur, -1 ou None, et l'écrire dans la spécification. 5) Recopier tout cela dans la docstring, entre triples guillemets, juste après la ligne def, avant d'écrire le corps. 6) Déduire de la spécification un jeu de tests : un cas usuel, chaque cas limite, et un appel interdit par les préconditions, qui doit échouer.
Exemple
Rédaction modèle : de la spécification au jeu de tests
Écrire une fonction qui calcule la moyenne de deux notes affectées de coefficients. Spécification, écrite avant tout code. Entrées : note_1 et note_2, flottants compris entre 0 et 20 ; coefficient_1 et coefficient_2, flottants positifs. Préconditions : les notes appartiennent à [0,20], les coefficients sont positifs, et leur somme est non nulle, sans quoi la moyenne n'a pas de sens et la division est impossible. Sortie : le flottant c1+c2c1n1+c2n2, qui appartient lui aussi à [0,20] comme moyenne pondérée de deux éléments de cet intervalle.
def moyenne_ponderee(note_1, coefficient_1, note_2, coefficient_2):
"""Renvoie la moyenne pondérée de deux notes.
Entrées : note_1, note_2 flottants de 0 à 20 ; coefficient_1, coefficient_2
flottants positifs de somme non nulle.
Sortie : le flottant (coefficient_1 * note_1 + coefficient_2 * note_2)
divisé par la somme des coefficients ; il est compris entre 0 et 20.
"""
assert 0 <= note_1 <= 20 and 0 <= note_2 <= 20, "les notes vont de 0 à 20"
assert coefficient_1 >= 0 and coefficient_2 >= 0, "les coefficients sont positifs"
assert coefficient_1 + coefficient_2 > 0, "la somme des coefficients doit être non nulle"
return (coefficient_1 * note_1 + coefficient_2 * note_2) / (coefficient_1 + coefficient_2)
Jeu de tests déduit de la spécification. Cas usuel : moyenne_ponderee(12, 1, 18, 3) renvoie 16.5, ce que confirme le calcul à la main 412+54=16,5. Cas limite, deux notes égales : moyenne_ponderee(12, 1, 12, 5) renvoie 12.0, quels que soient les coefficients. Appel interdit : moyenne_ponderee(12, 0, 18, 0) s'interrompt sur AssertionError: la somme des coefficients doit être non nulle, au lieu de produire une division par zéro au milieu du calcul. À retenir : spécification d'abord, préconditions en assert, postcondition vérifiée sur un calcul fait à la main, et un test par cas limite.
Piège
Confondre print et return
Ligne fautive : print(x * x) à la place de return x * x dans le corps d'une fonction.
def carre_affiche(x):
print(x * x)
La fonction print, présentée dans le thème Python : types, variables et expressions, affiche un texte à l'écran, à destination de l'humain ; returnrenvoie une valeur, à destination du calcul qui a fait l'appel. Ici la fonction affiche 9 puis se termine sans return : elle renvoie None. Tant qu'on se contente de l'appeler seule, l'illusion tient, car le 9 apparaît bien. Elle se dissipe au premier calcul : 2 * carre_affiche(3) affiche 9, puis échoue sur TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'. Version correcte : return x * x. L'appelant décide ensuite ce qu'il en fait, l'afficher par print(carre(3)) ou le réutiliser. Réflexe : dans une fonction, on écrit return ; print ne sert qu'à observer un programme en cours d'écriture, ou à produire l'affichage final demandé par l'énoncé. Une copie de concours qui affiche au lieu de renvoyer perd les questions suivantes, qui appellent toutes la fonction.
Piège
Écrire return dans la boucle au lieu d'après
Ligne fautive : un return indenté au niveau du corps de la boucle, alors qu'il devait venir après elle.
def somme(n):
total = 0
for k in range(1, n + 1):
total = total + k
return total
return termine l'appel sur-le-champ : la boucle ne fait qu'un tour et somme(5) renvoie 1 au lieu de 15. Aucune erreur n'est signalée, le résultat est un entier plausible, et le programme est faux pour tout n≥2. Version correcte : ramener le return à la marge du for, c'est-à-dire à l'indentation de total = 0, pour qu'il ne soit atteint qu'une fois la boucle terminée. Réflexe : dans une accumulation, le return est aligné avec l'initialisation de l'accumulateur ; s'il est aligné avec la mise à jour, il est mal placé. Un return dans la boucle n'est légitime que lorsqu'on veut en sortir dès qu'on a trouvé, et la spécification le dit alors.
Définition
Arguments nommés et valeurs par défaut
Un paramètre peut recevoir une valeur par défaut, écrite dans la ligne def : l'appelant peut alors omettre l'argument correspondant.
def puissance(base, exposant=2):
"""Renvoie base élevée à la puissance exposant."""
return base ** exposant
puissance(3) renvoie 9 et puissance(3, 4) renvoie 81. Les paramètres à valeur par défaut se placent après ceux qui n'en ont pas. À l'appel, un argument peut être donné par sa position, dans l'ordre de la ligne def, ou par son nom : puissance(exposant=4, base=3) renvoie 81, l'ordre n'important plus. Les arguments nommés viennent après les arguments positionnels. On les emploie pour rendre un appel lisible quand la fonction a plusieurs paramètres de même type, où une inversion silencieuse est facile.
Propriété
La valeur par défaut est évaluée une seule fois
Propriété : l'expression écrite comme valeur par défaut d'un paramètre est évaluée une seule fois, au moment où la ligne def est exécutée, et non à chaque appel. La valeur obtenue est ensuite attachée à la fonction et réutilisée telle quelle par tous les appels qui omettent cet argument. Un témoin : si l'on définit def valeur_par_defaut(x=n): alors que n vaut 5, puis que l'on donne à n la valeur 100, l'appel valeur_par_defaut() renvoie 5, la valeur que n avait à la définition. Pour un nombre ou une chaîne, la conséquence est bénigne. Elle ne l'est plus si la valeur est modifiable, comme une liste : tous les appels se partagent alors le même objet, et ce que l'un y ajoute, le suivant le retrouve. D'où la règle, sans exception : une valeur par défaut est immuable, un nombre, une chaîne, un booléen ou None.
Piège
Une liste comme valeur par défaut
Ligne fautive : def ajouter_note(note, releve=[]):. La liste vide est construite une fois pour toutes à la définition, et tous les appels qui omettent releve travaillent sur la même liste. Trois appels successifs le montrent : ajouter_note(12) renvoie [12], puis ajouter_note(15) renvoie [12, 15], puis ajouter_note(9) renvoie [12, 15, 9]. La fonction garde mémoire de ses appels précédents, ce que personne n'a demandé, et le bogue ne se manifeste qu'au deuxième appel, souvent loin de là. Version correcte : prendre None comme valeur par défaut et construire la liste dans le corps, à chaque appel.
def ajouter_note(note, releve=None):
if releve is None:
releve = []
releve.append(note)
return releve
Les mêmes appels renvoient alors [12], puis [15]. Le fond de l'affaire est la mutabilité des listes, étudiée dans le thème Python : listes, tuples, chaînes et dictionnaires ; la règle à retenir ici est qu'une valeur par défaut ne doit jamais être un objet modifiable.
Définition
Portée : variables locales et variables globales
La portée d'une variable est la partie du programme où son nom la désigne. Une variable créée dans le corps d'une fonction, paramètre compris, est locale : elle naît à l'appel, meurt au retour, et son nom est invisible depuis l'extérieur. Une variable créée au niveau principal du fichier est globale : les fonctions peuvent la lire, ce qui sert pour une constante, mais pas la modifier par une simple affectation. Deux variables locales de deux fonctions différentes, ou de deux appels de la même fonction, sont sans rapport, même si elles portent le même nom. En particulier, affecter un paramètre ne change rien chez l'appelant :
Après x = 3 puis incremente(x), la variable x vaut toujours 3 ; le résultat est dans la valeur renvoyée, 4. Le cas des objets modifiables, où une fonction peut changer ce que l'appelant lui a passé, relève du thème Python : listes, tuples, chaînes et dictionnaires.
Propriété
Toute variable affectée dans une fonction y est locale
Propriété : si le corps d'une fonction contient, n'importe où, une affectation à un nom, alors ce nom est local à la fonction dans tout le corps, y compris dans les lignes situées avant l'affectation. Une lecture antérieure à la première affectation ne va donc pas chercher la variable globale de même nom : elle échoue.
L'appel s'interrompt sur UnboundLocalError: cannot access local variable 'compteur' where it is not associated with a value : le membre de droite lit un compteur local qui n'a pas encore de valeur. Le mot-clé global lèverait l'interdit, mais rend la fonction dépendante de l'extérieur et illisible : en prépa comme aux concours, on passe la valeur en paramètre et l'on renvoie le résultat.
Méthode
Choisir entre un paramètre, une variable locale et une valeur renvoyée
Quand l'utiliser : au moment d'écrire la ligne def, et chaque fois qu'une fonction a besoin d'une donnée ou produit un résultat. 1) La donnée vient de l'appelant et peut changer d'un appel à l'autre : c'est un paramètre. C'est le cas le plus fréquent, et le bon réflexe par défaut. 2) La donnée est construite et consommée à l'intérieur du corps, accumulateur, compteur, variable de boucle, valeur temporaire : c'est une variable locale, créée par une affectation dans le corps. 3) La donnée est un résultat que l'appelant doit pouvoir utiliser : elle se renvoie par return, jamais par un print, jamais par l'écriture dans une variable globale. Pour renvoyer plusieurs valeurs, on écrit return a, b et l'appelant récupère par a, b = .... 4) La donnée est une constante du problème, la même pour tous les appels, et n'est que lue : une globale nommée en majuscules est acceptable ; un paramètre à valeur par défaut est encore mieux, car la fonction reste testable isolément. 5) Relire la ligne def et la docstring : si un lecteur ne peut pas prévoir le résultat à partir des seuls arguments, une dépendance cachée subsiste, et il faut la remonter en paramètre.
Exemple
Rédaction modèle : remonter une dépendance cachée en paramètre
Le programme suivant calcule le quotient et le reste de la division euclidienne, puis compte le nombre d'appels. Récrire les deux fonctions pour qu'elles ne dépendent de rien d'autre que de leurs arguments. Premier jet, à corriger :
nombre_d_appels = 0
quotient = 0
reste = 0
def division(a, b):
global quotient, reste, nombre_d_appels
nombre_d_appels = nombre_d_appels + 1
quotient = a // b
reste = a % b
Diagnostic. La fonction ne renvoie rien : son appel vaut None, et le résultat n'existe que dans deux variables extérieures, qu'un second appel écrase. Elle ne peut donc pas s'employer dans une expression, ni se tester seule. La précondition b>0 n'est écrite nulle part, alors que a % b n'a pas de sens pour b nul. Correction. Le quotient et le reste sont des résultats : ils se renvoient. Le compteur est une donnée de l'appelant : il se passe en argument et se renvoie mis à jour.
def division_euclidienne(a, b):
"""Renvoie le quotient et le reste de la division euclidienne de a par b.
Entrées : a entier, b entier strictement positif.
Sortie : le couple (q, r) d'entiers tel que a = b * q + r et 0 <= r < b.
"""
assert b > 0, "b doit être strictement positif"
return a // b, a % b
def suivant(compteur):
"""Renvoie le compteur augmenté de un."""
return compteur + 1
L'appelant écrit alors q, r = division_euclidienne(17, 5) puis nombre_d_appels = suivant(nombre_d_appels). Vérification. L'appel donne q = 3 et r = 2, et l'on retrouve bien 5×3+2=17, avec 0≤2<5 : la postcondition est vérifiée. Après un appel de suivant partant de 0, le compteur vaut 1. Les opérateurs // et % employés ici sont ceux du thème Python : types, variables et expressions. À retenir : un résultat se renvoie, au besoin sous forme de couple ; une donnée de l'appelant se passe en paramètre ; et le mot global disparaît avec les deux.
a=bq+r,0≤r<b
la postcondition de la division euclidienne, vérifiée sur le résultat renvoyé
Piège
Utiliser une variable globale au lieu de renvoyer le résultat
Lignes fautives : ranger le résultat dans une variable extérieure au lieu de l'écrire après return.
resultat = 0
def calcul(n):
global resultat
resultat = n * n
Rien n'est renvoyé : l'appel vaut None, et le résultat n'existe que si l'on pense à lire resultat juste après, avant qu'un autre appel ne l'écrase. La fonction n'est plus utilisable dans une expression, ni testable seule, et deux appels enchaînés dans un même calcul se détruisent l'un l'autre. Sans le mot-clé global, la même écriture ne modifie même plus la variable extérieure : elle crée une locale qui disparaît au retour, et le programme est faux en silence. Version correcte : def calcul(n): return n * n, et l'appelant écrit resultat = calcul(n). De même, pour incrémenter un compteur tenu à l'extérieur, on écrit une fonction def suivant(compteur): return compteur + 1 et l'appelant fait compteur = suivant(compteur). Réflexe : une fonction se juge à sa ligne def et à son return ; tout ce qu'elle touche d'autre est une dépendance cachée.
Définition
Une fonction est une valeur que l'on peut passer en argument
En Python, une fonction est une valeur comme une autre : elle a un nom, on peut la ranger dans une variable, la mettre dans une liste, et surtout la passer en argument d'une autre fonction. Le paramètre correspondant s'utilise alors comme une fonction, avec des parenthèses.
def somme_f(f, a, b):
total = 0
for k in range(a, b + 1):
total = total + f(k)
return total
L'argument f est le nom de la fonction, écrit sans parenthèses : somme_f(cube, 1, 4) passe la fonction cube elle-même, tandis que somme_f(cube(1), 1, 4) passerait le nombre 1, et échouerait au premier f(k) sur TypeError: 'int' object is not callable. Une fonction qui en reçoit une autre s'appelle une fonction d'ordre supérieur ; c'est ce mécanisme qui permet d'écrire une fois un calcul et de le réutiliser sur n'importe quelle fonction, comme sorted le fait avec son argument key, vu dans le thème Python : listes, tuples, chaînes et dictionnaires.
Définition
La fonction anonyme lambda
Une fonction anonyme, ou lambda, est une fonction écrite en une expression, sans nom et sans def : lambda parametres: expression. Sa valeur est la fonction qui, aux paramètres, associe l'expression ; il n'y a ni bloc, ni return, ni docstring, et le corps se réduit à une seule expression, sans instruction ni boucle. Elle sert à passer un calcul court en argument, là où écrire une fonction complète alourdirait le programme : somme_f(lambda k: k * k, 1, 5) renvoie 55, la somme des carrés des entiers de 1 à 5. Deux écritures équivalentes, carre = lambda t: t * t et la définition par def carre(t): return t * t, donnent la même fonction, mais la seconde est la seule à recevoir une spécification. D'où l'usage : une lambda ne se nomme pas. Si le calcul mérite un nom, il mérite un def et une docstring.
Méthode
Écrire un calcul générique en recevant une fonction en argument
Quand l'utiliser : le même schéma de calcul doit servir pour plusieurs fonctions, ou l'énoncé demande une fonction « qui prend une fonction en argument » : somme de valeurs f(k), table de valeurs, recherche d'un zéro, comparaison de deux méthodes sur un même exemple. 1) Séparer ce qui ne change pas, le schéma de calcul, de ce qui change, la fonction appliquée. Le second devient un paramètre, placé en premier par convention. 2) Écrire la spécification en disant ce que l'on exige de ce paramètre : de quel ensemble vers quel ensemble, et sous quelles conditions, par exemple « f fonction d'un entier vers un nombre » ou « f continue sur le segment ». 3) Dans le corps, employer le paramètre comme une fonction, f(k), et ne jamais y écrire le nom d'une fonction particulière : c'est l'erreur qui fait passer tous les tests avec la première fonction essayée et échouer avec la seconde. 4) À l'appel, donner le nom de la fonction sans parenthèses. Une fonction de la bibliothèque standard convient aussi bien qu'une fonction écrite à la main. 5) Pour un calcul d'une ligne dont on n'a pas besoin ailleurs, écrire une lambda directement dans l'appel ; sinon, définir la fonction par def. 6) Tester avec deux fonctions différentes au moins : une seule ne prouve rien sur la généricité.
Exemple
Rédaction modèle : somme des valeurs d'une fonction
Écrire une fonction somme_f(f, a, b) qui renvoie ∑k=abf(k), puis l'employer pour calculer ∑k=14k3 et ∑k=15k2. Spécification. Entrées : f, fonction d'un entier vers un nombre, définie au moins pour les entiers de a à b ; a et b entiers. Sortie : le nombre f(a)+f(a+1)+⋯+f(b), et 0 si b<a, la somme étant alors vide. Le schéma est celui de l'accumulation : seul le terme ajouté change, et c'est lui que le paramètre f porte.
def somme_f(f, a, b):
"""Renvoie la somme des f(k) pour k entier de a à b.
Entrées : f fonction d'un entier vers un nombre, a et b entiers.
Sortie : le nombre f(a) + f(a+1) + ... + f(b), et 0 si b est inférieur à a.
"""
total = 0
for k in range(a, b + 1):
total = total + f(k)
return total
Premier emploi, avec une fonction définie à part :
def cube(k):
return k ** 3
somme_f(cube, 1, 4) renvoie 100, ce que confirme la formule (24×5)2=100. Deuxième emploi, avec une fonction anonyme, le calcul ne servant qu'ici : somme_f(lambda k: k * k, 1, 5) renvoie 55, valeur déjà obtenue plus haut pour la somme des carrés. Troisième emploi, avec une fonction de la bibliothèque standard : somme_f(math.sqrt, 1, 4) renvoie 6.146264369941973, c'est-à-dire 1+2+3+2. Cas limite : somme_f(cube, 3, 2) renvoie 0, la boucle ne tournant pas. À retenir : on passe le nom de la fonction, sans parenthèses, et l'on teste le calcul générique avec au moins deux fonctions différentes.
k=1∑nk3=(2n(n+1))2
formule fermée qui sert de témoin pour le premier essai
Définition
Assertion et précondition
L'instruction assert condition, message vérifie, au moment où elle est exécutée, que la condition est vraie. Si elle l'est, l'exécution continue sans rien faire ; sinon, le programme s'interrompt en levant une AssertionError qui porte le message. Le message est facultatif, mais sans lui l'erreur ne dit pas ce qui a échoué. On y écrit les préconditions de la spécification, c'est-à-dire ce que l'appelant doit garantir : assert n >= 0, assert a != 0, assert 0 <= minutes < 60. Une assertion ne corrige rien et ne remplace pas un test de la logique du programme : elle arrête tôt un appel dont le résultat n'aurait aucun sens, à l'endroit même où la faute est commise, au lieu de laisser le calcul produire une valeur absurde trente lignes plus loin. C'est un outil de mise au point, désactivable par l'option -O de l'interpréteur : un programme ne doit donc jamais faire reposer sa logique sur un assert.
Méthode
Protéger une fonction par ses préconditions
Quand l'utiliser : à l'écriture de toute fonction dont la spécification comporte une précondition, et systématiquement quand le corps divise, prend une racine, un logarithme, ou accède à un rang. 1) Reprendre les préconditions déjà écrites dans la docstring, une par une : elles sont la liste exacte des assertions à poser. 2) Écrire un assertpar précondition, en tête du corps, avant tout calcul. Une assertion qui teste deux choses à la fois ne dit pas laquelle a échoué. 3) Donner à chacune un message qui décrit la contrainte violée, en français, et non le nom de la variable : « le coefficient dominant doit être non nul » est utilisable, « erreur » ne l'est pas. 4) Ne pas y mettre ce qui n'est pas une précondition : une donnée saisie par l'utilisateur ou lue dans un fichier n'est pas garantie par l'appelant, et se traite par try et except. 5) Tester la protection : un appel qui viole chaque précondition doit s'arrêter sur AssertionError, avec le bon message. Une assertion qu'aucun test n'a jamais fait échouer ne protège rien. 6) Ne jamais mettre la condition et le message entre une seule paire de parenthèses : l'assertion serait alors toujours vraie.
Exemple
Rédaction modèle : une fonction protégée et ses tests d'échec
Écrire une fonction qui convertit en minutes une durée donnée en heures et minutes, et la protéger par ses préconditions. Spécification. Entrées : heures, entier positif ; minutes, entier compris entre 0 et 59. Sortie : l'entier 60h+m. Les préconditions sont au nombre de deux, donc les assertions aussi : une durée négative n'a pas de sens, et un nombre de minutes supérieur ou égal à 60 signale un appel mal formé, dont le résultat serait pourtant un entier plausible, ce qui est le pire des cas.
def duree_en_minutes(heures, minutes):
"""Renvoie la durée en minutes.
Entrées : heures entier positif, minutes entier de 0 à 59.
Sortie : l'entier 60 * heures + minutes.
"""
assert heures >= 0, "heures doit être positif"
assert 0 <= minutes < 60, "minutes doit être compris entre 0 et 59"
return 60 * heures + minutes
Test du cas usuel : duree_en_minutes(2, 30) renvoie 150, ce que confirme le calcul 60×2+30=150. Test d'échec, un par précondition. duree_en_minutes(2, 75) s'interrompt sur AssertionError: minutes doit être compris entre 0 et 59, et c'est bien la seconde assertion qui a parlé : le message le dit. De même, un appel avec un nombre d'heures négatif s'arrête sur AssertionError: heures doit être positif. Ce qu'il ne faut pas écrire : assert (0 <= minutes < 60, "minutes doit être compris entre 0 et 59"). Les parenthèses feraient de la condition et du message un couple non vide, donc vrai, et l'appel duree_en_minutes(2, 75) renverrait tranquillement 195. À retenir : une assertion par précondition, un message en français qui nomme la contrainte, et un test d'échec par assertion, sans quoi la protection n'a jamais été éprouvée.
Piège
Mettre une assertion entre parenthèses
Ligne fautive : assert (x > 0, "x doit être strictement positif"). Les parenthèses réunissent la condition et le message en un seul objet, un couple de deux éléments, que Python considère comme vrai parce qu'il est non vide. L'assertion est donc toujours vraie, quelle que soit la valeur de x, et ne protège plus rien. Avec x = -3, le programme continue sans lever la moindre AssertionError. Python signale d'ailleurs le danger, mais par un simple avertissement, SyntaxWarning: assertion is always true, perhaps remove parentheses?, qui se perd dans la sortie et n'arrête pas l'exécution. Version correcte : assert x > 0, "x doit être strictement positif", sans parenthèses englobantes, la virgule séparant deux choses distinctes, la condition et le message. Réflexe : après avoir écrit une assertion, l'éprouver une fois sur une valeur interdite ; si aucune erreur ne se lève, c'est l'assertion qui est fautive, pas le test.
Définition
Exceptions : try et except
Une exception est une interruption du cours normal du programme, déclenchée par une opération impossible, et qui remonte les appels jusqu'à ce que quelqu'un la rattrape ; personne ne la rattrapant, le programme s'arrête en affichant le message. Le bloc try la rattrape :
def lire_entier(texte):
"""Renvoie l'entier écrit dans texte, et None si texte n'est pas un entier."""
try:
return int(texte)
except ValueError:
return None
lire_entier("12") renvoie 12, et lire_entier("douze") renvoie None au lieu d'interrompre le programme. On écrit dans le try les seules lignes susceptibles d'échouer, et l'on nomme le type d'exception attendu après except : un except sans type rattraperait aussi les fautes de frappe du programme, et les cacherait. On rattrape ce qui vient du dehors, une saisie, un fichier, une donnée mal formée ; ce qui vient de l'appelant relève, lui, des préconditions.
Vocabulaire
Les messages d'erreur usuels
Chaque erreur porte un nom qui désigne une faute précise ; le reconnaître fait gagner l'essentiel du temps de correction. SyntaxError : la phrase n'est pas du Python, le plus souvent un deux-points ou une parenthèse manquants, comme SyntaxError: expected ':'. IndentationError : les blocs ne sont pas cohérents, par exemple IndentationError: expected an indented block after 'if' statement on line 1, quand le bloc qui suit un deux-points n'a pas été décalé, ou IndentationError: unindent does not match any outer indentation level. NameError : un nom est employé sans avoir été défini, NameError: name 'total_general' is not defined ; le plus souvent une faute de frappe, ou une variable définie dans une autre fonction. UnboundLocalError : un nom local est lu avant d'avoir reçu une valeur, UnboundLocalError: cannot access local variable 'compteur' where it is not associated with a value. TypeError : l'opération ne convient pas aux types en présence, TypeError: can only concatenate str (not "int") to str, ou TypeError: unsupported operand type(s) for *: 'int' and 'NoneType', signature d'une fonction qui affiche au lieu de renvoyer. ValueError : le type est bon, la valeur non, ValueError: invalid literal for int() with base 10: 'douze'. IndexError : un rang hors bornes, IndexError: list index out of range. ZeroDivisionError : division by zero pour / entre deux entiers, float division by zero dès qu'un opérande est flottant, integer division or modulo by zero pour // entre entiers et integer modulo by zero pour % entre entiers.
Méthode
Lire un message d'erreur et corriger la ligne fautive
Quand l'utiliser : dès qu'un programme s'interrompt. Le message n'est pas un reproche, c'est un diagnostic, et il se lit de bas en haut. 1) Lire la dernière ligne : elle donne le type de l'erreur et sa description. C'est elle qui dit de quelle faute il s'agit. 2) Remonter à la dernière ligne du fichier citée dans la trace : c'est l'endroit où l'exception s'est produite. Les lignes au-dessus disent qui a appelé qui, et se lisent quand la faute vient de plus haut. 3) Relire l'expression signalée en se demandant ce que vaut chaque nom qui y figure : un TypeError sur NoneType désigne une fonction qui affiche au lieu de renvoyer ; un IndexError désigne un rang calculé une unité trop grand ; un NameError désigne une faute de frappe ou une variable locale à une autre fonction. 4) Corriger une chose, puis relancer. Corriger trois lignes à la fois empêche de savoir laquelle était en cause. 5) Si le message ne suffit pas, afficher les valeurs juste avant la ligne fautive avec un print provisoire, ou appeler la fonction sur un cas minuscule où le résultat se calcule de tête. 6) SyntaxError et IndentationError sont signalées avant toute exécution : aucune ligne du programme n'a tourné, et le numéro indiqué peut être celui qui suit la ligne réellement fautive, par exemple une parenthèse restée ouverte.
Exemple
Rédaction modèle : diagnostic d'une fonction qui s'interrompt
Le programme suivant devait calculer la moyenne de trois notes ; il s'interrompt. Diagnostiquer et corriger.
# extrait : programme fautif, il s'interrompt à l'exécution
def moyenne(notes):
total = 0
for i in range(len(notes) + 1):
total = total + notes[i]
return total / len(notes)
print(moyenne([12, 8, 15]))
La trace obtenue, dont le chemin du fichier est abrégé :
Traceback (most recent call last):
File "…/moyenne.py", line 9, in <module>
print(moyenne([12, 8, 15]))
~~~~~~~^^^^^^^^^^^^^
File "…/moyenne.py", line 5, in moyenne
total = total + notes[i]
~~~~~^^^
IndexError: list index out of range
Lecture, de bas en haut. Dernière ligne : le type est IndexError, et la description dit qu'un rang sort des bornes. Dernière ligne du fichier citée : la ligne 5, dans la fonction moyenne, et les caractères soulignés désignent notes[i] : c'est donc i qui est en cause, non notes. Examen de i : la liste compte trois éléments, de rang 0, 1 et 2 ; or range(len(notes) + 1) fait prendre à i les valeurs 0, 1, 2 et 3. Au quatrième tour, le rang 3 n'existe pas. Correction, une seule chose à la fois : supprimer le + 1, qui vient d'un réflexe pris sur les sommes de 1 à n. Ici les rangs vont de 0 à n−1, et range(len(notes)) les donne exactement. Mieux encore, puisque le rang ne sert qu'à relire la valeur : parcourir directement les valeurs.
def moyenne(notes):
total = 0
for note in notes:
total = total + note
return total / len(notes)
Vérification : moyenne([12, 8, 15]) renvoie 11.666666666666666, et le calcul à la main donne 335. À retenir : la dernière ligne donne le type de la faute, la dernière ligne citée donne l'endroit, et l'on corrige une seule chose avant de relancer.
Piège
Une condition d'arrêt fondée sur l'égalité de deux flottants
Ligne fautive : while x != 1.0:, pour une variable x partie de 0.0 que le corps augmente de 0.1 à chaque tour. La dixième addition ne donne pas 1.0 mais 0.9999999999999999 : la condition x != 1.0 reste vraie, et la boucle ne s'arrête jamais. Que deux flottants ne se comparent pas par == ni par != est établi dans le thème Python : types, variables et expressions ; ce qui est propre à la boucle, c'est la conséquence : l'erreur ne donne pas un résultat faux, elle donne un programme qui ne rend jamais la main, et le calcul juste sur le papier n'y change rien. Deux versions correctes, toutes deux vérifiées. Compter les tours avec un entier, qui est exact, et reconstruire la valeur à chaque tour : une boucle for k in range(11) avec x = k / 10 parcourt exactement onze valeurs, dont la dernière est 1.0. Ou, si la condition doit porter sur la valeur, la rendre franchissable, avec une inégalité ou une tolérance : while x < 1.0 - 1e-9: et while abs(x - 1.0) > 1e-9: s'arrêtent l'une et l'autre au bout de dix tours. Réflexe : une condition d'arrêt ne s'écrit jamais avec == ni != entre deux flottants ; le nombre de tours se tient avec un entier, et la valeur décimale se calcule à partir de lui.
∣x−a∣≤ε
la condition à écrire à la place d'une égalité entre deux flottants
Vocabulaire
Les mots du thème
Paramètre : un nom de la ligne def. Argument : une valeur donnée à l'appel. Signature : le nom de la fonction et la liste de ses paramètres. Corps : le bloc indenté qui suit le def. Appel : l'exécution de la fonction sur des arguments. Spécification : le contrat, entrées, préconditions, sortie. Docstring : la chaîne entre triples guillemets qui le porte dans le programme. Précondition : ce que l'appelant garantit. Postcondition : ce que la fonction garantit en retour. Portée : la partie du programme où un nom désigne une variable donnée. Locale : créée dans un corps de fonction. Globale : créée au niveau principal. Effet de bord : toute modification qu'un appel laisse derrière lui autrement que par sa valeur renvoyée, affichage, écriture d'une globale, modification d'un objet reçu. Itération : un tour de boucle. Variable de boucle : celle qui prend les valeurs parcourues. Accumulateur : la variable qui porte le résultat partiel. Compteur : un accumulateur qui compte. Drapeau : une variable booléenne qui retient qu'un événement a eu lieu. Condition d'arrêt : la négation de la condition d'un while.
Formulaire
Les constructions du thème
Les squelettes à connaître par coeur. Ce ne sont pas des programmes complets : les noms condition, bloc, terme, convient, f, g et les valeurs initiales sont à remplacer par ce que donne l'énoncé, d'où la mention « extrait » en tête de chacun.
# extrait : disjonction de cas, du plus restrictif au plus large
if condition_1:
bloc_1
elif condition_2:
bloc_2
else:
bloc_3
# extrait : parcours d'un nombre de tours connu, de a à b inclus
for k in range(a, b + 1):
bloc
# extrait : répétition tant qu'une condition reste vraie
etat = valeur_initiale
while condition:
etat = mise_a_jour(etat)
# extrait : accumulation d'une somme
def somme(a, b):
total = 0
for k in range(a, b + 1):
total = total + terme(k)
return total
# extrait : accumulation d'un produit
def produit(a, b):
resultat = 1
for k in range(a, b + 1):
resultat = resultat * terme(k)
return resultat
# extrait : suite récurrente d'ordre un
def terme_ordre_un(n):
u = valeur_initiale
for _ in range(n):
u = f(u)
return u
# extrait : suite récurrente d'ordre deux
def terme_ordre_deux(n):
u, v = premiere_valeur, deuxieme_valeur
for _ in range(n):
u, v = v, g(v, u)
return u
# extrait : recherche du premier élément qui convient, avec sa valeur de repli
def premier_qui_convient(a, b):
for k in range(a, b + 1):
if convient(k):
return k
return -1
# extrait : fonction spécifiée et protégée par ses préconditions
def nom(parametres):
"""Renvoie ...
Entrées : ...
Sortie : ...
"""
assert precondition, "message"
corps
return resultat
# extrait : rattrapage d'une donnée venue du dehors
try:
valeur = int(texte)
except ValueError:
valeur = None
max(0,⌈pb−a⌉)
nombre de tours d'une boucle de pas strictement positif
k=a∑buk,k=a∏buk
les deux accumulations, initialisées à zéro et à un
Exercices
Exercice 1Application
Le tarif d'un colis, cas par cas
Un service d'expédition facture un colis d'après sa masse, exprimée en grammes et toujours entière : 250 centimes jusqu'à 250 g inclus ; 380 centimes au-delà, jusqu'à 500 g inclus ; 520 centimes au-delà, jusqu'à 1000 g inclus ; 890 centimes au-delà, jusqu'à 30000 g inclus. Un colis de plus de 30000 g est refusé, et une masse nulle ou négative n'a pas de sens. 1) Écrire la spécification de la fonction tarif(masse) : entrée, préconditions, sortie. 2) Écrire la fonction, avec une seule cascade et une assertion par précondition. 3) Donner le jeu de tests : une valeur par cas, chaque borne, et un appel interdit par chacune des préconditions. 4) Un camarade écrit les mêmes quatre conditions, mais range la cascade dans l'autre sens : masse <= 30000 en premier, puis masse <= 1000, puis masse <= 500, et 250 centimes sous le else. Que renvoie sa fonction pour une masse de 100 g ? Pourquoi Python ne signale-t-il aucune erreur ?
Voir le corrigé
1) Spécification. Entrée : masse, entier, en grammes. Préconditions : masse est supérieure ou égale à 1, et inférieure ou égale à 30000. Sortie : l'entier 250, 380, 520 ou 890, prix du colis en centimes. Les quatre cas sont donnés par quatre intervalles d'entiers consécutifs, deux à deux disjoints, dont la réunion est exactement l'ensemble des masses autorisées : la cascade peut donc se terminer par un else sans condition. 2) Les conditions sont rangées du plus restrictif au plus large, et chaque borne est incluse, d'où les <=.
def tarif(masse):
"""Renvoie le prix d'expédition d'un colis, en centimes.
Entrée : masse, entier, en grammes.
Préconditions : 1 <= masse et masse <= 30000.
Sortie : l'entier 250, 380, 520 ou 890, prix du colis en centimes.
"""
assert masse >= 1, "la masse doit valoir au moins un gramme"
assert masse <= 30000, "au-delà de 30 kg, le colis est refusé"
if masse <= 250:
return 250
elif masse <= 500:
return 380
elif masse <= 1000:
return 520
else:
return 890
La condition du else n'est pas écrite : c'est la négation des trois précédentes, c'est-à-dire masse > 1000, et c'est la seconde assertion, et elle seule, qui garantit que la masse ne dépasse pas 30000 g. 3) Une valeur par cas, puis les bornes 250, 500 et 1000, chacune suivie de la valeur qui la dépasse d'une unité, et enfin la borne supérieure 30000 : c'est sur une borne, et sur elle seule, qu'un < écrit à la place d'un <= se voit.
for masse in [100, 250, 251, 500, 501, 1000, 1001, 30000]:
print(masse, tarif(masse))
Appels interdits, un par précondition : tarif(0) s'interrompt sur AssertionError: la masse doit valoir au moins un gramme, et tarif(30001) sur AssertionError: au-delà de 30 kg, le colis est refusé. Ces deux appels font partie du jeu de tests : une assertion qu'aucun test n'a jamais fait échouer ne protège rien. 4) Sa fonction renvoie 890 pour une masse de 100 g.
Toute masse autorisée vérifie la première condition, qui est la plus large : le premier test vrai l'emporte, l'évaluation s'arrête là, et les trois branches suivantes sont inatteignables. La fonction renvoie donc 890 pour tout colis accepté, et 250 pour les colis qu'elle aurait dû refuser. Python ne signale rien parce qu'il n'y a rien à signaler : les quatre conditions sont écrites correctement, chaque branche est syntaxiquement valide, et la valeur renvoyée est un entier plausible. C'est l'ordre des tests qui est faux, et l'ordre des tests fait partie du programme, non de sa syntaxe. Seul un jeu de tests couvrant un cas par branche révèle la faute. À retenir : une disjonction de cas s'écrit en une seule cascade, du plus restrictif au plus large, et se teste sur une valeur par cas plus chaque borne.
Exercice 2Application
Trois accumulations et leurs cas limites
On demande trois fonctions, écrites chacune par accumulation, et l'on notera à chaque fois ce que contient l'accumulateur après le tour d'indice k. 1) somme_impairs(n) renvoie 1+3+⋯+(2n−1), pour n entier naturel. Vérifier le résultat sur la formule fermée n2 pour n=7, puis traiter le cas n=0. 2) produit_pairs(n) renvoie 2×4×⋯×(2n), pour n entier naturel. Vérifier sur n=5 à l'aide de l'égalité 2×4×⋯×(2n)=2nn!, puis traiter le cas n=0. 3) compte_multiples(a, b, d) renvoie le nombre de multiples de d compris entre a et b inclus, pour a et b entiers et d entier strictement positif. Que doit renvoyer la fonction lorsque b est strictement inférieur à a ? Le vérifier.
Voir le corrigé
1) L'accumulateur total contient, après le tour d'indice k, la somme des k premiers entiers impairs. Avant le premier tour, aucun terme n'a été ajouté : il vaut 0, élément neutre de l'addition, qui est aussi la valeur de la somme vide.
def somme_impairs(n):
"""Renvoie la somme des n premiers entiers impairs.
Entrée : n entier naturel.
Sortie : l'entier 1 + 3 + ... + (2n - 1), et 0 si n vaut 0.
"""
assert n >= 0, "n doit être un entier naturel"
total = 0
for k in range(1, n + 1):
total = total + (2 * k - 1)
return total
print(somme_impairs(7), 7 ** 2)
print(somme_impairs(0), somme_impairs(1))
49 49
0 1
Le terme d'indice k est 2k−1 : pour k allant de 1 à n, il parcourt 1,3,…,2n−1, d'où l'en-tête range(1, n + 1), borne de droite exclue. Pour n=0, la boucle ne tourne pas et la fonction renvoie 0, ce qui est bien 02. 2) L'accumulateur produit contient, après le tour d'indice k, le produit des k premiers entiers pairs non nuls. Il est initialisé à 1, élément neutre de la multiplication et valeur du produit vide.
import math
def produit_pairs(n):
"""Renvoie le produit des n premiers entiers pairs non nuls.
Entrée : n entier naturel.
Sortie : l'entier 2 * 4 * ... * (2n), et 1 si n vaut 0.
"""
assert n >= 0, "n doit être un entier naturel"
produit = 1
for k in range(1, n + 1):
produit = produit * (2 * k)
return produit
print(produit_pairs(5), 2 ** 5 * math.factorial(5))
print(produit_pairs(0))
3840 3840
1
L'égalité 2×4×⋯×(2n)=2nn! s'obtient en mettant un facteur 2 en évidence dans chacun des n facteurs. Pour n=0, la fonction renvoie 1 : initialiser à 0 donnerait 0 pour toute valeur de n, et initialiser au premier facteur 2 obligerait à traiter à part le cas où il n'y a aucun facteur. 3) Le compteur contient, après le tour d'indice k, le nombre de multiples de d rencontrés parmi les entiers de a à k. Il part de 0.
def compte_multiples(a, b, d):
"""Renvoie le nombre de multiples de d compris entre a et b inclus.
Entrées : a et b entiers, d entier strictement positif.
Sortie : l'entier égal au nombre de k tels que a <= k <= b et d divise k,
et 0 si b est strictement inférieur à a.
"""
assert d > 0, "d doit être un entier strictement positif"
compteur = 0
for k in range(a, b + 1):
if k % d == 0:
compteur = compteur + 1
return compteur
print(compte_multiples(10, 30, 7), compte_multiples(5, 4, 3), compte_multiples(-6, 6, 4))
3 0 3
Pour parcourir les entiers de a à b inclus, l'en-tête est range(a, b + 1). Lorsque b est strictement inférieur à a, cette plage est vide : la boucle ne tourne pas, le compteur garde sa valeur initiale, et la fonction renvoie 0. C'est la bonne réponse, puisqu'aucun entier ne vérifie la condition. Les trois appels vérifiés sont 14, 21 et 28 entre 10 et 30 ; aucun entre 5 et 4 ; −4, 0 et 4 entre −6 et 6. À retenir : l'initialisation se lit sur l'opération, l'en-tête de boucle sur les bornes de l'énoncé, et c'est la plage vide qui dit si l'initialisation est la bonne.
Exercice 3Classique
Deux boucles while et ce qu'elles garantissent
1) Écrire nombre_de_doublements(N) qui renvoie le plus petit entier n≥0 tel que 2n>N, pour N entier naturel, sans employer de logarithme. Écrire en une phrase ce que contiennent les variables à chaque passage en tête de boucle, puis ce que l'on sait à la sortie. 2) Vérifier la fonction sur N=0, N=1, N=7, N=8 et N=1000, en justifiant chaque valeur à la main. 3) Écrire nombre_de_chiffres(n) qui renvoie le nombre de chiffres de l'écriture décimale de n, pour n entier naturel, en divisant par 10 jusqu'à épuisement. Attention à n=0. 4) Pour chacune des deux boucles, dire quelle quantité entière positive décroît strictement à chaque tour, et pourquoi la boucle s'arrête donc au bout d'un nombre fini de tours.
Voir le corrigé
1) L'état du calcul tient en deux variables : n compte les doublements déjà faits, et puissance vaut 2n. Avant le premier tour, aucun doublement n'a eu lieu : on pose n = 0 et puissance = 1, et la phrase est vraie, puisque 20=1. La condition de continuation est la négation de la condition d'arrêt : tant que 2n n'a pas dépassé N, il faut un doublement de plus, donc while puissance <= N.
def nombre_de_doublements(N):
"""Renvoie le plus petit entier n >= 0 tel que 2 ** n soit strictement plus grand que N.
Entrée : N entier naturel.
Sortie : un entier n >= 0.
"""
assert N >= 0, "N doit être un entier naturel"
puissance = 1
n = 0
while puissance <= N:
puissance = puissance * 2
n = n + 1
return n
print(nombre_de_doublements(0), nombre_de_doublements(1), nombre_de_doublements(7), nombre_de_doublements(8), nombre_de_doublements(1000))
0 1 3 4 10
À la sortie, la condition est fausse : puissance > N, c'est-à-dire 2n>N. Et si un tour au moins a eu lieu, la boucle n'a pas pu s'arrêter au tour précédent, donc 2n−1≤N : l'entier renvoyé est bien le plus petit qui convienne. Si aucun tour n'a eu lieu, l'entier renvoyé est 0, qui est le plus petit entier naturel. 2) Pour N=0 : 20=1>0, la boucle ne tourne pas et la fonction renvoie 0. Pour N=1 : 20=1 ne dépasse pas 1, mais 21=2>1, d'où 1. Pour N=7 : 22=4≤7 et 23=8>7, d'où 3. Pour N=8 : 23=8≤8, l'inégalité demandée étant stricte, et 24=16>8, d'où 4. La comparaison de N=7 et de N=8 est le test de la borne : c'est là, et seulement là, qu'un < écrit à la place d'un <= se verrait. Pour N=1000 : 29=512≤1000 et 210=1024>1000, d'où 10. 3) Le nombre de chiffres de 0 est 1, alors que la boucle de division ne tournerait aucune fois et laisserait le compteur à 0 : ce cas se traite à part, avant la boucle.
def nombre_de_chiffres(n):
"""Renvoie le nombre de chiffres de l'écriture décimale de n.
Entrée : n entier naturel.
Sortie : un entier supérieur ou égal à 1.
"""
assert n >= 0, "n doit être un entier naturel"
if n == 0:
return 1
compteur = 0
reste = n
while reste > 0:
reste = reste // 10
compteur = compteur + 1
return compteur
print(nombre_de_chiffres(0), nombre_de_chiffres(7), nombre_de_chiffres(10), nombre_de_chiffres(999), nombre_de_chiffres(1000))
1 1 2 3 4
La variable reste contient, après compteur tours, l'entier n privé de ses compteur derniers chiffres. À la sortie, la condition est fausse : reste vaut 0, donc tous les chiffres ont été retirés, et compteur les a comptés. Le paramètre n n'est pas modifié : c'est reste qui travaille, ce qui permet de relire n après la boucle si besoin. 4) Pour la première boucle, la quantité qui décroît est l'écart entre N et puissance : il est positif ou nul à chaque passage en tête de boucle, puisque c'est la condition de continuation, et il décroît strictement, puisque puissance, valant au moins 1, est au moins doublée à chaque tour. Pour la seconde, c'est reste lui-même : il est entier positif et, comme il est strictement supérieur à 0 à l'entrée du corps, reste // 10 est strictement plus petit que reste. Une quantité entière positive qui décroît strictement à chaque tour ne peut le faire qu'un nombre fini de fois : c'est l'argument de terminaison, qui porte le nom de variant de boucle et se rédige dans le thème Algorithmes élémentaires et preuve de programmes. À retenir : une boucle while s'écrit en trois temps, initialisation avant, condition de continuation, progression de l'état dans le corps ; et ce que l'on sait à la sortie, c'est que sa condition est fausse.
Exercice 4Classique
Une suite récurrente d'ordre deux
Soit (uk)k∈N la suite définie par u0=2, u1=5 et, pour tout k∈N, uk+2=5uk+1−6uk. 1) Calculer à la main u2, u3 et u4. 2) Écrire une fonction terme(n) qui renvoie un, pour n entier naturel, au moyen de deux variables mises à jour ensemble. Écrire la phrase qui dit quel terme chaque variable contient après j tours, et expliquer pourquoi elle reste vraie d'un tour au suivant. 3) Écrire une seconde version, terme_temporaire(n), qui met les deux variables à jour l'une après l'autre au moyen d'une variable temporaire, et vérifier que les deux fonctions donnent les mêmes valeurs. 4) Montrer que la suite de terme général 2n+3n vérifie les mêmes deux premiers termes et la même relation de récurrence, et en déduire une expression de un. Confronter la fonction à cette expression pour n allant de 0 à 6. 5) Sans exécuter le programme, dire ce que renverrait la fonction de la question 2 si l'on écrivait return v au lieu de return u.
Voir le corrigé
1) u2=5u1−6u0=25−12=13, puis u3=5u2−6u1=65−30=35, puis u4=5u3−6u2=175−78=97. 2) La récurrence est d'ordre 2 : il faut garder deux termes consécutifs, donc deux variables. Phrase de l'invariant : après j tours, u contient uj et v contient uj+1. Avant le premier tour, u vaut 2 et v vaut 5, c'est-à-dire u0 et u1 : la phrase est vraie.
def terme(n):
"""Renvoie u_n pour u_0 = 2, u_1 = 5 et u_(k+2) = 5 u_(k+1) - 6 u_k.
Entrée : n entier naturel.
Sortie : l'entier u_n.
"""
assert n >= 0, "n doit être un entier naturel"
u, v = 2, 5
for _ in range(n):
u, v = v, 5 * v - 6 * u
return u
L'affectation u, v = v, 5 * v - 6 * u évalue d'abord ses deux expressions de droite, avec les anciennes valeurs, puis affecte. Si la phrase est vraie après j tours, alors, au tour suivant, u reçoit l'ancienne valeur de v, c'est-à-dire uj+1, et v reçoit 5uj+1−6uj, c'est-à-dire uj+2 : la phrase est vraie après j+1 tours. La boucle faisant n tours, u contient un à la sortie. 3) Il faut garder l'ancienne valeur de u avant de l'écraser, sans quoi la seconde ligne calculerait 5uj+1−6uj+1.
def terme_temporaire(n):
"""Renvoie u_n, les deux variables étant mises à jour l'une après l'autre."""
assert n >= 0, "n doit être un entier naturel"
u, v = 2, 5
for _ in range(n):
ancien_u = u
u = v
v = 5 * v - 6 * ancien_u
return u
4) Posons wn=2n+3n pour tout n∈N. On a w0=1+1=2=u0 et w1=2+3=5=u1. Pour tout k∈N : 5wk+1−6wk=5(2k+1+3k+1)−6(2k+3k)=(10−6)2k+(15−6)3k=4×2k+9×3k=2k+2+3k+2=wk+2. Les deux suites ont donc les mêmes deux premiers termes et vérifient la même relation d'ordre 2 : par une récurrence à deux termes (bloc Fondamental), elles sont égales, donc un=2n+3n pour tout n∈N.
for n in range(7):
print(n, terme(n), terme_temporaire(n), 2 ** n + 3 ** n)
Les trois colonnes coïncident, et les valeurs des rangs 2, 3 et 4 sont celles calculées à la main. 5) D'après la phrase de l'invariant, v contient uj+1 après j tours : après les n tours de la boucle, v contient un+1. La fonction renverrait donc le terme suivant celui qui est demandé, c'est-à-dire 5 pour n=0 au lieu de 2. C'est l'intérêt d'écrire la phrase : elle dit quelle variable renvoyer, et l'erreur d'un cran se voit sans exécuter le programme. À retenir : à l'ordre 2, deux variables, une mise à jour simultanée ou une variable temporaire, et une phrase qui nomme le terme contenu par chacune.
Exercice 5Classique
Le premier carré parfait d'une plage, et le dernier
Un entier naturel k est un carré parfait s'il existe un entier naturel j tel que k=j2. 1) Écrire est_un_carre(k), pour k entier naturel, qui renvoie True ou False, au moyen d'une boucle while et sans employer de racine carrée. Dire ce que l'on sait de j à la sortie de la boucle, et pourquoi cela suffit à conclure. 2) Écrire la spécification, puis la fonction premier_carre(a, b) qui renvoie le plus petit carré parfait compris entre a et b inclus, pour a entier naturel et b entier. Décider et écrire ce que la fonction renvoie lorsqu'aucun entier de la plage ne convient. 3) Écrire dernier_carre(a, b), qui renvoie cette fois le plus grand. Une seule ligne change. 4) Écrire, hors de toute fonction, la variante de la question 2 qui emploie break au lieu de return, et dire où se place la valeur du cas « rien ne convient ». 5) Tester les trois situations sur chacune des versions : la réponse au premier tour, la réponse au dernier tour, et aucune réponse.
Voir le corrigé
1) On cherche le plus petit entier naturel j tel que j2≥k, en partant de j=0 et en avançant d'une unité tant que j2<k.
def est_un_carre(k):
"""Dit si l'entier naturel k est le carré d'un entier naturel.
Entrée : k entier naturel.
Sortie : True si k est un carré parfait, False sinon.
"""
assert k >= 0, "k doit être un entier naturel"
j = 0
while j * j < k:
j = j + 1
return j * j == k
print(est_un_carre(0), est_un_carre(1), est_un_carre(2), est_un_carre(15), est_un_carre(16))
True True False False True
À la sortie, la condition est fausse : j2≥k. Et comme la boucle n'a pas pu s'arrêter au tour précédent, ou bien j vaut 0, ou bien (j−1)2<k. Dans les deux cas, j est le plus petit entier naturel dont le carré atteint ou dépasse k. Si un entier naturel i vérifiait i2=k, il vérifierait i2≥k, donc i≥j par minimalité, donc i2≥j2≥k=i2, d'où j2=k. Tester la seule égalité j2=k suffit donc à conclure, et c'est ce que renvoie la dernière ligne. Les carrés sont ici détectés exactement, sans aucun flottant. 2) Spécification. Entrées : a entier naturel, b entier. Précondition : a est positif, pour que est_un_carre puisse être appelée sur chaque entier parcouru. Sortie : le plus petit entier k tel que a <= k <= b et k carré parfait, et l'entier −1 s'il n'en existe aucun, en particulier lorsque b est strictement inférieur à a. Le nombre de tours est borné par la plage : on écrit donc une boucle for, et l'on sort dès que la réponse est trouvée. Le calcul se faisant dans une fonction, return est préférable à break.
def premier_carre(a, b):
"""Renvoie le plus petit carré parfait de a à b inclus.
Entrées : a entier naturel, b entier.
Sortie : cet entier, ou -1 si aucun entier de a à b n'est un carré parfait.
"""
assert a >= 0, "a doit être un entier naturel"
for k in range(a, b + 1):
if est_un_carre(k):
return k
return -1
Le dernier return est à la marge du for : on ne l'atteint qu'après avoir épuisé tous les tours sans jamais trouver de carré. 3) Il suffit de parcourir la plage dans l'autre sens, de b à a inclus, ce que donne le pas −1 : la borne de droite restant exclue, on écrit a - 1.
def dernier_carre(a, b):
"""Renvoie le plus grand carré parfait de a à b inclus.
Entrées : a entier naturel, b entier.
Sortie : cet entier, ou -1 si aucun entier de a à b n'est un carré parfait.
"""
assert a >= 0, "a doit être un entier naturel"
for k in range(b, a - 1, -1):
if est_un_carre(k):
return k
return -1
4) Hors d'une fonction, il n'y a pas de return : on range la réponse dans une variable, initialisée à la valeur du cas « rien ne convient », et l'on quitte la boucle par break. La valeur de repli n'est plus écrite après la boucle mais avant elle, dans l'initialisation, et c'est elle que l'on lit si aucun tour n'a déclenché le break.
a, b = 17, 24
reponse = -1
for k in range(a, b + 1):
if est_un_carre(k):
reponse = k
break
print(reponse)
-1
5) Les trois situations sur chacune des trois versions :
Réponse au premier tour : premier_carre(9, 9) renvoie 9. Réponse au dernier tour : premier_carre(10, 16) renvoie 16, qui est la dernière valeur parcourue. Aucune réponse : premier_carre(17, 24) renvoie −1, les entiers de 17 à 24 étant tous strictement compris entre 16 et 25. Enfin premier_carre(5, 4) renvoie −1 sans faire le moindre tour. Les mêmes trois situations sur dernier_carre, qui parcourt la plage à l'envers : dernier_carre(10, 16) renvoie 16 dès le premier tour, dernier_carre(9, 15) renvoie 9 au septième et dernier, et dernier_carre(17, 24) renvoie −1. La plage de 10 à 30 donne 25 et non 16 : c'est bien l'autre extrémité qui est rendue. Reste la variante à break, dont la question 4 a déjà montré le cas « rien ne convient ». Les deux autres situations, sur la plage réduite à 9 puis sur celle de 10 à 16 :
a, b = 9, 9
reponse = -1
for k in range(a, b + 1):
if est_un_carre(k):
reponse = k
break
print(reponse)
a, b = 10, 16
reponse = -1
for k in range(a, b + 1):
if est_un_carre(k):
reponse = k
break
print(reponse)
9
16
La sortie par break est ainsi éprouvée, et non la seule initialisation de repli : un test qui ne fait jamais jouer le break ne contrôle pas la ligne qui l'écrit. À retenir : décider d'abord ce que l'on renvoie quand rien ne convient, sortir par return dès que la réponse est trouvée, et tester les trois situations, la première, la dernière et l'absence de réponse.
Exercice 6Rédaction
Combien de tours fait une boucle for
Soient a, b et p trois entiers, avec p>0. On admet que la boucle for k in range(a, b, p) exécute son bloc une fois pour chaque entier de la forme a+jp avec j∈N et a+jp<b, dans l'ordre croissant des j. 1) Démontrer que le nombre de tours de cette boucle vaut max(0,⌈pb−a⌉), et que, lorsque ce nombre N n'est pas nul, la dernière valeur prise par k est a+(N−1)p. 2) En déduire le nombre de tours de for k in range(1, n + 1) et celui de for k in range(0, n, 2), pour n entier naturel, en distinguant dans le second cas n pair et n impair. 3) Écrire nombre_de_tours(a, b, p) qui renvoie ce nombre sans exécuter la moindre boucle, sachant que l'opérateur // de Python donne la partie entière inférieure du quotient. Écrire ensuite une fonction qui compte réellement les tours, et confronter les deux sur un domaine que l'on précisera.
Voir le corrigé
1) Notons J={j∈N∣a+jp<b} l'ensemble des indices des tours, et N son cardinal : d'après ce que l'on admet, la boucle exécute son bloc N fois, la valeur prise au tour d'indice j étant a+jp. Soit j∈N. Comme p>0, l'inégalité a+jp<b équivaut à jp<b−a, donc à j<pb−a. Posons x=pb−a, de sorte que J={j∈N∣j<x}. Premier cas : b≤a. Alors b−a≤0 et p>0, donc x≤0. Tout j∈N vérifie j≥0≥x, donc aucun ne vérifie j<x : l'ensemble J est vide et N=0. Par ailleurs x≤0 donne ⌈x⌉≤0, donc max(0,⌈x⌉)=0 : la formule est vérifiée, et la boucle n'a pas de dernière valeur. Second cas : b>a. Alors x>0. Montrons que pour tout j∈Z, l'inégalité j<x équivaut à j≤⌈x⌉−1. Supposons j<x. Comme x≤⌈x⌉, on a j<⌈x⌉ ; ces deux nombres étant entiers, on en déduit j≤⌈x⌉−1. Réciproquement, supposons j≤⌈x⌉−1. Comme ⌈x⌉<x+1, on a ⌈x⌉−1<x, donc j<x. Ainsi J={j∈N∣j≤⌈x⌉−1}. Comme x>0, on a ⌈x⌉≥1, donc ⌈x⌉−1≥0 et J={0,1,…,⌈x⌉−1}, ensemble de cardinal N=⌈x⌉. Ce nombre étant positif, il est égal à max(0,⌈x⌉), et la formule est encore vérifiée. Enfin, le plus grand élément de J est N−1 et, comme p>0, l'application j↦a+jp est strictement croissante : la dernière valeur prise par k, qui est celle du plus grand indice, vaut a+(N−1)p. Dans les deux cas, le nombre de tours vaut max(0,⌈pb−a⌉). 2) Pour for k in range(1, n + 1), on a a=1, b=n+1 et p=1, donc x=n. Comme n est un entier naturel, ⌈x⌉=n≥0 et le nombre de tours vaut n. Si n≥1, la dernière valeur prise est 1+(n−1)×1=n : la boucle parcourt bien les entiers de 1 à n inclus, ce qui justifie l'en-tête employé pour toute somme allant de 1 à n. Pour for k in range(0, n, 2), on a a=0, b=n et p=2, donc x=2n. Si n=2m avec m∈N, alors x=m est entier, ⌈x⌉=m et le nombre de tours vaut m=2n ; la dernière valeur, lorsque m≥1, est 2(m−1)=n−2. Si n=2m+1 avec m∈N, alors m<x<m+1, donc ⌈x⌉=m+1 et le nombre de tours vaut m+1=2n+1 ; la dernière valeur est 2m=n−1. Dans les deux cas, la boucle parcourt les entiers pairs de 0 à n exclu. 3) Pour tout réel t, on a ⌈t⌉=−⌊−t⌋. En appliquant cette égalité à t=pb−a, il vient ⌈pb−a⌉=−⌊pa−b⌋, et comme // donne la partie entière inférieure du quotient, cette valeur s'écrit -((a - b) // p) en Python.
def nombre_de_tours(a, b, p):
"""Renvoie le nombre de tours de for k in range(a, b, p), sans boucler.
Entrées : a, b, p entiers, avec p strictement positif.
Sortie : l'entier max(0, plafond de (b - a) / p).
"""
assert p > 0, "le pas doit être strictement positif"
return max(0, -((a - b) // p))
def tours_comptes(a, b, p):
"""Renvoie le nombre de tours réellement exécutés par la boucle.
Entrées : a, b, p entiers, avec p strictement positif.
Sortie : l'entier égal au nombre de tours de for k in range(a, b, p).
"""
assert p > 0, "le pas doit être strictement positif"
compteur = 0
for _ in range(a, b, p):
compteur = compteur + 1
return compteur
Le domaine de confrontation est choisi pour contenir les cas limites : bornes dans le désordre, bornes égales, bornes négatives, et un pas qui ne divise pas l'écart. On prend a et b parcourant les entiers de −10 à 10, et p de 1 à 5, ce qui fait 21×21×5=2205 triplets.
desaccords = 0
for a in range(-10, 11):
for b in range(-10, 11):
for p in range(1, 6):
if nombre_de_tours(a, b, p) != tours_comptes(a, b, p):
desaccords = desaccords + 1
print(desaccords, "désaccord(s) sur 2205 triplets")
0 désaccord(s) sur 2205 triplets
Ce contrôle ne remplace pas la démonstration : il l'éprouve sur un domaine fini. C'est la démonstration qui vaut pour tous les entiers, et le programme qui dit que la traduction en Python de la formule est fidèle. À retenir : la borne de gauche est atteinte, la borne de droite ne l'est jamais, et le nombre de tours se lit sur le quotient de l'écart par le pas, arrondi vers le haut.
Exercice 7Trouver l'erreur
L'accumulateur qui ne cumule rien
On demande une fonction qui renvoie ∑k=1nk2, pour n entier naturel. Un étudiant rédige :
def somme_des_carres(n):
"""Renvoie la somme des carrés des entiers de 1 à n.
Entrée : n entier naturel.
Sortie : l'entier 1 + 4 + ... + n * n, et 0 si n vaut 0.
"""
for k in range(1, n + 1):
total = 0
total = total + k * k
return total
et il justifie ainsi son programme : « L'accumulateur total part de 0 et reçoit le carré de k à chaque tour ; après le dernier tour, il contient la somme demandée. J'ai vérifié : somme_des_carres(1) renvoie bien 1. Et pour n=0, la boucle ne tourne pas, donc la fonction renvoie 0, valeur de la somme vide. » Trouver l'erreur, dire pourquoi elle invalide le programme, puis donner la version correcte et le jeu de tests qui l'aurait démasquée.
Voir le corrigé
L'erreur est l'emplacement de l'initialisation : la ligne total = 0 est écrite dans le corps de la boucle, à la même indentation que la mise à jour, alors qu'elle doit venir avant la boucle, à la marge du for. Pourquoi cela invalide le programme. L'indentation, et elle seule, dit à quel bloc appartient une ligne : total = 0 est donc exécutée à chaque tour, et remet l'accumulateur à zéro juste avant de lui ajouter le terme courant. Après le tour d'indice k, la variable total ne contient pas la somme des carrés de 1 à k, mais le seul carré k2. La fonction renvoie donc n2 au lieu de la somme demandée.
def somme_des_carres(n):
for k in range(1, n + 1):
total = 0
total = total + k * k
return total
print(somme_des_carres(1), somme_des_carres(2), somme_des_carres(5), somme_des_carres(10))
1 4 25 100
Le contrôle que l'étudiant a fait ne pouvait pas échouer : pour n=1, la somme vaut 1 et le dernier carré aussi. Un test qui ne distingue pas la fonction attendue de la fonction écrite ne contrôle rien, et c'est précisément le cas de la plus petite valeur possible. La seconde affirmation est fausse elle aussi, et pour une raison différente. Pour n=0, la boucle ne tourne pas ; or la variable total n'est affectée que dans le corps de la boucle. Le nom total étant affecté quelque part dans le corps de la fonction, il est local dans tout ce corps, y compris à la ligne return, où il n'a encore reçu aucune valeur. L'appel ne renvoie donc pas 0 : il s'interrompt. Voici la trace obtenue en remplaçant la dernière ligne du programme ci-dessus par print(somme_des_carres(0)), le chemin du fichier étant abrégé.
Traceback (most recent call last):
File "…/carres.py", line 8, in <module>
print(somme_des_carres(0))
~~~~~~~~~~~~~~~~^^^
File "…/carres.py", line 5, in somme_des_carres
return total
^^^^^
UnboundLocalError: cannot access local variable 'total' where it is not associated with a value
Version correcte. L'initialisation remonte avant la boucle, à la même indentation que le return, et la précondition annoncée par la spécification est posée en assertion.
def somme_des_carres(n):
"""Renvoie la somme des carrés des entiers de 1 à n.
Entrée : n entier naturel.
Sortie : l'entier 1 + 4 + ... + n * n, et 0 si n vaut 0.
"""
assert n >= 0, "n doit être un entier naturel"
total = 0
for k in range(1, n + 1):
total = total + k * k
return total
for n in [0, 1, 5, 10]:
print(n, somme_des_carres(n), n * (n + 1) * (2 * n + 1) // 6)
0 0 0
1 1 1
5 55 55
10 385 385
Le jeu de tests qui aurait démasqué l'erreur comporte deux appels que l'étudiant n'a pas faits. D'abord une valeur assez grande pour que la somme diffère du dernier terme, confrontée à la formule fermée 6n(n+1)(2n+1) du cours : pour n=5, elle donne 65×6×11=55, et la fonction fautive renvoyait 25. Ensuite la plage vide, n=0, qui aurait révélé l'interruption au lieu du 0 annoncé. À retenir : dans une accumulation, l'initialisation est alignée avec le return, jamais avec la mise à jour ; et un test choisi sur la plus petite valeur possible est souvent celui qui ne peut pas échouer.
Exercice 8Approfondissement
Encadrer un zéro par dichotomie
Soit f une fonction d'un réel vers un réel, continue sur un segment [a,b] et telle que f(a)×f(b)≤0. Le théorème des valeurs intermédiaires assure alors que f s'annule au moins une fois sur [a,b]. 1) Écrire la spécification, puis la fonction dichotomie(f, a, b, precision) qui renvoie un couple (g,d) tel que a≤g≤d≤b, d−g≤precision et f(g)×f(d)≤0. La protéger par ses préconditions. 2) Justifier que la propriété f(g)×f(d)≤0 est vraie à chaque passage en tête de boucle. Dire ce que la condition du while garantit à la sortie, puis donner le nombre de tours en fonction de b−a et de la précision. 3) L'employer pour encadrer 2 à 10−6 près, en passant une fonction anonyme, et comparer à math.sqrt(2). L'employer ensuite pour l'unique solution de x3+x=1 sur [0,1]. 4) Un étudiant propose de remplacer la condition du while par f(milieu) != 0, pour s'arrêter dès que le zéro est atteint. Dire ce que produit cette substitution écrite telle quelle, puis ce qui se passerait sur la fonction x↦x2−2 sur [1,2] une fois le milieu calculé avant la boucle et de nouveau en fin de corps. 5) Modifier la fonction pour qu'elle renvoie aussi le nombre d'évaluations de f. Pourquoi un compteur tenu dans une variable globale serait-il une mauvaise réponse ?
Voir le corrigé
1) Spécification. Entrées : f, fonction d'un réel vers un réel, continue sur [a,b] ; a et b réels ; precision réel strictement positif. Préconditions : a <= b, precision > 0, et f(a) * f(b) <= 0. Sortie : le couple (g,d) de réels tel que a≤g≤d≤b, d−g≤precision et f(g)×f(d)≤0 ; f s'annule donc entre g et d. La continuité de f n'est pas vérifiable par une assertion : elle reste une hypothèse de la spécification, que l'appelant garantit. Les trois autres préconditions se posent, elles, en assertions. Une quatrième contrainte, qu'aucune assertion simple n'exprime, est dégagée à la question 2 : la précision demandée doit rester atteignable en arithmétique flottante.
def dichotomie(f, a, b, precision):
"""Renvoie un encadrement d'un zéro de f par dichotomie.
Entrées : f fonction d'un réel vers un réel, continue sur [a, b] ;
a et b réels ; precision réel strictement positif.
Préconditions : a <= b, precision > 0 et f(a) * f(b) <= 0.
Sortie : le couple (g, d) tel que a <= g <= d <= b, d - g <= precision
et f(g) * f(d) <= 0.
"""
assert a <= b, "l'intervalle doit être donné dans l'ordre croissant"
assert precision > 0, "la précision doit être strictement positive"
assert f(a) * f(b) <= 0, "f doit changer de signe entre a et b"
gauche = a
droite = b
while droite - gauche > precision:
milieu = (gauche + droite) / 2
if f(gauche) * f(milieu) <= 0:
droite = milieu
else:
gauche = milieu
return gauche, droite
Le paramètre f est employé comme une fonction, avec des parenthèses, et aucun nom de fonction particulière n'apparaît dans le corps : c'est ce qui rend le calcul générique. 2) Avant le premier tour, gauche vaut a et droite vaut b : la propriété f(g)×f(d)≤0 est la troisième précondition. Supposons-la vraie en tête d'un tour et posons m le milieu. Si f(g)×f(m)≤0, le programme remplace d par m et la propriété reste vraie. Sinon, f(g)×f(m)>0, donc f(g) et f(m) sont non nuls et de même signe ; comme f(g)×f(d)≤0, le réel f(d) est nul ou de signe contraire à celui de f(g), donc contraire à celui de f(m) : le produit f(m)×f(d) est négatif ou nul, et le programme, qui remplace g par m, conserve la propriété. Elle est donc vraie à chaque passage en tête de boucle, et en particulier à la sortie. À la sortie, la condition du while est fausse : droite - gauche <= precision. Combinée à la propriété précédente et au fait que [g,d] reste inclus dans [a,b], elle donne exactement la postcondition annoncée. Nombre de tours. Chaque tour remplace l'un des deux bords par le milieu, donc divise par 2 la largeur droite - gauche : après j tours, cette largeur vaut 2jb−a. La boucle s'arrête au premier j tel que 2jb−a≤ε, où ε désigne la précision demandée, c'est-à-dire au premier j tel que 2j≥εb−a. Si b−a>ε, ce nombre de tours vaut donc ⌈log2εb−a⌉ ; sinon la boucle ne tourne pas. La terminaison est assurée du même coup : la quantité 2jεb−a est divisée par deux à chaque tour, donc elle finit par devenir inférieure ou égale à 1, ce qui est exactement la condition d'arrêt. Cet argument vaut pour le calcul exact, et pour lui seul. Sur des flottants, la largeur cesse de décroître dès que gauche et droite sont deux flottants consécutifs : leur milieu retombe alors sur l'une des deux bornes, et la condition du while ne devient jamais fausse. Sur [1,2], l'écart entre deux flottants voisins vaut 2−52, soit environ 2,22×10−16, et la largeur atteint cette valeur au cinquante-deuxième tour pour n'en plus bouger : une précision de 10−6 s'obtient en 20 tours, une précision de 10−15 en 50, mais une précision de 10−16 ne s'obtient jamais. La précondition precision > 0 ne suffit donc pas à garantir l'arrêt : il faut y ajouter que la précision demandée reste grande devant l'écart entre deux flottants voisins de l'intervalle. 3) On passe le nom de la fonction, sans parenthèses, ou directement une fonction anonyme lorsque le calcul ne sert qu'ici.
import math
g, d = dichotomie(lambda x: x * x - 2, 1, 2, 1e-6)
print(g, d)
print(math.sqrt(2))
La fonction x↦x2−2 est continue sur [1,2], et (12−2)(22−2)=(−1)×2=−2≤0 : les préconditions sont réunies. La valeur donnée par math.sqrt est bien comprise entre les deux bornes renvoyées, dont l'écart vaut 2201, soit environ 9,5×10−7 : la boucle a fait 20 tours, ce qui est bien le plus petit entier j tel que 2j≥106, puisque 219=524288 et 220=1048576.
def f_cube(x):
"""Renvoie x au cube plus x moins un."""
return x ** 3 + x - 1
g, d = dichotomie(f_cube, 0, 1, 1e-6)
print(g, d)
0.6823272705078125 0.6823282241821289
Ici fcube est continue sur [0,1], avec f(0)=−1 et f(1)=1, donc le produit vaut −1≤0. Le calcul a été mené avec deux fonctions différentes, comme il se doit pour un calcul générique : une seule n'aurait rien prouvé sur la généricité. 4) Écrite telle quelle, la substitution ne donne pas une boucle infinie : elle s'interrompt à la première évaluation de la condition. Dans la fonction de la question 1, milieu n'est affecté que dans le corps de la boucle ; le nom étant affecté quelque part dans le corps de la fonction, il y est local partout, y compris dans la condition du while, qui est évaluée avant le premier tour. L'appel s'arrête donc sur UnboundLocalError: cannot access local variable 'milieu' where it is not associated with a value, sans faire un seul tour. Réparons ce défaut, comme le propose l'énoncé : le milieu est calculé avant la boucle, puis de nouveau en fin de corps, et la condition s'écrit while f(milieu) != 0. Sur [1,2], les milieux successifs sont alors des rationnels de la forme 1+2jq, et le carré d'un rationnel ne vaut jamais 2, puisque 2 est irrationnel. À cela s'ajoute que les calculs sont faits sur des flottants, où l'égalité de deux valeurs voisines n'est de toute façon pas atteinte. La condition f(milieu) != 0 reste donc vraie indéfiniment : le programme ne rend jamais la main, sans produire la moindre erreur. Vu à l'exécution : après trois mille tours, gauche vaut 1.414213562373095 et droite vaut 1.4142135623730951, deux flottants consécutifs, et la boucle tourne encore. Une condition d'arrêt ne s'écrit jamais avec == ni != entre deux flottants ; ici elle s'écrit sur la largeur de l'encadrement, qui, elle, franchit la précision demandée. 5) Le nombre d'évaluations est un résultat : il se renvoie. On en profite pour n'évaluer f qu'une fois par tour, en gardant la valeur au bord gauche d'un tour au suivant.
def dichotomie_comptee(f, a, b, precision):
"""Renvoie l'encadrement et le nombre d'évaluations de f.
Entrées : comme dichotomie.
Sortie : le triplet (g, d, appels), où appels est le nombre d'appels de f.
"""
assert a <= b, "l'intervalle doit être donné dans l'ordre croissant"
assert precision > 0, "la précision doit être strictement positive"
gauche = a
droite = b
valeur_gauche = f(gauche)
valeur_droite = f(droite)
appels = 2
assert valeur_gauche * valeur_droite <= 0, "f doit changer de signe entre a et b"
while droite - gauche > precision:
milieu = (gauche + droite) / 2
valeur_milieu = f(milieu)
appels = appels + 1
if valeur_gauche * valeur_milieu <= 0:
droite = milieu
else:
gauche = milieu
valeur_gauche = valeur_milieu
return gauche, droite, appels
print(dichotomie_comptee(lambda x: x * x - 2, 1, 2, 1e-6))
print(dichotomie_comptee(f_cube, 0, 1, 1e-6))
On compte 22 appels, c'est-à-dire les deux évaluations aux bornes plus une par tour : les 20 tours prévus à la question 2 sont bien là. Un compteur tenu dans une variable globale serait une mauvaise réponse pour trois raisons. La fonction ne serait plus testable seule : son résultat dépendrait d'un nom extérieur, et le lecteur de la ligne def ne pourrait pas prévoir ce qu'elle produit. Deux appels enchaînés dans un même calcul cumuleraient leurs comptes, à moins que l'appelant ne pense à remettre le compteur à zéro entre les deux, ce que rien ne lui rappelle. Enfin, sans le mot-clé global, l'affectation créerait une variable locale et le compteur extérieur ne bougerait pas du tout : le programme serait faux en silence. À retenir : une fonction reçoit la fonction sur laquelle elle travaille, renvoie tous ses résultats, et sa condition d'arrêt porte sur une largeur qui décroît, jamais sur une égalité entre flottants.
QCM
12 questions : clique sur une réponse pour voir la correction.
Question 1
Que produit ce programme ?
def etiquette(n):
if n % 2 == 0:
return "pair"
elif n % 3 == 0:
return "multiple de trois"
elif n % 6 == 0:
return "multiple de six"
else:
return "autre"
print(etiquette(6))
print(etiquette(9))
print(etiquette(25))
Question 2
Combien de tours fait la boucle for k in range(1, 10, 3):, et quelle est la dernière valeur prise par k ?
Question 3
Une fonction calcule le produit 2×4×⋯×(2n) par accumulation, pour n entier naturel. Que doit valoir l'accumulateur avant la boucle, et que renvoie alors la fonction pour n=0 ?
Question 4
Une boucle while somme <= seuil: vient de se terminer. Son corps ne contient ni break ni return, et l'on ne sait rien d'autre de lui, ni des valeurs que les variables avaient avant la boucle. Laquelle de ces affirmations est certaine ?
Question 5
Qu'affiche ce programme ?
u, v = 2, 5
for _ in range(4):
u = v
v = 5 * v - 6 * u
print(u)
Question 6
Qu'affiche ce programme ?
total = 0
for k in range(1, 11):
if k % 3 == 0:
continue
total = total + k
if total > 20:
break
print(total)
Question 7
Qu'obtient-on en exécutant ce programme ?
# extrait : à exécuter tel quel
def perimetre(cote):
print(4 * cote)
x = perimetre(3)
print(x + 1)
Question 8
Que vaut le paramètre limite lors de l'appel compare(10) écrit en dernière ligne ?
seuil = 5
def compare(x, limite=seuil):
if x > limite:
return "au-dessus"
else:
return "au-dessous"
seuil = 100
print(compare(10))
Question 9
Qu'obtient-on en exécutant ce programme ?
# extrait : à exécuter tel quel
compteur = 0
def enregistrer(valeur):
compteur = compteur + valeur
return compteur
print(enregistrer(3))
Question 10
Qu'obtient-on en exécutant ce programme ?
# extrait : à exécuter tel quel
def cube(k):
return k ** 3
def somme_f(f, a, b):
total = 0
for k in range(a, b + 1):
total = total + f(k)
return total
print(somme_f(cube(2), 1, 3))
Question 11
Cette fonction renvoie la partie entière de la racine carrée d'un entier naturel. Que produit l'appel racine_entiere(-3), selon que l'assertion est écrite sans les parenthèses englobantes, comme il se doit, ou avec elles, comme ci-dessous ?
def racine_entiere(n):
assert (n >= 0, "n doit être positif")
j = 0
while (j + 1) * (j + 1) <= n:
j = j + 1
return j
Question 12
Le programme suivant s'interrompt sur cette trace, dont le chemin du fichier est abrégé. Quel diagnostic est exact ?
# extrait : programme fautif, il s'interrompt à l'exécution
def moyenne_des_carres(n):
total = 0
for k in range(1, n + 1):
total = total + k * k
return total / n
print(moyenne_des_carres(0))
Traceback (most recent call last):
File "…/moyenne.py", line 9, in <module>
print(moyenne_des_carres(0))
~~~~~~~~~~~~~~~~~~^^^
File "…/moyenne.py", line 6, in moyenne_des_carres
return total / n
~~~~~~^~~
ZeroDivisionError: division by zero