Moon Arrows Sun
Arrows
Return Retour
Accueil Home
Imprimer

Les programmes débranchés

Les cartes d'un magicien, la monnaie d'un distributeur, les carrés d'un menuisier et le calendrier d'un championnat : quatre programmes Python à dérouler à la main, sans ordinateur.

Les cartes du magicien

Un magicien fait choisir un nombre entier de \(1\) à \(15\), puis demande sur lesquelles de ses quatre cartes il est écrit. Ce programme écrit les cartes ; n % 4 est le reste de la division de n par \(4\).

for n in range(1, 16):
    if n % 2 == 1:
        print(n, "carte A")
    if n % 4 >= 2:
        print(n, "carte B")
    if n % 8 >= 4:
        print(n, "carte C")
    if n >= 8:
        print(n, "carte D")
Les quatre cartes du magicien, A, B, C et D, chacune de huit cases : la carte A porte 1, 3, 5, 7, 9, 11, 13 et 15, les trois autres sont vides Carte A 1 3 5 7 9 11 13 15 Carte B Carte C Carte D
Les quatre cartes complétées. A : 1, 3, 5, 7, 9, 11, 13, 15. B : 2, 3, 6, 7, 10, 11, 14, 15. C : 4, 5, 6, 7, 12, 13, 14, 15. D : 8 à 15. Le plus petit nombre de chaque carte, 1, 2, 4 et 8, est sur fond vert Carte A 1 3 5 7 9 11 13 15 Carte B 2 3 6 7 10 11 14 15 Carte C 4 5 6 7 12 13 14 15 Carte D 8 9 10 11 12 13 14 15
  1. La boucle for n in range(1, 16) répète son bloc pour chaque entier n de \(1\) à \(15\). Dérouler le programme et compléter les cartes B, C et D : la carte A est déjà écrite.

    Pour \(n = 6\) : 6 % 2 vaut \(0\), 6 % 4 vaut \(2\), 6 % 8 vaut \(6\), et \(6 \lt 8\). Le nombre \(6\) va donc sur les cartes B et C.

    Les restes de la division par \(4\) se répètent : \(1\), \(2\), \(3\), \(0\). La carte B prend les nombres de reste \(2\) ou \(3\) :

    $$ \text{carte B} : 2 \ ; \ 3 \ ; \ 6 \ ; \ 7 \ ; \ 10 \ ; \ 11 \ ; \ 14 \ ; \ 15 $$

    La carte C prend les nombres dont le reste par \(8\) vaut au moins \(4\), la carte D ceux qui valent au moins \(8\) :

    $$ \text{carte C} : 4 \ ; \ 5 \ ; \ 6 \ ; \ 7 \ ; \ 12 \ ; \ 13 \ ; \ 14 \ ; \ 15 $$
    $$ \text{carte D} : 8 \ ; \ 9 \ ; \ 10 \ ; \ 11 \ ; \ 12 \ ; \ 13 \ ; \ 14 \ ; \ 15 $$

    Chaque carte porte huit nombres, et commence par \(1\), \(2\), \(4\) ou \(8\).

  2. Le magicien additionne les plus petits nombres des cartes qui portent le nombre choisi. Retrouver ainsi le nombre de chaque spectateur : il doit être écrit sur ces cartes-là, et sur elles seules.
    Les réponses des cinq spectateurs. Léa : oui pour A, C et D. Hugo : oui pour B et C. Inès : oui pour les quatre cartes. Tom : oui pour D seulement. Clara : oui pour A, B et D. La colonne du nombre choisi est vide spectateur A B C D nombre choisi Léa oui non oui oui Hugo non oui oui non Inès oui oui oui oui Tom non non non oui Clara oui oui non oui
    $$ \text{Léa} : 1 + 4 + 8 = 13 \quad \text{Hugo} : 2 + 4 = 6 \quad \text{Inès} : 1 + 2 + 4 + 8 = 15 $$
    $$ \text{Tom} : 8 \quad \text{Clara} : 1 + 2 + 8 = 11 $$

    \(13\) est bien sur les cartes A, C et D, et pas sur la carte B : le tour a marché.

    Le tableau des spectateurs complété : Léa 13, Hugo 6, Inès 15, Tom 8, Clara 11 spectateur A B C D nombre choisi Léa oui non oui oui 13 Hugo non oui oui non 6 Inès oui oui oui oui 15 Tom non non non oui 8 Clara oui oui non oui 11
  3. Pour aller jusqu'à \(31\), le magicien remplace range(1, 16) par range(1, 32), et ajoute une carte E écrite par le test if n >= 16. Sur quelles cartes le nombre \(16\) est-il alors écrit ? Montrer que le tour échoue pour lui.

    16 % 2, 16 % 4 et 16 % 8 valent \(0\) : \(16\) n'est ni sur A, ni sur B, ni sur C. Mais \(16 \geqslant 8\) et \(16 \geqslant 16\) : il est sur les cartes D et E.

    $$ 8 + 16 = 24 \neq 16 $$

    Le magicien annonce \(24\) : le tour échoue. Il échoue de même pour tous les nombres de \(16\) à \(23\).

  4. Corriger le test de la carte D, sur le modèle des tests des cartes B et C, puis trouver les cartes qui portent le nombre \(24\) avec le programme corrigé.

    Les tests se suivent : reste par \(4\) au moins \(2\), reste par \(8\) au moins \(4\), donc reste par \(16\) au moins \(8\) :

        if n % 16 >= 8:
        print(n, "carte D")

    16 % 16 vaut \(0\) : \(16\) n'est plus que sur la carte E, et le magicien annonce bien \(16\).

    Pour \(24\) : 24 % 2, 24 % 4 et 24 % 8 valent \(0\), 24 % 16 vaut \(8\) et \(24 \geqslant 16\). Il est sur les cartes D et E :

    $$ 8 + 16 = 24 $$

