NSI Première • Programme français, lycées de Montréal
Exercices corrigés de NSI Première : les bases de Python
Voici une série d'exercices corrigés de NSI de Première, sur les bases de la programmation Python. Elle s'adresse aux élèves des lycées français de Montréal, le Lycée Marie de France et le Collège Stanislas, qui suivent le programme français de la spécialité Numérique et Sciences Informatiques.
Elle couvre les types et les opérateurs, division entière, modulo et flottants (exercice 1), les expressions booléennes, les lois de De Morgan et l'évaluation en court-circuit (exercice 2), les boucles for et while avec la suite de Syracuse (exercice 3) et les boucles imbriquées avec break (exercice 11), les fonctions, la portée des variables et le piège de l'argument par défaut mutable (exercice 4), les listes et les chaînes de caractères (exercices 5 et 9), les tableaux à deux dimensions (exercice 8) et les conversions de types d'une saisie (exercice 12). Les problèmes font programmer un palindrome et le chiffre de César (exercice 9), l'année bissextile et ses tests (exercice 13), la clé de Luhn des cartes bancaires (exercice 14) et le gagnant d'une grille de morpion (exercice 15).
Un conseil de méthode avant de commencer : ne lisez pas le code, exécutez-le à la main. Prenez une feuille, faites un tableau avec une colonne par variable, et remplissez une ligne par tour de boucle. C'est exactement ce que l'épreuve attend quand elle demande « que renvoie cette fonction », et c'est la seule façon de trouver un bug sans machine. La partie B est entièrement construite là-dessus : lire du code faux, le corriger, et écrire avec assert le jeu de tests qui l'aurait détecté (exercices 6 et 7), jusqu'au maximum initialisé à 0 qui échoue sur une liste de nombres négatifs et à la grille [[0] * p] * n dont les lignes sont partagées (exercice 8).
La partie D traite deux capacités du programme de Première que les parties précédentes n'abordaient qu'en passant : spécifier une fonction par ses préconditions ET ses postconditions, écrites en assertions (exercice 16), et utiliser la documentation d'une bibliothèque, randint, randrange et floor (exercice 17). Les tranches, que la série utilise çà et là, sont signalées : le programme les déclare non exigibles, et chaque exercice concerné dit comment écrire la même chose avec une boucle sur les indices.
Série autocorrigéeTape tes réponses et vérifie-les question par question : la page te dit juste ou faux avant d'ouvrir la correction. Avec un compte, chaque bonne réponse du premier coup rapporte des points, et tes réponses justes restent remplies quand tu reviens.
•Division : a//b est le quotient entier (arrondi vers le bas, y compris pour les négatifs) et a%b le reste ; a/b renvoie toujours un flottant.
•Flottants : ne jamais tester l'égalité de deux flottants avec ==. On compare avec une tolérance : abs(a - b) < 1e-9.
•Booléens : lois de De Morgan, non(a et b) = (non a) ou (non b). Python évalue « et » et « ou » en court-circuit, de gauche à droite.
•Boucle for i in range(a, b, p) : i part de a, avance de p, et s'arrête AVANT b. range(n) donne 0, 1, ..., n-1.
•Terminaison d'une boucle while : exhiber un variant, une quantité entière positive qui décroît strictement à chaque tour.
•Tranches, non exigibles en Première : t[i:j] contient les indices i à j-1, t[::-1] renverse, t[:] copie. Au programme, on écrit la boucle sur les indices, [t[k] for k in range(i, j)], et l'on copie par list(t).
•Tableau à deux dimensions : t[i][j] désigne la ligne i, colonne j. len(t) est le nombre de lignes, len(t[0]) le nombre de colonnes.
•Spécification : la PRÉCONDITION porte sur les arguments et se vérifie à l'entrée, assert n >= 0 ; la POSTCONDITION porte sur le résultat et se vérifie juste avant le return. Le succès d'un jeu de tests ne garantit pas la correction.
•Documentation : lire les paramètres et leurs valeurs par défaut, les bornes incluses ou exclues, la valeur renvoyée et les exceptions. randint(a, b) inclut b ; randrange(a, b) suit range et l'exclut.
Partie A : Les bases (/50)
Exercice 1 : Types, opérateurs et résultats surprenants
Toutes les questions demandent la valeur ET le type du résultat. Répondez sans machine : l'épreuve se passe sans interpréteur, et savoir prévoir ce que Python va faire est précisément la compétence évaluée.
a) Donnez la valeur et le type de : 7 // 2, 7 / 2, 7 % 2, 2 ** 10.
b) Donnez la valeur de -7 // 2 et de -7 % 2. Le résultat de la division entière vous surprend-il ? Expliquez la règle utilisée par Python.
c) Que vaut 0.1 + 0.2 ? L'expression 0.1 + 0.2 == 0.3 est-elle vraie ? Justifiez, puis proposez la bonne façon de comparer deux flottants.
d) Donnez la valeur de : '3' + '4', '3' * 4, int(3.9), int(-3.9).
e) Que valent round(2.5), round(3.5) et round(0.5) ? Formulez la règle d'arrondi réellement appliquée par Python.
Voir la correction
Réponses
a)3, 3.5 (float), 1, 1024
b)-4 et 1 : arrondi vers moins l'infini
c)0.30000000000000004 : comparer avec une tolérance
d)'34', '3333', 3, -3
e)2, 4, 0 : arrondi au pair
a)
7 // 2 vaut 3 (int) : c'est le quotient entier. 7 / 2 vaut 3.5 (float) : l'opérateur / renvoie TOUJOURS un flottant, même quand la division tombe juste. 7 % 2 vaut 1 (int), le reste. 2 ** 10 vaut 1024 (int).
b)
-7 // 2 vaut -4, et non -3. Python arrondit le quotient vers le bas (vers moins l'infini), pas vers zéro. Et -7 % 2 vaut 1, un reste positif. Les deux sont cohérents : la relation a=b×(a//b)+(a%b) doit rester vraie, et en effet −7=2×(−4)+1. En Python, le reste a toujours le signe du diviseur.
c)
0.1 + 0.2 vaut 0.30000000000000004, donc l'expression est FAUSSE. En binaire, 0,1 et 0,2 n'ont pas d'écriture finie, exactement comme 1/3 n'en a pas en base 10 : la machine en stocke une approximation, et les erreurs s'additionnent. On ne teste donc jamais l'égalité de deux flottants ; on écrit abs(a - b) < 1e-9, ou l'on travaille avec des entiers quand c'est possible (des centimes plutôt que des euros).
d)
'3' + '4' vaut '34' : entre deux chaînes, + est la concaténation. '3' * 4 vaut '3333' : chaîne fois entier, c'est la répétition. int(3.9) vaut 3 et int(-3.9) vaut -3 : int() tronque vers zéro, elle n'arrondit pas (attention, ce n'est donc PAS la même chose que //).
e)
round(2.5) vaut 2, round(3.5) vaut 4 et round(0.5) vaut 0. La règle n'est pas « 0,5 s'arrondit au-dessus » mais l'arrondi au pair le plus proche : en cas d'égalité parfaite, Python choisit l'entier pair. Ce choix évite le biais systématique vers le haut quand on arrondit de longues séries de valeurs.
Coche ici les exercices faits ou à revoir : un compte gratuit, sans mot de passe, retient tes coches et tes réponses justes d'une visite à l'autre, te dit quel chapitre attaquer ensuite et te permet de demander l'exercice qui te manque. Crée ton espace, un courriel suffit.
Exercice 2 : Expressions booléennes, De Morgan et court-circuit
Une condition mal écrite est la première cause de bug en NSI. Ces questions portent sur l'équivalence logique et sur l'ordre d'évaluation.
Python
def acces(age, abonne, invite):
if age >= 18:
if abonne == True:
return True
else:
if invite == True:
return True
else:
return False
else:
return False
a) Dressez la table de vérité de non(a et b) et de (non a) ou (non b) pour les quatre couples possibles. Que constatez-vous ?
b) Réécrivez la fonction acces ci-dessus en UNE seule instruction return, sans aucun if.
c) On veut tester qu'un nombre x est non nul et que 10/x dépasse 2. Entre x != 0 and 10 / x > 2 et 10 / x > 2 and x != 0, une seule des deux écritures est correcte. Laquelle, et pourquoi l'autre plante-t-elle ?
d) Traduisez en Python : « x est compris entre 0 et 10 inclus ». Donnez la version courte propre à Python.
e) Simplifiez : if n % 2 == 0: return True else: return False.
Voir la correction
Réponses
a)De Morgan : non(a et b) = non a ou non b
b)return age >= 18 and (abonne or invite)
c)x != 0 d'abord : court-circuit
d)0 <= x <= 10
e)return n % 2 == 0
a)
Pour (a, b) valant (F,F), (F,V), (V,F), (V,V), les deux expressions valent respectivement V, V, V, F. Elles coïncident dans les quatre cas : c'est la loi de De Morgan, non(a et b) = (non a) ou (non b). L'autre loi, symétrique, est non(a ou b) = (non a) et (non b).
b)
Le corps entier revient à demander : l'utilisateur est majeur ET (abonné OU invité). D'où la version en une ligne : return age >= 18 and (abonne or invite). Deux remarques de style : les parenthèses sont indispensables car « and » est prioritaire sur « or », et on n'écrit jamais abonne == True mais simplement abonne, qui est déjà un booléen.
c)
Seule x != 0 and 10 / x > 2 est correcte. Python évalue « and » en court-circuit et de gauche à droite : si x vaut 0, le premier facteur est faux, la deuxième condition n'est jamais évaluée et la division par zéro n'a pas lieu. Dans l'autre ordre, 10 / x est calculée en premier et lève une ZeroDivisionError pour x = 0. Le court-circuit n'est donc pas une optimisation, c'est un outil de protection.
d)
On peut écrire x >= 0 and x <= 10, mais Python autorise les comparaisons chaînées : 0 <= x <= 10, qui se lit comme en mathématiques et n'évalue x qu'une fois.
e)
return n % 2 == 0. La comparaison produit déjà un booléen : le if ne fait que le recopier. Écrire if cond: return True else: return False est toujours un signe qu'on peut renvoyer directement la condition.
Exercice 3 : Boucles, trace d'exécution et terminaison
La suite de Syracuse part d'un entier n strictement positif et applique la règle suivante : si n est pair on le divise par 2, sinon on le remplace par 3n + 1, jusqu'à atteindre 1.
Python
def syracuse(n):
etapes = 0
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
etapes += 1
return etapes
a) Faites la trace complète de syracuse(6) : donnez la suite des valeurs prises par n, puis la valeur renvoyée.
b) Même travail pour n = 7. Donnez le nombre d'étapes et la plus grande valeur atteinte par n en cours de route.
c) Combien de tours effectue la boucle for i in range(3, 20, 4) ? Donnez les valeurs prises par i.
d) Pour prouver qu'une boucle while se termine, on exhibe un variant. Expliquez pourquoi la terminaison de syracuse est un cas très particulier, et ce qu'on sait réellement à son sujet.
e) Écrivez une fonction altitude(n) qui renvoie la plus grande valeur atteinte par la suite partant de n.
Voir la correction
Réponses
a)6, 3, 10, 5, 16, 8, 4, 2, 1 : 8 étapes
b)16 étapes, maximum 52
c)3, 7, 11, 15, 19 : 5 tours
d)Aucun variant connu : conjecture
e)Mémoriser le maximum
a)
La suite est 6, 3, 10, 5, 16, 8, 4, 2, 1. Chaque flèche est un tour de boucle, donc etapes vaut 8. Détail : 6 est pair donc 3 ; 3 est impair donc 10 ; 10 pair donc 5 ; 5 impair donc 16 ; puis 8, 4, 2, 1 par divisions successives.
b)
Pour n = 7 : 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Cela fait 16 étapes, et la plus grande valeur atteinte est 52. Noter que la suite monte largement au-dessus de son point de départ avant de retomber : c'est ce qui rend la terminaison non évidente.
c)
i prend les valeurs 3, 7, 11, 15, 19, puis 23 dépasserait 20 et la boucle s'arrête : 5 tours. La borne de range est toujours exclue.
d)
Un variant est une quantité entière positive qui décroît strictement à chaque tour, ce qui garantit l'arrêt. Ici, aucun variant n'est connu : n n'a aucune raison de décroître, il triple presque quand il est impair. La conjecture de Syracuse affirme que la suite atteint 1 pour tout entier de départ, mais elle n'est PAS démontrée, malgré une vérification par ordinateur jusqu'à des valeurs colossales. C'est donc un programme dont personne ne sait prouver qu'il termine toujours, tout en étant certain qu'il termine pour tous les cas testés.
e)
Il suffit de mémoriser le maximum au fil du parcours.
Python
def altitude(n):
maxi = n
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3 * n + 1
if n > maxi:
maxi = n
return maxi
# altitude(7) vaut 52
Exercice 4 : Fonctions, portée et le piège de l'argument par défaut
Le code ci-dessous compile et s'exécute sans erreur, mais son comportement surprend presque tout le monde la première fois.
Python
def ajouter(x, liste=[]):
liste.append(x)
return liste
print(ajouter(1))
print(ajouter(2))
print(ajouter(3))
a) Qu'affiche ce programme ? Donnez les trois lignes exactement.
b) Expliquez le mécanisme responsable de ce comportement.
c) Corrigez la fonction pour que chaque appel sans deuxième argument reparte d'une liste vide.
d) Quelle est la différence entre une fonction qui RENVOIE une valeur et une fonction qui MODIFIE son argument ? Illustrez avec deux versions d'une fonction qui double tous les éléments d'une liste.
e) Que vaut la variable n après l'exécution du code suivant ? n = 5 ; def f(): n = 10 ; f() ; print(n).
Voir la correction
Réponses
a)[1], [1, 2], [1, 2, 3]
b)Défaut évalué une seule fois
c)None puis liste créée dans le corps
d)Renvoyer ou modifier, jamais les deux
e)n vaut 5 : variable locale
a)
L'affichage est [1], puis [1, 2], puis [1, 2, 3].
b)
La valeur par défaut est évaluée UNE SEULE FOIS, au moment où Python lit la définition de la fonction, pas à chaque appel. Il existe donc une unique liste, créée une fois pour toutes et attachée à la fonction ; chaque appel sans deuxième argument travaille sur cette même liste, qui garde les ajouts précédents. La règle à retenir : on ne met jamais d'objet mutable (liste, dictionnaire) comme valeur par défaut.
c)
On utilise None comme sentinelle et on crée la liste à l'intérieur du corps, donc à chaque appel.
d)
Une fonction qui renvoie une valeur laisse son argument intact et produit un nouvel objet : on l'utilise avec t2 = double(t). Une fonction qui modifie son argument agit par effet de bord, ne renvoie rien (None), et s'utilise avec double_sur_place(t) sur une ligne seule. Le bug classique consiste à écrire t = double_sur_place(t), ce qui écrase t avec None. Il faut choisir l'un des deux styles et le documenter, jamais les deux à la fois.
e)
n vaut 5. L'affectation n = 10 à l'intérieur de f crée une variable LOCALE qui porte le même nom et disparaît à la fin de l'appel ; elle ne touche pas la variable globale. Pour modifier la globale il faudrait déclarer global n, ce qu'on évite en pratique.
Python
def ajouter(x, liste=None):
if liste is None:
liste = []
liste.append(x)
return liste
def double(t): # renvoie une nouvelle liste
return [2 * x for x in t]
def double_sur_place(t): # modifie t, ne renvoie rien
for i in range(len(t)):
t[i] = 2 * t[i]
Exercice 5 : Listes, tranches et chaînes de caractères
On pose t = [0, 1, 2, 3, 4, 5] et m = 'informatique'. Répondez sans machine, en donnant à chaque fois le résultat exact.
Les tranches des questions a), b), c) et e) ne sont pas exigibles : le programme de Première précise qu'« aucune connaissance des tranches (slices) n'est exigible ». Au programme, on extrait une partie d'un tableau par une boucle ou une compréhension sur les indices, [t[k] for k in range(1, 4)] à la place de t[1:4], et l'on copie un tableau par list(t) ou [x for x in t] à la place de t[:]. L'accès par indice, len et la construction en compréhension de la question d) sont, eux, au programme. La figure ci-dessous représente t et m case par case.
a) Donnez la valeur de t[1:4], t[::2], t[::-1] et t[-2:].
b) Que valent t[:0] et t[2:2] ? Que se passe-t-il si l'on écrit t[10] ? Et t[2:10] ?
c) Donnez la valeur de m[0], m[-1], m[0:5], m[::-1] et len(m).
d) Écrivez une expression qui construit la liste des carrés des entiers de 1 à 10, d'abord avec une boucle, puis en compréhension.
e) Quelle est la différence entre t2 = t et t2 = t[:] ? Illustrez par un exemple où le choix change le résultat.
Voir la correction
Réponses
a)[1, 2, 3], [0, 2, 4], [5, …, 0], [4, 5]
b)Tranche tolérante, indice non
c)'i', 'e', 'infor', 12 caractères
d)[i * i for i in range(1, 11)]
e)t2 = t : même objet ; t[:] : copie
a)
t[1:4] vaut [1, 2, 3] : les indices 1, 2 et 3, la borne de droite étant exclue. t[::2] vaut [0, 2, 4] : un élément sur deux. t[::-1] vaut [5, 4, 3, 2, 1, 0] : la liste renversée. t[-2:] vaut [4, 5] : les deux derniers, l'indice -1 désignant le dernier élément.
b)
t[:0] et t[2:2] valent tous deux [] : une tranche vide n'est pas une erreur. En revanche t[10] lève une IndexError, car l'indexation d'un élément hors bornes est interdite. Mais t[2:10] vaut [2, 3, 4, 5] sans erreur : les TRANCHES sont tolérantes et se contentent de s'arrêter à la fin de la liste. C'est une asymétrie que l'épreuve aime tester.
c)
m[0] vaut 'i', m[-1] vaut 'e', m[0:5] vaut 'infor', m[::-1] vaut 'euqitamrofni' et len(m) vaut 12. Une chaîne s'indexe et se tranche exactement comme une liste, à une différence près : elle est immuable, donc m[0] = 'I' est interdit.
d)
Par boucle : créer une liste vide puis ajouter les carrés un par un. En compréhension, tout tient sur une ligne. Les deux produisent [1, 4, 9, 16, 25, 36, 49, 64, 81, 100].
e)
t2 = t ne copie rien : les deux noms désignent le MÊME objet, donc modifier t2[0] change aussi t[0]. t2 = t[:] crée une vraie copie (superficielle) : les deux listes sont indépendantes. Exemple : après t = [1, 2, 3] et t2 = t, l'instruction t2[0] = 99 donne t = [99, 2, 3]. Avec t2 = t[:], t reste [1, 2, 3].
Python
carres = []
for i in range(1, 11):
carres.append(i * i)
carres = [i * i for i in range(1, 11)]
# [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
Partie B : Niveau examen (/50)
Exercice 6 : Lire du code faux : trouver le bug et le prouver
Les deux fonctions ci-dessous sont censées calculer la moyenne d'une liste de notes et compter combien dépassent cette moyenne. Elles s'exécutent sans message d'erreur, et pourtant les deux donnent un résultat faux. On teste avec notes = [12, 15, 9, 18].
Python
def moyenne(t):
s = 0
for i in range(1, len(t)):
s = s + t[i]
return s / len(t)
def au_dessus(t):
n = 0
for x in t:
if x > moyenne(t):
n = n + 1
return n
notes = [12, 15, 9, 18]
a) Calculez à la main la valeur correcte de la moyenne de notes.
b) Que renvoie réellement moyenne(notes) ? Identifiez précisément le bug et corrigez-le.
c) Une fois moyenne corrigée, que renvoie au_dessus(notes) ? Ce résultat est-il correct ?
d) La fonction au_dessus contient un défaut qui n'est pas un bug de résultat mais un défaut de conception. Lequel, et comment le corriger ?
e) Proposez un jeu de trois tests, écrits avec assert, qui aurait détecté le bug de la question b. Justifiez le choix de chaque test.
Voir la correction
Réponses
a)Moyenne 13,5
b)10,5 : range(1, …) saute t[0]
c)2, correct
d)Calculer la moyenne une fois
e)Tester la liste à un élément
a)
La somme vaut 12 + 15 + 9 + 18 = 54, et il y a 4 notes : la moyenne correcte est 54 / 4 = 13,5.
b)
La fonction renvoie 10,5. Le bug est dans range(1, len(t)) : la boucle démarre à l'indice 1 et saute donc le premier élément. Elle additionne 15 + 9 + 18 = 42, puis divise par 4, d'où 10,5. La correction est d'écrire range(len(t)), ou mieux, de parcourir directement les valeurs avec for x in t, ce qui rend l'erreur d'indice impossible.
c)
Avec la moyenne corrigée à 13,5, les notes strictement supérieures sont 15 et 18 : au_dessus renvoie 2, ce qui est correct.
d)
Le défaut est que moyenne(t) est recalculée à CHAQUE tour de boucle, alors qu'elle ne change jamais. Sur une liste de n notes, on fait n calculs de moyenne coûtant chacun n additions, soit un travail proportionnel à n2 au lieu de n. La correction est de calculer la moyenne une seule fois avant la boucle et de la stocker dans une variable. C'est un réflexe attendu à l'examen : sortir de la boucle tout calcul qui n'en dépend pas.
e)
Trois tests qui couvrent des cas différents : une liste à un seul élément, où la moyenne doit valoir cet élément (ce test échoue immédiatement avec le bug, car la boucle ne fait aucun tour et renvoie 0) ; une liste de valeurs toutes égales, où la moyenne doit valoir cette valeur commune ; et un cas connu calculé à la main. Le premier est le plus utile : les bugs d'indice se révèlent presque toujours sur les cas de taille 0 ou 1, jamais sur les cas moyens.
Python
def moyenne(t):
s = 0
for x in t: # plus d'indice, plus de bug possible
s = s + x
return s / len(t)
def au_dessus(t):
m = moyenne(t) # calculee UNE fois
n = 0
for x in t:
if x > m:
n = n + 1
return n
assert moyenne([7]) == 7
assert moyenne([5, 5, 5]) == 5
assert moyenne([12, 15, 9, 18]) == 13.5
Exercice 7 : Spécifier, tester, et le cas limite qu'on oublie toujours
On veut écrire une fonction indice_max(t) qui renvoie l'INDICE du plus grand élément d'une liste de nombres. Avant d'écrire une seule ligne, on spécifie.
a) Écrivez la spécification complète : ce que la fonction prend en entrée, ce qu'elle renvoie, et la précondition sur t.
b) Que doit renvoyer la fonction si le maximum apparaît plusieurs fois ? Complétez la spécification pour lever cette ambiguïté.
c) Écrivez la fonction. Elle ne doit parcourir la liste qu'une seule fois.
d) Un camarade initialise son maximum avec m = 0 au lieu de m = t[0]. Sur quel type de liste sa version échoue-t-elle ? Donnez un contre-exemple précis avec le résultat attendu et le résultat obtenu.
e) Écrivez un jeu de tests avec assert couvrant : le cas général, la liste à un élément, les valeurs négatives, et le maximum en double.
Voir la correction
Réponses
a)Précondition : t non vide
b)Premier indice du maximum
c)Inégalité stricte, un seul parcours
d)m = 0 : faux sur les négatifs
e)Général, un élément, négatifs, doublon
a)
Entrée : une liste t de nombres. Sortie : un entier i tel que t[i] soit supérieur ou égal à tous les éléments de t. Précondition : t doit être non vide. Sur une liste vide, il n'existe aucun indice à renvoyer ; on choisit d'exiger la précondition plutôt que d'inventer une valeur de retour, et on peut la matérialiser dans le code par assert len(t) > 0.
b)
La spécification doit trancher : on convient de renvoyer le PREMIER indice où le maximum est atteint. Sans cette précision, deux implémentations correctes peuvent donner des réponses différentes sur [3, 9, 9], et un test automatique deviendrait arbitraire. Une spécification qui laisse une ambiguïté est une spécification incomplète.
c)
On mémorise l'indice du meilleur élément vu jusqu'ici, et on ne le remplace que sur une inégalité STRICTE, ce qui garantit qu'on conserve la première occurrence.
d)
Sa version échoue sur toute liste dont tous les éléments sont strictement négatifs. Sur t = [-5, -2, -9], aucun élément ne dépasse 0 : la condition x > m n'est jamais vraie, l'indice n'est jamais mis à jour et la fonction renvoie 0, donc l'indice de -5. Le résultat attendu est 1, l'indice de -2. La leçon générale : on initialise un maximum avec un élément de la liste, jamais avec une constante choisie arbitrairement.
e)
Le jeu de tests figure dans le corrigé ci-dessous. Chaque test vise un risque identifié : le cas général vérifie la logique, la liste à un élément vérifie les bornes de la boucle, les négatifs attrapent le bug d'initialisation de la question d, et le doublon vérifie la convention fixée en b.
Python
def indice_max(t):
"""Plus petit indice du maximum. Precondition : t non vide."""
assert len(t) > 0, 't ne doit pas etre vide'
imax = 0
for i in range(1, len(t)):
if t[i] > t[imax]: # strict : on garde la 1re occurrence
imax = i
return imax
assert indice_max([3, 9, 2]) == 1 # cas general
assert indice_max([7]) == 0 # un seul element
assert indice_max([-5, -2, -9]) == 1 # que des negatifs
assert indice_max([3, 9, 9]) == 1 # maximum en double
Exercice 8 : Tableaux à deux dimensions
On représente une grille de nombres par une liste de listes. On travaille sur la grille suivante, à 3 lignes et 3 colonnes : grille = [[3, 8, 1], [4, 2, 9], [7, 5, 6]]. La figure redonne cette grille avec ses indices de ligne et de colonne.
a) Que vaut grille[1][2] ? Et grille[2][0] ? Donnez l'expression qui vaut 8.
b) Écrivez une fonction somme_grille(g) qui renvoie la somme de tous les éléments. Donnez le résultat sur la grille ci-dessus.
c) Écrivez une fonction somme_colonne(g, j) qui renvoie la somme de la colonne j. Donnez la somme de la colonne 0.
d) Écrivez une fonction transposee(g) qui renvoie la grille transposée (les lignes deviennent les colonnes). Donnez le résultat sur la grille ci-dessus.
e) On veut créer une grille de n lignes et p colonnes remplie de zéros. Expliquez pourquoi g = [[0] * p] * n est un piège, et donnez la bonne écriture.
Voir la correction
Réponses
a)9 et 7 ; 8 est grille[0][1]
b)Somme 45
c)Colonne 0 : 14
d)[[3, 4, 7], [8, 2, 5], [1, 9, 6]]
e)[[0] * p for _ in range(n)]
a)
grille[1][2] vaut 9 : ligne d'indice 1 (la deuxième), colonne d'indice 2 (la troisième). grille[2][0] vaut 7. La valeur 8 s'obtient par grille[0][1]. L'ordre est toujours [ligne][colonne].
b)
On parcourt chaque ligne, puis chaque élément de la ligne. La somme vaut 3+8+1+4+2+9+7+5+6 = 45.
c)
On fixe la colonne et on fait varier l'indice de ligne. La colonne 0 contient 3, 4 et 7 : sa somme vaut 14.
d)
La transposée est [[3, 4, 7], [8, 2, 5], [1, 9, 6]] : l'élément de la ligne i colonne j vient de la ligne j colonne i.
e)
[0] * p crée bien une ligne de p zéros, mais la multiplication suivante par n ne duplique pas cette ligne : elle recopie n fois la MÊME référence. Les n lignes sont donc un seul et même objet, et g[0][0] = 1 met un 1 en tête de toutes les lignes à la fois. La bonne écriture crée une ligne neuve à chaque tour, par exemple en compréhension : [[0] * p for _ in range(n)]. C'est exactement le même piège que l'argument par défaut mutable de l'exercice 4 : en Python, dupliquer une référence n'est pas dupliquer l'objet.
Python
def somme_grille(g):
s = 0
for ligne in g:
for x in ligne:
s = s + x
return s # 45
def somme_colonne(g, j):
return sum(g[i][j] for i in range(len(g))) # colonne 0 -> 14
def transposee(g):
n, p = len(g), len(g[0])
return [[g[i][j] for i in range(n)] for j in range(p)]
g = [[0] * p for _ in range(n)] # correct
# g = [[0] * p] * n # PIEGE : n fois la meme ligne
Exercice 9 : Traitement de chaînes : palindromes et chiffre de César
Les chaînes de caractères se parcourent comme des listes, mais elles sont immuables : on ne peut pas modifier un caractère en place, on construit une nouvelle chaîne. On note alpha = 'abcdefghijklmnopqrstuvwxyz'.
La tranche m[::-1] du corrigé de la question a) n'est pas exigible en Première ; la version de la question b), qui compare les caractères deux à deux avec une boucle sur les indices, est celle que le programme attend. La figure ci-dessous donne la position de chaque lettre dans alpha.
a) Écrivez une fonction est_palindrome(m) qui dit si m se lit pareil dans les deux sens. Testez sur 'radar', 'kayak', 'python' et 'ressasser'.
b) Écrivez la même fonction SANS utiliser de tranche, avec une boucle qui compare les caractères deux à deux depuis les extrémités. Combien de tours fait votre boucle sur un mot de n lettres ?
c) Le chiffre de César décale chaque lettre de k positions dans l'alphabet, en revenant au début après z. Écrivez cesar(m, k) pour un mot en minuscules sans accent. Que donne cesar('bonjour', 3) ?
d) Que donne cesar('xyz', 3) ? Quelle opération assure le retour au début de l'alphabet ?
e) Comment déchiffre-t-on un message chiffré avec la clé k ? Vérifiez sur votre réponse de la question c.
Voir la correction
Réponses
a)m == m[::-1]
b)Au plus n // 2 tours
c)'erqmrxu'
d)'abc' grâce au modulo 26
e)cesar(message, -k)
a)
Il suffit de comparer le mot à son renversé : return m == m[::-1]. Résultats : 'radar' vrai, 'kayak' vrai, 'python' faux, 'ressasser' vrai.
b)
On avance deux indices l'un vers l'autre depuis les deux bouts, et on s'arrête dès qu'ils se croisent ou qu'une paire diffère. La boucle fait au plus n // 2 tours : une fois arrivé au milieu, toutes les paires ont été vérifiées, continuer reviendrait à recomparer les mêmes lettres. Cette version est préférable sur de longs textes, car la version avec tranche construit une copie complète du mot en mémoire.
c)
On repère la position de chaque lettre dans alpha, on ajoute k, on prend le reste modulo 26 et on relit la lettre correspondante. cesar('bonjour', 3) donne 'erqmrxu'.
d)
cesar('xyz', 3) donne 'abc'. C'est le modulo 26 qui assure le rebouclage : la position de 'x' est 23, plus 3 donne 26, et 26 % 26 vaut 0, soit la position de 'a'. Sans ce modulo, l'indice sortirait de l'alphabet et provoquerait une IndexError.
e)
Déchiffrer, c'est chiffrer avec la clé opposée : cesar(message, -k). Le modulo gère aussi les valeurs négatives en Python, puisque le reste y est toujours positif. On vérifie : cesar('erqmrxu', -3) redonne bien 'bonjour'.
Python
alpha = 'abcdefghijklmnopqrstuvwxyz'
def est_palindrome(m):
return m == m[::-1]
def est_palindrome2(m):
i, j = 0, len(m) - 1
while i < j:
if m[i] != m[j]:
return False
i, j = i + 1, j - 1
return True
def cesar(m, k):
r = ''
for c in m:
r = r + alpha[(alpha.index(c) + k) % 26]
return r
# cesar('bonjour', 3) -> 'erqmrxu' ; cesar('erqmrxu', -3) -> 'bonjour'
Exercice 10 : Problème : analyser un relevé de températures
Une station météo enregistre une température par jour. On travaille sur une semaine : temps = [12, 15, 14, 19, 22, 21, 17]. Toutes les fonctions demandées prennent la liste en argument et doivent fonctionner quelle que soit sa longueur, du moment qu'elle est non vide. Le graphique ci-dessous représente ce relevé.
a) Écrivez amplitude(t) qui renvoie l'écart entre la température maximale et la minimale. Donnez le résultat.
b) Écrivez jours_au_dessus(t) qui renvoie la LISTE DES INDICES des jours dont la température dépasse strictement la moyenne. Donnez le résultat.
c) Écrivez plus_forte_hausse(t) qui renvoie la plus grande hausse observée d'un jour au suivant, et l'indice du jour où elle commence.
d) Écrivez plus_longue_hausse(t) qui renvoie la longueur de la plus longue suite de jours consécutifs où la température augmente strictement. Donnez le résultat.
e) Pourquoi la question d ne peut-elle pas se traiter par une simple compréhension de liste, alors que les questions b et c le peuvent ?
La moyenne vaut 712+15+14+19+22+21+17=7120≈17,14. Les températures qui la dépassent strictement sont 19, 22 et 21, aux indices 3, 4 et 5. La fonction renvoie donc [3, 4, 5]. Attention à calculer la moyenne UNE fois avant la compréhension, pas à l'intérieur.
c)
Les écarts d'un jour au suivant sont [3, -1, 5, 3, -1, -4]. La plus forte hausse vaut 5, et elle commence à l'indice 2 (du jour 2 au jour 3, de 14 à 19).
d)
Les suites strictement croissantes sont 12, 15 (longueur 2), puis 14, 19, 22 (longueur 3), puis 17 seul. La plus longue a donc une longueur de 3.
e)
Parce que la question d demande de retenir une information ENTRE les tours : la longueur de la série en cours, qu'il faut remettre à 1 dès que la croissance s'interrompt, tout en conservant le meilleur score vu jusque-là. Une compréhension de liste ne peut pas porter cet état accumulé, elle calcule chaque terme indépendamment des autres. Les questions b et c s'y prêtent au contraire parce que chaque terme s'y calcule à partir des seules données locales, sans mémoire. C'est le critère à retenir : dès qu'il faut un accumulateur qui dépend de l'historique, il faut une vraie boucle.
Python
def amplitude(t):
return max(t) - min(t) # 10
def jours_au_dessus(t):
m = sum(t) / len(t) # calculee UNE fois
return [i for i in range(len(t)) if t[i] > m] # [3, 4, 5]
def plus_forte_hausse(t):
ecarts = [t[i + 1] - t[i] for i in range(len(t) - 1)]
h = max(ecarts)
return h, ecarts.index(h) # (5, 2)
def plus_longue_hausse(t):
best = courant = 1
for i in range(1, len(t)):
courant = courant + 1 if t[i] > t[i - 1] else 1
if courant > best:
best = courant
return best # 3
Partie C : les classiques (/50)
Exercice 11 : Boucles imbriquées : compter avant d'exécuter
On veut prévoir, sans machine, combien de fois s'exécute une instruction placée dans des boucles. Les trois programmes ci-dessous sont indépendants.
Python
# Programme 1
c = 0
for i in range(4):
for j in range(i):
c = c + 1
print(c)
# Programme 2
for i in range(1, 4):
for j in range(1, 4):
if j == i:
break
print(i, j)
# Programme 3
n = 0
s = 0
while s < 50:
n = n + 1
s = s + n
a) Programme 1 : quelle valeur est affichée ?
b) On remplace range(4) par range(n) dans le programme 1. Exprimez la valeur affichée en fonction de n, puis calculez-la pour n = 100.
c) Programme 2 : écrivez les lignes affichées, dans l'ordre. L'instruction break arrête-t-elle les deux boucles ?
d) Programme 3 : quelles sont les valeurs de n et de s à la sortie de la boucle ?
e) Un élève veut calculer la somme des entiers de 1 à 10 et écrit sum(range(1, 10)). Quelle valeur obtient-il, et comment corriger ?
Voir la correction
Réponses
a)0+1+2+3=6
b)n(n−1)/2 : 4 950
c)2 1, 3 1, 3 2 : break sort d'une boucle
d)n = 10, s = 55
e)45 : écrire range(1, 11)
a)
Pour i = 0, la boucle intérieure range(0) ne fait aucun tour ; pour i = 1, un tour ; pour i = 2, deux tours ; pour i = 3, trois tours. Le compteur vaut donc 0 + 1 + 2 + 3 = 6, et le programme affiche 6.
b)
La boucle intérieure fait i tours pour chaque i de 0 à n - 1 : le total vaut 0+1+⋯+(n−1)=2n(n−1). Pour n = 100 : 2100×99=4950. Le nombre de tours croît comme n2 : c'est la signature de deux boucles imbriquées dont les bornes dépendent de n.
c)
Pour i = 1, la boucle intérieure commence avec j = 1 : j == i, donc break immédiat, rien n'est affiché. Pour i = 2 : j = 1 est affiché, puis j = 2 déclenche break. Pour i = 3 : j = 1 et j = 2 sont affichés, puis break. Les lignes sont donc 2 1, puis 3 1, puis 3 2, soit trois lignes. L'instruction break ne sort QUE de la boucle la plus intérieure qui la contient : la boucle sur i continue normalement.
d)
La boucle ajoute 1, puis 2, puis 3 et ainsi de suite tant que s < 50. Après n = 9, s vaut 45, encore inférieur à 50, donc un tour de plus : n = 10 et s = 55. La condition est testée AVANT chaque tour : la boucle s'arrête avec s = 55, qui dépasse 50. Le piège est de répondre n = 9, la dernière valeur pour laquelle s reste sous 50.
e)
range(1, 10) s'arrête à 9, la borne de droite étant exclue : il obtient 45 au lieu de 55. On corrige en écrivant sum(range(1, 11)), et plus généralement range(1, n + 1) pour aller de 1 à n.
Exercice 12 : Conversions de types et chaînes saisies
La fonction input renvoie TOUJOURS une chaîne de caractères, même quand l'utilisateur tape un nombre. La plupart des erreurs d'un programme qui dialogue avec l'utilisateur viennent de là. Répondez sans machine, en donnant la valeur ou le nom de l'erreur levée.
a) L'utilisateur tape 16 après age = input('Âge ? '). Quel est le type de age ? Que produit l'instruction age + 1 ?
b) Donnez le résultat de : int('16') + 1, float('3.5'), int('3.5'), int(float('3.5')).
c) Donnez le résultat de : str(12) + '3', int('12') + int('3'), '12' * 2.
d) Que vaut len(str(2 ** 100)) ? Écrivez une expression qui calcule la somme des chiffres de 2 ** 15 et donnez sa valeur.
e) Que valent bool(''), bool('False'), bool(0) et bool([0]) ? Pourquoi le test if reponse: est-il trompeur quand reponse vient d'un input ?
Voir la correction
Réponses
a)str : TypeError
b)17, 3.5, ValueError, 3
c)'123', 15, '1212'
d)31 chiffres ; somme 26
e)Chaîne non vide : toujours vraie
a)
age est de type str : il vaut '16'. L'instruction age + 1 lève une TypeError, car Python refuse d'additionner une chaîne et un entier. Il faut convertir : age = int(input('Âge ? ')).
b)
int('16') + 1 vaut 17. float('3.5') vaut 3.5. int('3.5') lève une ValueError : int accepte une chaîne qui représente un ENTIER, pas un décimal. int(float('3.5')) vaut 3 : on convertit d'abord en flottant, puis on tronque vers zéro.
c)
str(12) + '3' vaut '123' : deux chaînes, donc concaténation. int('12') + int('3') vaut 15 : deux entiers, donc addition. '12' * 2 vaut '1212' : chaîne fois entier, donc répétition. Le même symbole change de sens selon le type de ses opérandes.
d)
2 ** 100 vaut 1267650600228229401496703205376, un entier de 31 chiffres : len(str(2 ** 100)) vaut 31. Les entiers Python n'ont pas de taille maximale. Pour la somme des chiffres, on parcourt la chaîne et on reconvertit chaque caractère : sum(int(c) for c in str(2 ** 15)). Comme 2 ** 15 = 32768, cela vaut 3 + 2 + 7 + 6 + 8 = 26.
e)
bool('') vaut False, bool('False') vaut True, bool(0) vaut False et bool([0]) vaut True. Une chaîne est fausse seulement si elle est VIDE, quel que soit son contenu ; une liste est fausse seulement si elle est vide, même si elle contient 0. Si l'utilisateur tape non, 0 ou False, la chaîne n'est pas vide et if reponse: est vrai : il faut comparer explicitement, par exemple if reponse == 'oui':.
Exercice 13 : L'année bissextile : spécifier et tester
Une année est bissextile si elle est divisible par 4 sans être divisible par 100, ou si elle est divisible par 400. On veut écrire une fonction bissextile(a) qui renvoie un booléen. La figure ci-dessous représente cette règle par des ensembles emboîtés.
a) Sans machine, dites si 2024, 2023, 1900 et 2000 sont bissextiles.
b) Écrivez bissextile(a) avec une seule instruction return. Un camarade écrit return a % 4 == 0 or a % 400 == 0 and a % 100 != 0. Que renvoie sa fonction pour 1900 ?
c) Combien d'années bissextiles compte-t-on de 1901 à 2000 inclus ? De 2001 à 2100 inclus ?
d) Écrivez nb_jours(a1, a2) qui renvoie le nombre de jours du 1er janvier de a1 au 1er janvier de a2. Calculez nb_jours(2000, 2025).
e) On ne peut écrire que quatre tests. Lequel des tests suivants est le plus important pour attraper l'erreur du camarade : 2024, 2023, 1900 ou 2000 ? Justifiez.
Voir la correction
Réponses
a)Oui, non, non, oui
b)Camarade : True pour 1900
c)25 puis 24
d)9 132 jours
e)Tester 1900
a)
2024 est divisible par 4 et pas par 100 : bissextile. 2023 n'est pas divisible par 4 : non. 1900 est divisible par 100 mais pas par 400 : NON, c'est le piège. 2000 est divisible par 400 : bissextile.
b)
return (a % 4 == 0 and a % 100 != 0) or a % 400 == 0. Les parenthèses sont facultatives car and est prioritaire sur or, mais elles rendent la lecture sûre. La version du camarade se lit a % 4 == 0 or (a % 400 == 0 and a % 100 != 0) : pour 1900, le premier terme est vrai, donc elle renvoie True, alors que 1900 n'est pas bissextile. La seconde partie ne peut d'ailleurs jamais être vraie, un multiple de 400 étant toujours multiple de 100.
c)
De 1901 à 2000 : les multiples de 4 sont 1904, 1908, et ainsi de suite jusqu'à 2000, soit 25 années, et 2000 est bien bissextile car multiple de 400 : 25. De 2001 à 2100 : 25 multiples de 4, de 2004 à 2100, mais 2100 est divisible par 100 et pas par 400 : 24.
d)
On parcourt les années de a1 à a2 - 1 et on ajoute 366 ou 365. De 2000 à 2024 inclus, il y a 25 années dont 7 bissextiles, 2000, 2004, 2008, 2012, 2016, 2020 et 2024 : 25×365+7=9132 jours. L'erreur classique est d'aller jusqu'à a2 inclus, ce qui compte une année de trop.
e)
Le test sur 1900. L'erreur du camarade ne se voit que sur une année divisible par 4 ET par 100 mais pas par 400 : 2024, 2023 et 2000 donnent le bon résultat avec sa fonction. Un bon jeu de tests ne vérifie pas des cas au hasard, il vise chaque branche de la règle, et le cas le plus rare est le plus précieux.
Python
def bissextile(a):
return (a % 4 == 0 and a % 100 != 0) or a % 400 == 0
def nb_jours(a1, a2):
total = 0
for a in range(a1, a2): # a2 exclu
if bissextile(a):
total = total + 366
else:
total = total + 365
return total # nb_jours(2000, 2025) -> 9132
assert bissextile(2024)
assert not bissextile(2023)
assert not bissextile(1900)
assert bissextile(2000)
Exercice 14 : Problème : la clé de Luhn
Les numéros de cartes bancaires se terminent par un chiffre de contrôle, calculé par l'algorithme de Luhn. On lit le numéro de DROITE à gauche : les chiffres de rang pair en partant de 0, dont le dernier, sont gardés tels quels ; ceux de rang impair sont doublés, et on retranche 9 à tout résultat supérieur à 9. Le numéro est valide si la somme obtenue est un multiple de 10.
Le numéro est donné sous forme de chaîne de chiffres, sans espace.
La tranche s[::-1] de la question b) n'est pas exigible en Première : on obtient le même parcours de droite à gauche avec une boucle sur les indices, for i in range(len(s) - 1, -1, -1), puis s[i].
a) Appliquez l'algorithme à la main au numéro '12345678903'. Donnez la somme et dites si le numéro est valide.
b) Écrivez luhn_valide(s) qui renvoie True si la chaîne s est un numéro valide. Pourquoi est-il commode de parcourir s[::-1] ?
c) Le numéro '52148937012?' a perdu son dernier chiffre. Quel chiffre le rend valide ?
d) On se trompe sur UN chiffre du numéro de la question a, le 0 devenant 1 : '12345678913'. L'algorithme détecte-t-il l'erreur ? Que vaut la nouvelle somme ?
e) Une faute de frappe fréquente consiste à inverser deux chiffres voisins. L'algorithme la détecte presque toujours, sauf pour une paire précise. Laquelle ?
Voir la correction
Réponses
a)28 + 22 = 50 : valide
b)Rang depuis la droite
c)Chiffre 7
d)52 : erreur détectée
e)09 et 90 non détectés
a)
Lu de droite à gauche : 3, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1. Rangs pairs, gardés : 3, 9, 7, 5, 3, 1, de somme 28. Rangs impairs, doublés : 0 donne 0, 8 donne 16 puis 7, 6 donne 12 puis 3, 4 donne 8, 2 donne 4, de somme 22. Total : 28 + 22 = 50, multiple de 10 : le numéro est VALIDE.
b)
Parcourir s[::-1] avec enumerate, ou avec un indice, donne directement le rang depuis la droite : le dernier chiffre a le rang 0 quelle que soit la longueur du numéro. Sans renversement, la parité du rang dépendrait de la longueur, et un numéro de 15 chiffres ne serait pas traité comme un numéro de 16. Il faut aussi penser à convertir chaque caractère avec int, sinon '8' * 2 donne la chaîne '88'.
c)
On essaie le chiffre manquant de 0 à 9 : il occupe le rang 0, donc il n'est pas doublé et s'ajoute tel quel à la somme des autres. Les onze autres chiffres, décalés d'un rang, donnent une somme de 43. Il faut 43 + k multiple de 10, donc k = 7 : le numéro valide est '521489370127'.
d)
Le 0 est au rang 1, donc doublé : il comptait pour 0, le 1 compte pour 2. La somme passe de 50 à 52, qui n'est pas un multiple de 10 : l'erreur est détectée. Changer un seul chiffre modifie toujours la somme d'une quantité comprise entre 1 et 9, jamais d'un multiple de 10 : toute erreur sur un seul chiffre est détectée.
e)
L'inversion de 0 et 9, dans un sens ou dans l'autre. Si 09 devient 90, le 0 doublé compte 0 et le 9 simple compte 9 avant l'erreur, soit 9 ; après, le 9 doublé donne 18 puis 9 et le 0 simple compte 0, soit encore 9. La somme ne change pas. Pour toutes les autres paires de chiffres différents, la somme change d'un nombre qui n'est pas multiple de 10.
Python
def luhn_valide(s):
total = 0
rang = 0
for c in s[::-1]: # rang 0 = dernier chiffre
d = int(c)
if rang % 2 == 1:
d = 2 * d
if d > 9:
d = d - 9
total = total + d
rang = rang + 1
return total % 10 == 0
assert luhn_valide('12345678903')
assert luhn_valide('521489370127')
assert not luhn_valide('12345678913')
Exercice 15 : Problème : qui a gagné au morpion ?
Une grille de morpion est une liste de trois listes de trois caractères : 'X', 'O' ou '.' pour une case vide. X joue toujours en premier, puis les joueurs alternent. On considère la grille g ci-dessous. La figure ci-dessous représente cette grille.
a) Que valent g[0][2] et g[2][0] ? Combien de cases vides la grille contient-elle ?
b) Combien d'alignements gagnants existe-t-il sur une grille 3 × 3 ? Écrivez les indices des cases de la diagonale qui part de g[0][2].
c) Écrivez gagne(g, j) qui renvoie True si le joueur j possède un alignement. Qui a gagné sur la grille g, et par quel alignement ?
d) Écrivez compter(g, j) qui renvoie le nombre de symboles j. Combien de X et de O la grille contient-elle ? Est-ce cohérent avec le fait que X commence ?
e) Une grille contient 2 X et 4 O. Peut-elle provenir d'une vraie partie ? Et une grille où X et O ont chacun un alignement complet ? Justifiez.
Voir la correction
Réponses
a)'X', 'O', aucune case vide
b)8 alignements ; g[i][2 - i]
c)X gagne par la diagonale principale
d)5 X, 4 O : cohérent
e)Deux grilles impossibles
a)
g[0][2] vaut 'X' : ligne 0, colonne 2. g[2][0] vaut 'O'. La grille ne contient aucune case vide : les neuf cases sont remplies.
b)
Il y a 8 alignements : 3 lignes, 3 colonnes et 2 diagonales. La diagonale qui part de g[0][2] passe par g[1][1] et g[2][0] : ses cases sont g[i][2 - i] pour i = 0, 1, 2. La diagonale principale est formée des cases g[i][i].
c)
On teste les trois lignes, les trois colonnes et les deux diagonales. Sur la grille g, les lignes et les colonnes sont toutes mélangées, et la diagonale secondaire contient X, X et O. La diagonale principale contient g[0][0], g[1][1] et g[2][2], qui valent tous 'X' : X a gagné par la diagonale principale, et O n'a aucun alignement.
d)
On parcourt les lignes puis les cases. La grille contient 5 X et 4 O. Comme X commence et que les joueurs alternent, il y a toujours autant de X que de O, ou un X de plus : 5 et 4 est cohérent, et correspond à une partie terminée par le cinquième coup de X.
e)
Avec 2 X et 4 O, O aurait joué deux fois de plus que X : c'est impossible, l'écart compter(g, 'X') - compter(g, 'O') devant valoir 0 ou 1. Une grille où les deux joueurs ont un alignement est aussi impossible : la partie s'arrête dès le premier alignement, et le joueur suivant ne peut plus en compléter un. Vérifier qu'une grille est cohérente avant de désigner un gagnant, c'est tester les préconditions de la fonction.
Python
def gagne(g, j):
for i in range(3):
if g[i][0] == g[i][1] == g[i][2] == j: # ligne i
return True
if g[0][i] == g[1][i] == g[2][i] == j: # colonne i
return True
if g[0][0] == g[1][1] == g[2][2] == j:
return True
return g[0][2] == g[1][1] == g[2][0] == j
def compter(g, j):
n = 0
for ligne in g:
for case in ligne:
if case == j:
n = n + 1
return n
# gagne(g, 'X') -> True ; compter(g, 'X') -> 5 ; compter(g, 'O') -> 4
Partie D : spécifier et documenter (/20)
Exercice 16 : Préconditions et postconditions : la racine entière sous contrat
On veut une fonction racine_entiere(n) qui renvoie la racine carrée entière de n, c'est-à-dire le plus grand entier r dont le carré ne dépasse pas n. La fonction ci-dessous porte DEUX assertions. Un camarade propose une autre version, racine_camarade, et la valide par un jeu de cinq tests.
Python
def racine_entiere(n):
"""Renvoie le plus grand entier r tel que r * r <= n.
Precondition : n est un entier positif ou nul."""
assert n >= 0, 'n doit etre positif'
r = 0
while (r + 1) * (r + 1) <= n:
r = r + 1
assert r * r <= n < (r + 1) * (r + 1)
return r
def racine_camarade(n):
r = 0
while r * r < n:
r = r + 1
return r
# jeu de tests du camarade
for k in [0, 1, 4, 9, 16]:
assert racine_camarade(k) == racine_entiere(k)
a) Laquelle des deux assertions de racine_entiere est la précondition, laquelle est la postcondition ? Traduisez la postcondition en français, et expliquez pourquoi sa première moitié, r * r <= n, ne suffirait pas.
b) Que renvoient racine_entiere(30), racine_entiere(49) et racine_entiere(0) ? Combien de tours fait la boucle pour n = 30 ?
c) Que se passe-t-il à l'appel racine_entiere(-4) ? Que se passerait-il si l'on supprimait la première assertion, en gardant la seconde ? Et si l'on supprimait les deux ?
d) Le jeu de tests du camarade passe-t-il ? Que renvoie racine_camarade(30) ? Quel cas son jeu de tests aurait-il dû contenir ?
e) On ajoute à racine_camarade la même postcondition, juste avant son return. Que se passe-t-il à l'appel racine_camarade(30) ? Pour combien d'entiers n compris entre 0 et 50 la version du camarade renvoie-t-elle le bon résultat ?
Voir la correction
Réponses
a)La première est la précondition, la seconde la postcondition : r2≤n<(r+1)2, r est le plus grand entier de carré au plus n
b)5, 7 et 0 ; 5 tours pour n = 30
c)AssertionError sur la précondition ; sans elle, AssertionError sur la postcondition ; sans les deux, 0 renvoyé à tort
d)Les tests passent, mais racine_camarade(30) vaut 6 ; il manquait un entier non carré
e)AssertionError dès l'appel ; juste pour 8 valeurs sur 51, les carrés parfaits
a)
La première, assert n >= 0, s'exécute à l'ENTRÉE, avant tout calcul, et porte sur l'argument : c'est la PRÉCONDITION, ce que l'appelant doit garantir. La seconde, placée juste avant le return, porte sur le résultat : c'est la POSTCONDITION, ce que la fonction garantit en échange. En français : le carré de r ne dépasse pas n, ET le carré de r + 1 le dépasse strictement, donc r est le PLUS GRAND entier dont le carré tient sous n. La première moitié seule ne dit presque rien : r = 0 la vérifie pour tout n positif, et une fonction qui renverrait toujours 0 passerait le contrôle. C'est la seconde moitié qui interdit de renvoyer trop petit. La docstring dit le contrat à l'humain, les assertions le disent à la machine, qui le vérifie à chaque appel.
b)
Pour n = 30, la boucle teste (r+1)2≤30 : 1, 4, 9, 16 et 25 passent, et r monte de 0 à 5 ; au sixième test, 36≤30 est faux et la boucle s'arrête. Elle a fait 5 tours, et la fonction renvoie 5 ; la postcondition 25≤30<36 est vraie. Pour n = 49, le test 49≤49 passe encore, r atteint 7, puis 64≤49 échoue : la fonction renvoie 7, et 49≤49<64. Pour n = 0, le tout premier test 1≤0 est faux : la boucle ne tourne pas, r vaut 0, et la postcondition 0≤0<1 certifie que ce 0 est juste. C'est le cas limite qu'on oublie : une boucle qui ne tourne jamais doit, elle aussi, rendre un résultat correct.
c)
Avec -4, la précondition est fausse : l'exécution s'arrête sur une AssertionError dont le message est « n doit etre positif », avant le moindre calcul. L'erreur est signalée là où la faute a été commise, c'est-à-dire à l'APPEL. Sans la première assertion, la boucle teste 1≤−4, faux, r reste à 0, puis la postcondition 0≤−4 est fausse : une AssertionError se déclenche quand même, mais sur la seconde assertion, qui accuse la fonction alors que c'est l'appelant qui s'est trompé. Sans aucune assertion, la fonction renverrait 0 sans broncher, un résultat faux puisqu'aucun entier n'a un carré inférieur ou égal à -4, et ce 0 se propagerait dans la suite du programme. Hors de sa précondition, une fonction ne promet rien : l'assertion d'entrée sert à le dire tout de suite.
d)
Les cinq tests passent : sur 0, la boucle du camarade ne tourne pas et renvoie 0 ; sur 1, 4, 9 et 16, elle s'arrête exactement sur la racine, puisque le test r * r < n devient faux quand r * r = n. Mais racine_camarade(30) fait tourner r jusqu'à 6, car 25<30 puis 36<30 est faux : elle renvoie 6, alors que 62=36>30. Sa fonction calcule le plus PETIT entier dont le carré atteint n, c'est-à-dire la racine arrondie vers le haut, et les deux versions ne coïncident que sur les carrés parfaits. Or le jeu de tests ne contient QUE des carrés parfaits : il vérifie une seule famille de cas, celle où l'erreur est invisible. Il fallait au moins un entier qui ne soit pas un carré, 2 ou 30 par exemple. C'est la phrase du programme : le succès d'un jeu de tests ne garantit pas la correction d'un programme.
e)
Pour n = 30, la version du camarade arrive au return avec r = 6, et la postcondition exige 36≤30 : elle est fausse, et une AssertionError se déclenche dès le premier appel sur un nombre qui n'est pas un carré. Là où les tests vérifient des CAS choisis à l'avance, la postcondition vérifie une PROPRIÉTÉ à chaque appel, y compris sur les valeurs que personne n'a prévues. Entre 0 et 50, les deux versions coïncident exactement sur les carrés parfaits 0, 1, 4, 9, 16, 25, 36 et 49 : la version du camarade n'est juste que pour 8 valeurs sur 51. On garde en général les postconditions pendant la mise au point : elles coûtent un calcul à chaque appel, et rapportent le bug le jour où il apparaît.
À retenir : la précondition protège la fonction contre l'appelant, la postcondition protège l'appelant contre la fonction. Un jeu de tests qui passe dit seulement que les cas écrits sont justes.
Exercice 17 : Lire la documentation d'une bibliothèque
Personne ne connaît une bibliothèque par cœur, et le programme n'en exige aucune connaissance exhaustive : il demande de savoir LIRE sa documentation. Voici ce qu'affiche help() pour trois fonctions des modules random et math, textes traduits de l'anglais.
Un professeur veut tirer au sort l'ordre de passage à l'oral des 30 élèves d'une classe, numérotés de 1 à 30. On répond sans machine, avec la seule documentation.
Python
>>> help(random.randint)
randint(a, b)
Renvoie un entier aleatoire N tel que a <= N <= b.
>>> help(random.randrange)
randrange(start, stop=None, step=1)
Choisit un element au hasard dans range(start, stop, step).
Appelee avec un seul argument, randrange(stop) choisit
dans range(stop).
Leve ValueError si ce range est vide.
>>> help(math.floor)
floor(x)
Renvoie le plus grand entier inferieur ou egal a x.
a) Combien de valeurs différentes randint(1, 30) peut-il renvoyer ? Et randrange(1, 30) ? Relevez, dans chaque documentation, ce qui décide.
b) Le professeur veut tirer un numéro d'élève avec randrange. Quel appel doit-il écrire ? Quelle est la plus petite valeur que peut renvoyer randrange(30), et pourquoi cet appel ne convient-il pas ?
c) Quelles valeurs peut renvoyer randrange(0, 30, 5) ? Combien y en a-t-il, et quelle est la plus grande ?
d) Que se passe-t-il à l'appel randrange(10, 10) ? Et à l'appel randint(10, 10) ?
e) Que valent floor(3.99) et floor(-2.5) ? Un élève pense que floor « enlève la partie après la virgule ». Sur laquelle de ces deux valeurs la documentation lui donne-t-elle tort ?
Voir la correction
Réponses
a)30 valeurs pour randint(1, 30), bornes comprises ; 29 pour randrange(1, 30), borne 30 exclue
b)randrange(1, 31) ; randrange(30) peut renvoyer 0 et jamais 30
c)0, 5, 10, 15, 20, 25 : 6 valeurs, la plus grande 25
d)randrange(10, 10) lève ValueError ; randint(10, 10) renvoie toujours 10
e)floor(3.99) vaut 3, floor(-2.5) vaut −3 ; l'élève se trompe sur la valeur négative
a)
La documentation de randint écrit a <= N <= b : les DEUX bornes sont comprises, et randint(1, 30) peut renvoyer 1, 2, jusqu'à 30, soit 30−1+1=30 valeurs. Celle de randrange renvoie à range(start, stop, step) : elle hérite donc de sa convention, borne de gauche comprise et borne de droite EXCLUE. randrange(1, 30) choisit dans 1, 2, ..., 29, soit 30−1=29 valeurs, et ne tire jamais 30. Deux fonctions du même module, deux conventions : c'est exactement pour cela qu'on lit la documentation au lieu de deviner d'après le nom.
b)
Il faut que la borne de droite exclue soit 31 : randrange(1, 31) choisit dans 1 à 30, comme randint(1, 30). Avec un seul argument, la documentation précise que randrange(30) choisit dans range(30), c'est-à-dire de 0 à 29 : la plus petite valeur possible est 0, qui ne désigne aucun élève, et l'élève numéro 30 ne serait jamais tiré. L'erreur est double et silencieuse : le programme tourne, les numéros semblent plausibles, et le défaut ne se voit qu'au bout de nombreux tirages. On pourrait aussi écrire randrange(30) + 1, qui décale tout d'un cran : c'est juste, mais moins lisible.
c)
Le troisième paramètre, step, a pour valeur par défaut 1 d'après la signature ; ici il vaut 5. randrange(0, 30, 5) choisit dans range(0, 30, 5), c'est-à-dire 0, 5, 10, 15, 20 et 25 : 6 valeurs, la plus grande étant 25, puisque 30 est la borne exclue. On compte sans les écrire : de 0 inclus à 30 exclu, par pas de 5, il y a 530−0=6 valeurs. Lire une signature, c'est aussi lire ses VALEURS PAR DÉFAUT : stop=None et step=1 disent ce que fait la fonction quand on n'écrit pas ces arguments.
d)
range(10, 10) est vide, puisqu'il s'arrête avant 10 sans avoir commencé : la documentation annonce alors une exception, randrange(10, 10) lève ValueError et le programme s'arrête. randint(10, 10), lui, cherche N tel que 10≤N≤10 : il existe exactement un tel entier, et l'appel renvoie toujours 10. La même paire d'arguments donne une erreur pour l'une et un résultat pour l'autre. La rubrique des exceptions fait partie du contrat au même titre que la valeur renvoyée : une fonction appelée hors de ce contrat ne renvoie rien de faux, elle refuse.
e)
floor renvoie le plus grand entier inférieur ou égal à x. Pour 3,99, c'est 3. Pour −2,5, les entiers inférieurs ou égaux sont −3, −4, et ainsi de suite, et le plus grand est −3 : floor(-2.5) vaut −3. L'idée de l'élève, enlever la partie décimale, donnerait −2, or −2>−2,5 : c'est sur la valeur NÉGATIVE que la documentation lui donne tort, et il ne le verrait jamais en testant 3,99. C'est le même arrondi vers le bas que le quotient entier de l'exercice 1, où -7 // 2 vaut -4.
La méthode, pour toute fonction inconnue : lire les paramètres et leurs valeurs par défaut, les bornes incluses ou exclues, la valeur renvoyée, et les exceptions. Quatre lignes de documentation lues avec soin évitent les bugs que dix exécutions ne montrent pas.
Il manque quelque chose dans cette série ?Un type d'exercice que ton prof donne, un énoncé qui te bloque, une erreur repérée : dis-le-moi, je lis chaque demande.
L'envoi passe par ton espace gratuit : c'est ce qui me permet de te répondre et de te prévenir quand l'exercice est ajouté. Un courriel suffit, pas de mot de passe. Crée ton espace.
Pas envie de créer un compte ? Écris-moi directement.
Contactez-moi pour une première séance. Bachelier en informatique de McGill et maîtrise en informatique appliquée de Concordia, je travaille la NSI sur du code réel, pas seulement sur le cours.