Moon Arrows Sun
Arrows
Return Retour
Accueil Home
Imprimer

Les casse-tête de Python

Un mélangeur de lettres, des programmes sans retraits, des nombres retournés et une ligne qui se dessine : quatre casse-tête Python à résoudre à la main, sans ordinateur.

Le mélangeur de lettres

Une chaîne de caractères se lit lettre par lettre : mot[i] est la lettre de rang i, les rangs partant de \(0\), et len(mot) est le nombre de lettres. Cette fonction mélange les lettres d'un mot.

def melange(mot, pas):
    n = len(mot)
    res = ""
    for k in range(n):
        rang = (pas * k) % n
        res = res + mot[rang]
    return res
Les lettres de TRIANGLE avec leur rang, de 0 à 7, au-dessus d'un tableau à compléter, avec les colonnes k, rang, mot[rang] et res, et une ligne pour chaque k de 0 à 7 0 T 1 R 2 I 3 A 4 N 5 G 6 L 7 E k rang mot[rang] res 0 1 2 3 4 5 6 7
Le tableau complété : les rangs 0, 3, 6, 1, 4, 7, 2, 5 donnent les lettres T, A, L, R, N, E, I, G, et res finit à TALRNEIG 0 T 1 R 2 I 3 A 4 N 5 G 6 L 7 E k rang mot[rang] res 0 0 T T 1 3 A TA 2 6 L TAL 3 1 R TALR 4 4 N TALRN 5 7 E TALRNE 6 2 I TALRNEI 7 5 G TALRNEIG
  1. Dérouler l'appel melange("TRIANGLE", 3) et compléter le tableau, tour après tour.

    Le mot a \(8\) lettres. Pour \(k = 3\) : rang = 9 % 8, soit \(1\), et la lettre de rang \(1\) est R. Les rangs pris tour après tour :

    $$ 0 \ ; \ 3 \ ; \ 6 \ ; \ 1 \ ; \ 4 \ ; \ 7 \ ; \ 2 \ ; \ 5 $$

    La fonction renvoie TALRNEIG : les huit lettres de TRIANGLE, chacune une fois.

  2. Écrire le mot que renvoie melange("TALRNEIG", 3). Que remarque-t-on ?

    Les mêmes rangs 0, 3, 6, 1, 4, 7, 2, 5 prennent dans TALRNEIG les lettres T, R, I, A, N, G, L, E : la fonction renvoie TRIANGLE.

    Le mélangeur de pas 3, appliqué deux fois à un mot de huit lettres, rend le mot de départ.

  3. Écrire le mot que renvoie melange("PYTHON", 3), puis expliquer pourquoi des lettres disparaissent.

    Le mot a \(6\) lettres : les rangs sont 0, 3, 0, 3, 0, 3, et la fonction renvoie PHPHPH.

    3 × k est un multiple de \(3\). Quand k est pair, c'est un multiple de \(6\), de reste \(0\) ; quand k est impair, il dépasse un multiple de \(6\) de \(3\). Le rang ne vaut donc que \(0\) ou \(3\), et seules les lettres P et H sont prises.

L'indentation perdue