La monnaie du distributeur

Le distributeur de boissons du foyer rend la monnaie en pièces de \(2 \ \text{€}\), de \(1 \ \text{€}\), de \(50\), de \(20\) et de \(10\) centimes. Il compte en centimes : rendre \(3.80 \ \text{€}\) s'écrit reste = 380. La boucle while répète son bloc tant que sa condition est vraie.

reste = 380
while reste > 0:
    if reste >= 200:
        piece = 200
    elif reste >= 100:
        piece = 100
    elif reste >= 50:
        piece = 50
    elif reste >= 20:
        piece = 20
    else:
        piece = 10
    print(piece)
    reste = reste - piece
Quatre tickets, pour reste = 380, 170, 490 et 375 : chacun a une colonne reste, dont la première case porte le montant, une colonne pièce de six lignes, et une case pour le total reste = 380 reste pièce 380 total reste = 170 reste pièce 170 total reste = 490 reste pièce 490 total reste = 375 reste pièce 375 total
Les tickets complétés. 380 : 200, 100, 50, 20, 10, total 380. 170 : 100, 50, 20, total 170. 490 : 200, 200, 50, 20, 20, total 490. 375 : 200, 100, 50, 20, 10, total 380, en rouge, et le reste finit à moins 5 reste = 380 reste pièce 380 200 180 100 80 50 30 20 10 10 0 total 380 reste = 170 reste pièce 170 100 70 50 20 20 0 total 170 reste = 490 reste pièce 490 200 290 200 90 50 40 20 20 20 0 total 490 reste = 375 reste pièce 375 200 175 100 75 50 25 20 5 10 -5 total 380
  1. Dérouler le programme pour reste = 380, puis en remplaçant 380 par 170 et par 490. Sur chaque ticket, écrire la valeur de reste au début de chaque tour, la pièce affichée, puis le total des pièces.

    Pour 380 : 380 vaut au moins 200, la machine rend 200 et reste vaut 180 ; puis 100, 50, 20 et 10.

    $$ 200 + 100 + 50 + 20 + 10 = 380 $$

    Les autres tickets :

    $$ 100 + 50 + 20 = 170 \quad \text{et} \quad 200 + 200 + 50 + 20 + 20 = 490 $$

    Chaque fois, reste tombe à 0 et la boucle s'arrête : le total est le montant à rendre.

  2. Un client a payé avec une pièce de \(5\) centimes : le distributeur doit rendre \(375\) centimes. Dérouler le programme sur le dernier ticket, puis expliquer ce qui ne va pas.

    La machine rend 200, 100, 50 et 20 : reste vaut alors 5. Aucun test n'est vrai, le else rend 10, et reste passe à -5 : la boucle s'arrête.

    $$ 200 + 100 + 50 + 20 + 10 = 380 \neq 375 $$

    Le distributeur rend \(5\) centimes de trop : le else donne une pièce de \(10\) centimes à tout reste de moins de \(20\), même plus petit que \(10\).

  3. Corriger le programme pour que le distributeur rende exactement \(375\) centimes, avec une pièce de \(5\) centimes.

    Le dernier cas devient un test, et la pièce de 5 centimes prend le else :

        elif reste >= 10:
        piece = 10
    else:
        piece = 5
    $$ 200 + 100 + 50 + 20 + 5 = 375 $$
  4. On revient au programme de départ, et le distributeur n'a plus de pièces de \(50\) centimes. Dire quelles lignes retirer du programme, puis quelles pièces il rend alors pour \(380\) centimes.

    On retire les deux lignes elif reste >= 50: et piece = 50. Pour 380 :

    $$ 200 + 100 + 20 + 20 + 20 + 20 = 380 $$

    Le distributeur rend six pièces au lieu de cinq.

