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ée Tape 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.

Ce chapitre fait partie de NSI en Première
Avant de commencer Fiche de révision : les pièges et la méthode de ce chapitre

Avant ce chapitre

Ces notions sont supposées acquises ici. Si le premier exercice résiste, le blocage vient presque toujours de l'une d'elles, pas du chapitre lui-même.

Remonter plus loin : la chaîne complète (4 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

  1. 1 Algorithmique et Scratch Cinquième, Mathématiques
  2. 2 Algorithmique et Scratch Quatrième, Mathématiques
  3. 3 Algorithmique et Scratch Troisième, Mathématiques
  4. 4 Algorithmique et Python Seconde, Mathématiques

Rappel de cours

  • • Division : a // ba\ //\ b est le quotient entier (arrondi vers le bas, y compris pour les négatifs) et a % ba\ \%\ b le reste ; a / ba\ /\ 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.

Tape tes réponses, la page te dit juste ou faux 0/15

a)
b)
c)
d)
e)
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)a = b \times (a\ //\ b) + (a\ \%\ b) doit rester vraie, et en effet −7=2×(−4)+1-7 = 2\times(-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.

Tape tes réponses, la page te dit juste ou faux 0/7

a)
b)
c)
d)
e)
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.

Tape tes réponses, la page te dit juste ou faux 0/7

a)
b)
c)
d)
e)
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
246810121416102030405060maximum 52départ 7arrivée 1tours de bouclevaleur de n

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).

Tape tes réponses, la page te dit juste ou faux 0/5

a)
b)
c)
d)
e)
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]
123défaut de listeajouter(1) : listeajouter(2) : listeajouter(3) : listeune seule liste,créée à la définition

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.

012345informatiquetm
  • 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.

Tape tes réponses, la page te dit juste ou faux 0/10

a)
b)
c)
d)
e)
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]
00-611-522-433-344-255-10123456t[1:4] = [1, 2, 3]t[-2:] = [4, 5]indicevaleurindice négatifcoupure

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.

Tape tes réponses, la page te dit juste ou faux 0/6

a)
b)
c)
d)
e)
Voir la correction

Réponses

  • a) Moyenne 13,513{,}5
  • b) 10,510{,}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 à n2n^{2} au lieu de nn. 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.

Tape tes réponses, la page te dit juste ou faux 0/7

a)
b)
c)
d)
e)
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.

381004291175622colonne jligne i
  • 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.

Tape tes réponses, la page te dit juste ou faux 0/6

a)
b)
c)
d)
e)
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
[[0] * p] * ng[0]g[1]g[2]000une seule ligne[[0] * p for _ in range(n)]g[0]000g[1]000g[2]000trois lignes distinctes

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.

a0b1c2d3e4f5g6h7i8j9k10l11m12n13o14p15q16r17s18t19u20v21w22x23y24z25alpha : position de chaque lettre
  • 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.

Tape tes réponses, la page te dit juste ou faux 0/7

a)
b)
c)
d)
e)
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é.

123456101214161820222412151419222117indice du jourtempérature (°C)
  • 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 ?

Tape tes réponses, la page te dit juste ou faux 0/6

a)
b)
c)
d)
e)
Voir la correction

Réponses

  • a) Amplitude 10
  • b) [3, 4, 5]
  • c) Hausse 5 à l'indice 2
  • d) Plus longue hausse : 3
  • e) Un accumulateur exige une boucle
a)

amplitude(t) = max(t) - min(t) = 22 - 12 = 10 degrés.

b)

La moyenne vaut 12+15+14+19+22+21+177=1207≈17,14\frac{12+15+14+19+22+21+17}{7}=\frac{120}{7}\approx 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
1234561012141618202224moyenne ≈ 17,14+522192114, 19, 22 : 3 jours en hausseindice du jourtempérature (°C)

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 ?

Tape tes réponses, la page te dit juste ou faux 0/9

a)
b)
c)
d)
e)
Voir la correction

Réponses

  • a) 0+1+2+3=60 + 1 + 2 + 3 = 6
  • b) n(n−1)/2n(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)=n(n−1)20 + 1 + \dots + (n-1) = \frac{n(n-1)}{2}. Pour n = 100 : 100×992=4 950\frac{100 \times 99}{2} = 4\ 950. Le nombre de tours croît comme n2n^{2} : 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.

i = 0aucun tour0i = 11i = 22i = 33tours60 + 1 + 2 + 3 = 6

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 ?

Tape tes réponses, la page te dit juste ou faux 0/12

a)
b)
c)
d)
e)
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.

toutes les annéesmultiples de 4multiples de 100multiples de 400bissextilebissextile
  • 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.

Tape tes réponses, la page te dit juste ou faux 0/8

a)
b)
c)
d)
e)
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=9 13225 \times 365 + 7 = 9\ 132 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)
toutes les annéesmultiples de 4multiples de 100multiples de 400bissextilebissextile2024202319002000non bissextile

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 ?