Ces programmes ont perdu leurs retraits. Un retrait décale une ligne de quatre espaces vers la droite : la ligne qui suit les deux-points d'un for, d'un while ou d'un if prend un retrait de plus que lui.

  1. Rendre au programme A ses retraits : dans chaque colonne, écrire le nombre de retraits de chaque ligne pour que le programme affiche l'écran de cette colonne.
    Programme A, sans indentation : total = 0 ; for k in range(1, 11): ; if k % 3 == 0: ; print(k) ; total = total + k ; print(total). Devant chaque ligne, deux cases de retraits, l'une pour l'écran 1, l'autre pour l'écran 2. Écran 1 : 3, 6, 9, 18. Écran 2 : 3, 6, 9, 55 1 2 total = 0 for k in range(1, 11): if k % 3 == 0: print(k) total = total + k print(total) écran 1 3 6 9 18 écran 2 3 6 9 55

    print(k) suit le if : deux retraits. Pour l'écran 1, total = total + k reste dans le if et n'ajoute que 3, 6 et 9 ; pour l'écran 2, elle sort du if, reste dans la boucle, et ajoute tous les entiers de 1 à 10.

    $$ 3 + 6 + 9 = 18 \quad \text{et} \quad 1 + 2 + \cdots + 10 = 55 $$
    Programme A, retraits retrouvés. Écran 1 : 0, 0, 1, 2, 2, 0. Écran 2 : 0, 0, 1, 2, 1, 0 1 2 0 0 total = 0 0 0 for k in range(1, 11): 1 1 if k % 3 == 0: 2 2 print(k) 2 1 total = total + k 0 0 print(total) écran 1 3 6 9 18 écran 2 3 6 9 55
  2. Rendre de même au programme B ses retraits, pour chacun des deux écrans.
    Programme B, sans indentation : a = 1 ; n = 0 ; while n < 5: ; a = 2 * a + 1 ; n = n + 1 ; print(a). Devant chaque ligne, deux cases de retraits, l'une pour l'écran 1, l'autre pour l'écran 2. Écran 1 : 63. Écran 2 : 3, 7, 15, 31, 63 1 2 a = 1 n = 0 while n < 5: a = 2 * a + 1 n = n + 1 print(a) écran 1 63 écran 2 3 7 15 31 63

    a prend les valeurs 3, 7, 15, 31 et 63 en cinq tours. Sans retrait, print(a) n'affiche que la dernière ; avec un retrait, elle les affiche toutes.

    Programme B, retraits retrouvés. Écran 1 : 0, 0, 0, 1, 1, 0. Écran 2 : 0, 0, 0, 1, 1, 1 1 2 0 0 a = 1 0 0 n = 0 0 0 while n < 5: 1 1 a = 2 * a + 1 1 1 n = n + 1 0 1 print(a) écran 1 63 écran 2 3 7 15 31 63
  3. Dans le programme B, la ligne n = n + 1 perd son retrait. Expliquer pourquoi le programme ne s'arrête plus.

    La ligne n = n + 1 sort de la boucle : le bloc du while ne contient plus que a = 2 * a + 1. n reste égal à \(0\), la condition n < 5 reste vraie, et la boucle tourne sans fin.

  4. Rendre enfin au programme C ses retraits, pour chacun des deux écrans.
    Programme C, sans indentation : for i in range(1, 4): ; s = 0 ; for j in range(1, i + 1): ; s = s + j ; print(i, s). Devant chaque ligne, deux cases de retraits, l'une pour l'écran 1, l'autre pour l'écran 2. Écran 1 : 1 1, 2 3, 3 6. Écran 2 : 3 1, 3 3, 3 6 1 2 for i in range(1, 4): s = 0 for j in range(1, i + 1): s = s + j print(i, s) écran 1 1 1 2 3 3 6 écran 2 3 1 3 3 3 6

    Pour l'écran 1, la boucle de j est dans celle de i, et s repart de 0 pour chaque i : le programme affiche 1, 1 + 2 et 1 + 2 + 3.

    for i in range(1, 4):
    s = 0
    for j in range(1, i + 1):
        s = s + j
    print(i, s)

    Pour l'écran 2, i vaut toujours 3 : la boucle de j est sortie de celle de i, qui ne contient plus que s = 0, et le print est dans la boucle de j.

    for i in range(1, 4):
    s = 0
for j in range(1, i + 1):
    s = s + j
    print(i, s)
    Programme C, retraits retrouvés. Écran 1 : 0, 1, 1, 2, 1. Écran 2 : 0, 1, 0, 1, 1 1 2 0 0 for i in range(1, 4): 1 1 s = 0 1 0 for j in range(1, i + 1): 2 1 s = s + j 1 1 print(i, s) écran 1 1 1 2 3 3 6 écran 2 3 1 3 3 3 6