Les carrés du menuisier

Un menuisier découpe une planche de a carreaux de long sur b de large en carrés : il scie le plus grand carré possible, puis recommence avec le morceau qui reste, jusqu'à ce que ce morceau soit lui-même un carré. Ce programme suit les dimensions du morceau qui reste.

a = 21
b = 12
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
print(a)
Trois tableaux de suivi, pour les planches de 21 sur 12, de 13 sur 8 et de 16 sur 6, avec les colonnes tour, a et b, et une dernière case pour le nombre affiché ; seule la ligne de départ est remplie 21 sur 12 tour a b affiché départ 21 12 1 2 3 4 5 13 sur 8 tour a b affiché départ 13 8 1 2 3 4 5 16 sur 6 tour a b affiché départ 16 6 1 2 3 4 5
Les tableaux complétés, a et b à chaque tour. 21 sur 12 : 21 et 12, 9 et 12, 9 et 3, 6 et 3, 3 et 3, affiché 3. 13 sur 8 : 13 et 8, 5 et 8, 5 et 3, 2 et 3, 2 et 1, 1 et 1, affiché 1. 16 sur 6 : 16 et 6, 10 et 6, 4 et 6, 4 et 2, 2 et 2, affiché 2 21 sur 12 tour a b affiché 3 départ 21 12 1 9 12 2 9 3 3 6 3 4 3 3 5 13 sur 8 tour a b affiché 1 départ 13 8 1 5 8 2 5 3 3 2 3 4 2 1 5 1 1 16 sur 6 tour a b affiché 2 départ 16 6 1 10 6 2 4 6 3 4 2 4 2 2 5
  1. Dérouler le programme pour chaque planche : compléter son tableau, tour après tour, puis le nombre affiché.

    Pour la planche de 21 sur 12, a vaut plus que b : a passe à 21 - 12, soit 9. Puis b vaut plus que a : b passe à 12 - 9, soit 3.

    $$ (21 \ ; \ 12) \rightarrow (9 \ ; \ 12) \rightarrow (9 \ ; \ 3) \rightarrow (6 \ ; \ 3) \rightarrow (3 \ ; \ 3) $$
    $$ (13 \ ; \ 8) \rightarrow (5 \ ; \ 8) \rightarrow (5 \ ; \ 3) \rightarrow (2 \ ; \ 3) \rightarrow (2 \ ; \ 1) \rightarrow (1 \ ; \ 1) $$
    $$ (16 \ ; \ 6) \rightarrow (10 \ ; \ 6) \rightarrow (4 \ ; \ 6) \rightarrow (4 \ ; \ 2) \rightarrow (2 \ ; \ 2) $$

    Le programme affiche \(3\), puis \(1\), puis \(2\).

  2. À chaque tour, le menuisier scie un carré dont le côté est le plus petit des deux nombres a et b : à gauche quand a > b, en haut sinon. Tracer sur chaque planche les carrés sciés, tour après tour : le dernier morceau est un carré dont le côté est le nombre affiché.
    Trois planches quadrillées, de 21 carreaux sur 12, de 13 sur 8 et de 16 sur 6 planche de 21 sur 12 planche de 13 sur 8 planche de 16 sur 6

    Chaque planche est entièrement couverte de carrés, et le dernier, en vert, a pour côté \(3\), \(1\) et \(2\).

    Les trois planches sciées. 21 sur 12 : carrés de 12, 9, 3, 3, puis le dernier carré de 3, en vert. 13 sur 8 : carrés de 8, 5, 3, 2, 1, puis le dernier carré de 1. 16 sur 6 : carrés de 6, 6, 4, 2, puis le dernier carré de 2 planche de 21 sur 12 12 9 3 3 3 planche de 13 sur 8 8 5 3 2 planche de 16 sur 6 6 6 4 2 2
  3. Dérouler le programme, sans tracer, pour une planche de \(55\) carreaux sur \(34\) : donner le nombre de tours de boucle et ce qu'affiche le programme.
    $$ (55 \ ; \ 34) \rightarrow (21 \ ; \ 34) \rightarrow (21 \ ; \ 13) \rightarrow (8 \ ; \ 13) \rightarrow (8 \ ; \ 5) $$
    $$ (8 \ ; \ 5) \rightarrow (3 \ ; \ 5) \rightarrow (3 \ ; \ 2) \rightarrow (1 \ ; \ 2) \rightarrow (1 \ ; \ 1) $$

    La boucle fait \(8\) tours, et le programme affiche \(1\) : le dernier carré a un seul carreau de côté.

  4. Expliquer pourquoi la boucle s'arrête toujours quand a et b sont des entiers strictement positifs. Que se passe-t-il avec a = 7 et b = 0 ?

    À chaque tour, on retranche le plus petit des deux nombres du plus grand : a et b restent des entiers strictement positifs, et leur somme diminue d'au moins 1. Une somme d'entiers positifs ne peut pas diminuer indéfiniment : la boucle s'arrête.

    Avec a = 7 et b = 0, a > b et a devient 7 - 0, soit encore 7 : rien ne change, et la boucle ne s'arrête jamais.