Tape tes réponses, la page te dit juste ou faux 0/7

a)
b)
c)
d)
e)
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')
chiffre30987654321rang012345678910doublé0161284compte pour30977358341somme : 50, multiple de 10rangs impairs doublés

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.

Python
g = [['X', 'O', 'X'],
     ['O', 'X', 'O'],
     ['O', 'X', 'X']]
  • 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.

Tape tes réponses, la page te dit juste ou faux 0/11

a)
b)
c)
d)
e)
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
001122g[0][0], g[1][1], g[2][2] : trois X

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 ?

Tape tes réponses, la page te dit juste ou faux 0/12

a)
b)
c)
d)
e)
Voir la correction

Réponses

  • a) La première est la précondition, la seconde la postcondition : r2≤n<(r+1)2r^{2}\leq n<(r+1)^{2}, r est le plus grand entier de carré au plus n
  • b) 55, 77 et 00 ; 55 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 66 ; il manquait un entier non carré
  • e) AssertionError dès l'appel ; juste pour 88 valeurs sur 5151, 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(r+1)^{2}\leq 30 : 11, 44, 99, 1616 et 2525 passent, et r monte de 0 à 5 ; au sixième test, 36≤3036\leq 30 est faux et la boucle s'arrête. Elle a fait 5 tours, et la fonction renvoie 5 ; la postcondition 25≤30<3625\leq 30<36 est vraie. Pour n = 49, le test 49≤4949\leq 49 passe encore, r atteint 7, puis 64≤4964\leq 49 échoue : la fonction renvoie 7, et 49≤49<6449\leq 49<64. Pour n = 0, le tout premier test 1≤01\leq 0 est faux : la boucle ne tourne pas, r vaut 0, et la postcondition 0≤0<10\leq 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≤−41\leq -4, faux, r reste à 0, puis la postcondition 0≤−40\leq -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<3025<30 puis 36<3036<30 est faux : elle renvoie 6, alors que 62=36>306^{2}=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≤3036\leq 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 00, 11, 44, 99, 1616, 2525, 3636 et 4949 : 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 3030 élèves d'une classe, numérotés de 11 à 3030. 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 ?

Tape tes réponses, la page te dit juste ou faux 0/10

a)
b)
c)
d)
e)
Voir la correction

Réponses

  • a) 3030 valeurs pour randint(1, 30), bornes comprises ; 2929 pour randrange(1, 30), borne 3030 exclue
  • b) randrange(1, 31) ; randrange(30) peut renvoyer 00 et jamais 3030
  • c) 00, 55, 1010, 1515, 2020, 2525 : 66 valeurs, la plus grande 2525
  • d) randrange(10, 10) lève ValueError ; randint(10, 10) renvoie toujours 1010
  • e) floor(3.99) vaut 33, floor(-2.5) vaut −3-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 11, 22, jusqu'à 3030, soit 30−1+1=3030-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 11, 22, ..., 2929, soit 30−1=2930-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 11 à 3030, comme randint(1, 30). Avec un seul argument, la documentation précise que randrange(30) choisit dans range(30), c'est-à-dire de 00 à 2929 : la plus petite valeur possible est 00, 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 00, 55, 1010, 1515, 2020 et 2525 : 66 valeurs, la plus grande étant 2525, puisque 3030 est la borne exclue. On compte sans les écrire : de 00 inclus à 3030 exclu, par pas de 55, il y a 30−05=6\frac{30-0}{5}=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≤1010\leq N\leq 10 : il existe exactement un tel entier, et l'appel renvoie toujours 1010. 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,993{,}99, c'est 33. Pour −2,5-2{,}5, les entiers inférieurs ou égaux sont −3-3, −4-4, et ainsi de suite, et le plus grand est −3-3 : floor(-2.5) vaut −3-3. L'idée de l'élève, enlever la partie décimale, donnerait −2-2, or −2>−2,5-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,993{,}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.

De quoi s'agit-il ?
Je lis chaque demande moi-même, personne d'autre ne la voit. Inutile d'écrire ton nom ou celui de ton école.
Quand ta demande est traitée, tu es prévenu par courriel et dans ton espace.

En envoyant, tu acceptes que je lise ta demande pour y répondre. Elle est gardée avec ton compte, effacée avec lui, et jamais publiée : politique de confidentialité.

Chapitre suivant Représentation des données : réels et texte

Ce chapitre resservira dans

Les chapitres qui le réclament en amont, plus tard dans l'année ou dans les années suivantes.

© Ahmed Squalli Houssaini. Série publiée sur www.letuteurscientifique.ca/exercices/nsi-python-bases. Libre pour l'usage personnel et en classe ; sa republication ailleurs demande une autorisation écrite (mentions légales).

Voir aussi

Vous cherchez un tuteur en NSI à Montréal ?

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.

Site par Studio Squalli