Les nombres retournés

n % 10 est le chiffre des unités de n, et n // 10 son quotient entier par \(10\) : 2026 % 10 vaut \(6\), et 2026 // 10 vaut \(202\).

def retourne(n):
    r = 0
    while n > 0:
        r = 10 * r + n % 10
        n = n // 10
    return r
Le tableau de suivi de retourne(2026), colonnes tour, n et r : le départ porte n = 2026 et r = 0, puis quatre tours et la valeur renvoyée à compléter tour n r départ 2026 0 1 2 3 4 renvoie
Le suivi de retourne(2026) complété : n vaut 202, 20, 2 puis 0, r vaut 6, 62, 620 puis 6202, et la fonction renvoie 6202 tour n r départ 2026 0 1 202 6 2 20 62 3 2 620 4 0 6202 renvoie 6202
  1. Dérouler l'appel retourne(2026) et compléter le tableau, tour après tour, jusqu'à la valeur renvoyée.

    Au premier tour, r prend 10 × 0 + 6, soit \(6\), et n devient \(202\). Chaque tour fait passer le dernier chiffre de n à la fin de r :

    $$ r : 0 \rightarrow 6 \rightarrow 62 \rightarrow 620 \rightarrow 6202 $$

    n vaut alors \(0\), la boucle s'arrête, et la fonction renvoie \(6202\).

  2. La fonction palindrome ajoute à n son retourné, jusqu'à obtenir un nombre qui se lit de la même façon dans les deux sens : 
    def palindrome(n):
    etapes = 0
    while n != retourne(n):
        n = n + retourne(n)
        etapes = etapes + 1
    return n, etapes
    Dérouler les appels palindrome(87) et palindrome(59) : compléter les tableaux, jusqu'au couple renvoyé.
    Deux tableaux de suivi, pour palindrome(87) et palindrome(59), colonnes étape, n et retourne(n), étapes 0 à 4 : seule la valeur de départ de n est écrite, et une case attend le couple renvoyé palindrome(87) étape n retourne(n) 0 87 1 2 3 4 renvoie palindrome(59) étape n retourne(n) 0 59 1 2 3 4 renvoie
    $$ 87 + 78 = 165 \quad 165 + 561 = 726 \quad 726 + 627 = 1353 \quad 1353 + 3531 = 4884 $$
    $$ 59 + 95 = 154 \quad 154 + 451 = 605 \quad 605 + 506 = 1111 $$

    4884 et 1111 se lisent dans les deux sens : palindrome(87) renvoie (4884, 4), et palindrome(59) renvoie (1111, 3).

    Les deux suivis complétés. palindrome(87) : 87, 165, 726, 1353 puis 4884, renvoie (4884, 4). palindrome(59) : 59, 154, 605 puis 1111, renvoie (1111, 3) palindrome(87) étape n retourne(n) 0 87 78 1 165 561 2 726 627 3 1353 3531 4 4884 4884 renvoie (4884, 4) palindrome(59) étape n retourne(n) 0 59 95 1 154 451 2 605 506 3 1111 1111 4 renvoie (1111, 3)
  3. Expliquer pourquoi la boucle de retourne s'arrête toujours quand n est un entier positif.

    À chaque tour, n est remplacé par n // 10, un entier positif strictement plus petit que n : n perd son dernier chiffre. Après autant de tours que n a de chiffres, n vaut \(0\), la condition n > 0 est fausse, et la boucle s'arrête.

  4. Avec \(196\), personne n'a jamais vu la boucle de palindrome s'arrêter. Modifier la ligne du while pour que la fonction s'arrête au bout de \(50\) étapes au plus.
        while n != retourne(n) and etapes < 50:

    La boucle s'arrête dès que n est un palindrome, ou quand etapes atteint \(50\).

La ligne qui se dessine