Le calendrier du championnat

Cinq équipes, numérotées de \(1\) à \(5\), disputent un championnat : chacune rencontre une fois chacune des autres. Pour chaque match, ce programme affiche les deux équipes i et j, l'équipe qui reçoit, puis le jour du match. La boucle de j est dans celle de i : pour chaque valeur de i, j prend toutes les valeurs de i + 1 à \(5\).

for i in range(1, 6):
    for j in range(i + 1, 6):
        if (i + j) % 2 == 1:
            hote = i
        else:
            hote = j
        jour = (i + j) % 5 + 1
        print(i, j, hote, jour)
La grille du championnat : cinq lignes, i de 1 à 5, et cinq colonnes, j de 1 à 5. Les cases au-dessus de la diagonale portent deux mentions à compléter, chez et jour ; les autres sont grisées chez jour chez jour chez jour chez jour chez jour chez jour chez jour chez jour chez jour chez jour j = 1 i = 1 j = 2 i = 2 j = 3 i = 3 j = 4 i = 4 j = 5 i = 5
La grille complétée : 1 contre 2 chez 1 le jour 4 ; 1 contre 3 chez 3 le jour 5 ; 1 contre 4 chez 1 le jour 1 ; 1 contre 5 chez 5 le jour 2 ; 2 contre 3 chez 2 le jour 1 ; 2 contre 4 chez 4 le jour 2 ; 2 contre 5 chez 2 le jour 3 ; 3 contre 4 chez 3 le jour 3 ; 3 contre 5 chez 5 le jour 4 ; 4 contre 5 chez 4 le jour 5 chez jour 1 4 chez jour 3 5 chez jour 1 1 chez jour 5 2 chez jour 2 1 chez jour 4 2 chez jour 2 3 chez jour 3 3 chez jour 5 4 chez jour 4 5 j = 1 i = 1 j = 2 i = 2 j = 3 i = 3 j = 4 i = 4 j = 5 i = 5
  1. Dérouler les deux boucles : pour chaque ligne affichée, écrire dans la case de la ligne i et de la colonne j l'équipe qui reçoit et le jour du match. Combien de lignes le programme affiche-t-il ?

    Pour \(i = 1\) et \(j = 2\) : \(1 + 2 = 3\) est impair, l'équipe \(1\) reçoit ; 3 % 5 vaut \(3\), le match a lieu le jour \(4\). La première ligne affichée est 1 2 1 4.

    Pour \(i = 1\), j va de \(2\) à \(5\) : quatre lignes. Puis trois pour \(i = 2\), deux pour \(i = 3\), une pour \(i = 4\), aucune pour \(i = 5\).

    $$ 4 + 3 + 2 + 1 + 0 = 10 \ \text{lignes} $$
  2. Compléter le calendrier jour par jour, avec les deux matchs du jour et l'équipe au repos, puis le nombre de matchs que chaque équipe joue chez elle. Aucune équipe ne doit jouer deux fois le même jour.
    Le calendrier à remplir, jour par jour de 1 à 5, avec deux matchs et une équipe au repos, et à côté le tableau du nombre de matchs que chaque équipe, de 1 à 5, joue chez elle jour match match au repos 1 2 3 4 5 équipe matchs chez elle 1 2 3 4 5

    Chaque jour, quatre équipes différentes jouent et la cinquième se repose ; chaque équipe joue deux matchs chez elle et deux à l'extérieur.

    Le calendrier complété. Jour 1 : 1 contre 4, 2 contre 3, l'équipe 5 au repos. Jour 2 : 1 contre 5, 2 contre 4, l'équipe 3 au repos. Jour 3 : 2 contre 5, 3 contre 4, l'équipe 1 au repos. Jour 4 : 1 contre 2, 3 contre 5, l'équipe 4 au repos. Jour 5 : 1 contre 3, 4 contre 5, l'équipe 2 au repos. Chaque équipe joue deux matchs chez elle jour match match au repos 1 1 contre 4 2 contre 3 5 2 1 contre 5 2 contre 4 3 3 2 contre 5 3 contre 4 1 4 1 contre 2 3 contre 5 4 5 1 contre 3 4 contre 5 2 équipe matchs chez elle 1 2 2 2 3 2 4 2 5 2
  3. Expliquer pourquoi la boucle de j commence à i + 1, et non à \(1\).

    Si j partait de \(1\), le programme afficherait aussi « 2 contre 1 », alors que « 1 contre 2 » est déjà écrit : chaque match serait joué deux fois. Il ferait aussi jouer chaque équipe contre elle-même, comme « 3 contre 3 ».

    En partant de i + 1, chaque paire d'équipes n'est écrite qu'une fois, la plus petite en premier : \(25\) lignes deviennent \(10\).

  4. Prouver qu'une équipe ne joue jamais deux matchs le même jour. On pourra noter e son numéro, u et v ceux de deux de ses adversaires, et comparer les nombres e + u et e + v.

    Le jour du match entre e et u se calcule par (e + u) % 5 + 1, que e soit i ou j. Les adversaires u et v sont deux numéros différents de \(1\) à \(5\) : e + u et e + v diffèrent de \(1\), \(2\), \(3\) ou \(4\).

    Deux nombres qui ont le même reste dans la division par \(5\) diffèrent d'un multiple de \(5\). Ce n'est pas le cas ici : les deux restes sont différents, et les deux matchs tombent deux jours différents.