Une ligne de cases blanches « . » et noires « # » donne la suivante : chaque case regarde ses deux voisines. En Python, (0 - 1) % n vaut n - 1 : la première case a pour voisine de gauche la dernière, comme si la ligne était refermée en anneau.

def suivante(ligne):
    n = len(ligne)
    nv = ""
    for k in range(n):
        g = ligne[(k - 1) % n]
        d = ligne[(k + 1) % n]
        if g != d:
            nv = nv + "#"
        else:
            nv = nv + "."
    return nv

ligne = "........#........"
for t in range(8):
    print(ligne)
    ligne = suivante(ligne)
La ligne "#....", ses cinq cases de rang 0 à 4, au-dessus d'un tableau à compléter, colonnes k, g, d et nv, une ligne pour chaque k de 0 à 4 0 # 1 . 2 . 3 . 4 . k g d nv 0 1 2 3 4
Le suivi de suivante("#....") complété : la case 0 a pour voisines la case 4 et la case 1, toutes deux blanches ; nv devient ".", ".#", ".#.", ".#..", puis ".#..#", la ligne renvoyée 0 # 1 . 2 . 3 . 4 . k g d nv 0 "." "." "." 1 "#" "." ".#" 2 "." "." ".#." 3 "." "." ".#.." 4 "." "#" ".#..#"
  1. Dérouler l'appel suivante("#....") et compléter le tableau, tour après tour : g et d sont les voisines de gauche et de droite de la case k.

    Pour \(k = 0\), (0 - 1) % 5 vaut \(4\) : les voisines sont les cases \(4\) et \(1\), toutes deux blanches, et la case devient blanche. Pour \(k = 4\), les voisines sont les cases \(3\) et \(0\) : l'une est noire, l'autre non, et la case devient noire.

    La fonction renvoie ".#..#".

  2. Noircir, ligne après ligne, les cases « # » que le programme affiche, de \(t = 0\) à \(t = 7\).
    Une grille de 17 cases de large, rangs 0 à 16, et de 10 lignes, t = 0 à 9 : sur la ligne 0, seule la case 8 est noircie ; un trait épais sépare les lignes 8 et 9 des autres t = 0 t = 1 t = 2 t = 3 t = 4 t = 5 t = 6 t = 7 t = 8 t = 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

    Au départ, seule la case \(8\) est noire : à la ligne suivante, ses voisines \(7\) et \(9\) noircissent, et elle blanchit. Les lignes dessinent un triangle fait de triangles, le triangle de Sierpinski.

    La grille complétée : les lignes 0 à 7 dessinent un triangle fait de triangles, symétrique par rapport à la case 8. Ligne 8 : cases 0 et 16. Ligne 9 : cases 0, 1, 15 et 16 t = 0 t = 1 t = 2 t = 3 t = 4 t = 5 t = 6 t = 7 t = 8 t = 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  3. Expliquer pourquoi chaque ligne affichée est symétrique par rapport à sa case \(8\).

    La règle compare les deux voisines sans distinguer la gauche de la droite : échanger les deux ne change pas la case. La ligne de départ est symétrique par rapport à la case \(8\).

    Si une ligne est symétrique, les cases \(8 - d\) et \(8 + d\) ont des voisines qui se correspondent dans la symétrie, donc la même couleur à la ligne suivante : la symétrie passe d'une ligne à la suivante, jusqu'à la dernière.

  4. On remplace range(8) par range(10). Noircir les lignes \(t = 8\) et \(t = 9\) de la grille, puis expliquer ce qui arrive aux cases des bords.

    À la ligne \(8\), le triangle touche les bords : seules les cases \(0\) et \(16\) sont noires.

    La ligne est refermée en anneau : la case \(0\) a pour voisine de gauche la case \(16\). À la ligne \(9\), les cases \(0\), \(1\), \(15\) et \(16\) sont noires : le dessin passe d'un bord à l'autre.