Moon Arrows Sun
Arrows
Return Retour
Accueil Home
Imprimer

Les casse-tête des programmes

Des briques à remettre dans l'ordre, des machines à calculer mystères, la tour de Hanoï et un minigolf : quatre casse-tête pour lire, écrire et dérouler des programmes.

Les mêmes briques

Un lutin se déplace de case en case sur un quadrillage. Le triangle bleu montre sa case de départ et la direction où il regarde ; le point rouge marque son arrivée. Pour tourner, il pivote sur place, vers sa droite ou vers sa gauche.

Les figures 1, 2 et 3 se tracent chacune avec les cinq briques, en utilisant chaque brique une seule fois.

Cinq briques lettrées : a, avancer de 3 cases ; b, tourner de 90° vers la droite ; c, avancer d'une case ; d, tourner de 90° vers la gauche ; e, avancer de 2 cases. Quatre quadrillages de six cases sur six. Figure 1 : le lutin part vers le haut, monte de 2, va de 3 vers la droite, monte de 1. Figure 2 : il part vers la droite, va de 3 vers la droite, monte de 1, va de 2 vers la droite. Figure 3 : il part vers le bas, descend de 1, va de 2 vers la gauche, descend de 3. Figure 4 : il part vers le haut, monte de 3, va de 2 vers la gauche, descend de 1. Sous les figures 1 à 3, cinq cases pour écrire les lettres a avancer de 3 cases b tourner de 90° vers la droite c avancer d'une case d tourner de 90° vers la gauche e avancer de 2 cases Figure 1 Figure 2 Figure 3 Figure 4
Les programmes retrouvés. Figure 1 : e, b, a, d, c. Figure 2 : a, d, c, b, e. Figure 3 : c, b, e, d, a. La figure 4 tourne deux fois à gauche : elle ne se trace pas avec les cinq briques a avancer de 3 cases b tourner de 90° vers la droite c avancer d'une case d tourner de 90° vers la gauche e avancer de 2 cases Figure 1 e b a d c Figure 2 a d c b e Figure 3 c b e d a Figure 4 impossible
  1. Écrire sous les figures 1, 2 et 3 les lettres des cinq briques, dans l'ordre où le lutin les exécute.

    Le lutin avance, tourne, avance, tourne, avance : on lit la longueur de chaque segment, puis le sens de chaque virage, vu par le lutin.

    Figure 3 : le lutin regarde vers le bas. Pour partir vers la gauche de la feuille, il tourne à sa droite : c'est la brique b.

    Figure 1 : e, b, a, d, c

    Figure 2 : a, d, c, b, e

    Figure 3 : c, b, e, d, a

  2. La figure 4 ne se trace pas avec ces cinq briques. Expliquer pourquoi.

    Au premier virage, le lutin regarde vers le haut et part vers la gauche : il tourne à sa gauche. Au second, il regarde vers la gauche et part vers le bas : il tourne encore à sa gauche.

    Il faudrait deux briques « tourner de \(90 \ [°]\) vers la gauche » ; il n'y en a qu'une.

Les machines mystères

Quatre machines à calculer ont le même programme : elles demandent un nombre \(n\), font deux calculs, puis affichent le résultat. Leurs deux calculs sont effacés, mais on connaît trois essais de chaque machine.

Les huit calculs effacés sont les huit opérations du stock, et chaque opération sert une seule fois.

Un stock de huit opérations : fois 2, plus 1, moins 3, fois 4, plus 5, divisé par 2, moins 2, fois 3. Quatre machines au même programme : demander n ; calculer n suivi d'une case vide ; calculer le résultat suivi d'une case vide ; afficher le résultat. Machine 1 : 1 donne 12, 3 donne 16, 6 donne 22. Machine 2 : 2 donne 4, 5 donne 13, 9 donne 25. Machine 3 : 4 donne 4, 6 donne 12, 10 donne 28. Machine 4 : 2 donne 2, 8 donne 5, 12 donne 7. × 2 + 1 − 3 × 4 + 5 ÷ 2 − 2 × 3 Machine 1 demander [ n ] calculer [ n ] calculer [ résultat ] afficher [ résultat ] entrée sortie 1 12 3 16 6 22 Machine 2 demander [ n ] calculer [ n ] calculer [ résultat ] afficher [ résultat ] entrée sortie 2 4 5 13 9 25 Machine 3 demander [ n ] calculer [ n ] calculer [ résultat ] afficher [ résultat ] entrée sortie 4 4 6 12 10 28 Machine 4 demander [ n ] calculer [ n ] calculer [ résultat ] afficher [ résultat ] entrée sortie 2 2 8 5 12 7
Les machines retrouvées. Machine 1 : plus 5, puis fois 2. Machine 2 : fois 3, puis moins 2. Machine 3 : moins 3, puis fois 4. Machine 4 : divisé par 2, puis plus 1 × 2 + 1 − 3 × 4 + 5 ÷ 2 − 2 × 3 Machine 1 demander [ n ] calculer [ n ] + 5 calculer [ résultat ] × 2 afficher [ résultat ] entrée sortie 1 12 3 16 6 22 Machine 2 demander [ n ] calculer [ n ] × 3 calculer [ résultat ] − 2 afficher [ résultat ] entrée sortie 2 4 5 13 9 25 Machine 3 demander [ n ] calculer [ n ] − 3 calculer [ résultat ] × 4 afficher [ résultat ] entrée sortie 4 4 6 12 10 28 Machine 4 demander [ n ] calculer [ n ] ÷ 2 calculer [ résultat ] + 1 afficher [ résultat ] entrée sortie 2 2 8 5 12 7
  1. Retrouver les deux calculs de chaque machine, en écrivant une opération du stock dans chaque case vide.

    Machine 1 : quand l'entrée augmente de \(2\), la sortie augmente de \(4\) ; la machine multiplie par \(2\), après avoir ajouté \(5\). Pour l'entrée \(1\) : \(1 + 5 = 6\), puis \(6 \times 2 = 12\).

    Machine 2 : \(2 \times 3 = 6\), puis \(6 - 2 = 4\). Machine 3 : \(4 - 3 = 1\), puis \(1 \times 4 = 4\). Machine 4 : \(2 \div 2 = 1\), puis \(1 + 1 = 2\).

    Les huit opérations du stock sont toutes placées, chacune une fois.

  2. Traduire chaque machine en une seule instruction « calculer » qui part de l'entrée \(n\).

    Quand l'addition ou la soustraction passe en premier, des parenthèses l'imposent.

    $$ \begin{array}{ll} \text{machine 1 :} & \text{calculer} \ \Bigl[ (n + 5) \times 2 \Bigr] \\ \text{machine 2 :} & \text{calculer} \ \Bigl[ n \times 3 - 2 \Bigr] \\ \text{machine 3 :} & \text{calculer} \ \Bigl[ (n - 3) \times 4 \Bigr] \\ \text{machine 4 :} & \text{calculer} \ \Bigl[ n \div 2 + 1 \Bigr] \end{array} $$
  3. On revient à la machine 1. Hugo la traduit par calculer \(\Bigl[\) \(n + 5 \times 2\) \(\Bigr]\). Calculer ce que donne son instruction pour l'entrée \(1\), puis expliquer son erreur.

    La multiplication passe avant l'addition : \(1 + 5 \times 2 = 1 + 10 = 11\), et non \(12\).

    La machine 1 ajoute \(5\) avant de multiplier : il faut des parenthèses, \((n + 5) \times 2\).

La tour de Hanoï

En 1883, le mathématicien Édouard Lucas invente la tour de Hanoï : une tour de disques, du plus grand au plus petit, à reconstruire sur un autre piquet. On ne déplace qu'un disque à la fois, celui du dessus, et on ne pose jamais un disque sur un plus petit.

Un robot suit le programme ci-dessous. « Vers la droite » veut dire de A vers B, de B vers C, et de C on revient en A ; « l'autre déplacement permis » est le seul déplacement possible qui ne touche pas au petit disque.

Le programme du robot : répéter 3 fois, déplacer le petit disque d'un piquet vers la droite, puis faire l'autre déplacement permis ; enfin, déplacer le petit disque d'un piquet vers la droite. Huit dessins de trois piquets : le départ, tour de trois disques sur le piquet A, puis sept dessins vides, un après chaque déplacement répéter 3 fois : déplacer le petit disque d'un piquet vers la droite faire l'autre déplacement permis déplacer le petit disque d'un piquet vers la droite départ A B C après le déplacement 1 A B C après le déplacement 2 A B C après le déplacement 3 A B C après le déplacement 4 A B C après le déplacement 5 A B C après le déplacement 6 A B C après le déplacement 7 A B C
Le programme du robot : répéter 3 fois, déplacer le petit disque d'un piquet vers la droite, puis faire l'autre déplacement permis ; enfin, déplacer le petit disque d'un piquet vers la droite. Les sept déplacements : 1, le disque P de A vers B ; 2, le disque M de A vers C ; 3, le disque P de B vers C ; 4, le disque G de A vers B ; 5, le disque P de C vers A ; 6, le disque M de C vers B ; 7, le disque P de A vers B. La tour arrive sur le piquet B répéter 3 fois : déplacer le petit disque d'un piquet vers la droite faire l'autre déplacement permis déplacer le petit disque d'un piquet vers la droite départ A B C après le déplacement 1 A B C après le déplacement 2 A B C après le déplacement 3 A B C après le déplacement 4 A B C après le déplacement 5 A B C après le déplacement 6 A B C après le déplacement 7 A B C
  1. Dérouler le programme pour la tour de trois disques, en dessinant les disques après chaque déplacement. Sur quel piquet la tour arrive-t-elle ?

    On note P, M et G le petit, le moyen et le grand disque. 1 : P de A vers B ; 2 : M de A vers C ; 3 : P de B vers C ; 4 : G de A vers B ; 5 : P de C vers A ; 6 : M de C vers B ; 7 : P de A vers B.

    Le programme s'arrête quand la tour est reconstruite, sans un déplacement de trop.

    La tour arrive sur le piquet B, en \(7\) déplacements.

  2. On passe à une tour de quatre disques : il faut \(15\) déplacements. Calculer combien de fois le robot répète la boucle, en justifiant.

    Chaque tour de boucle fait deux déplacements, et le dernier déplacement du petit disque en ajoute un : pour trois disques, \(3 \times 2 + 1 = 7\).

    $$ 15 - 1 = 14 \quad \text{et} \quad 14 \div 2 = 7 $$

    Le robot répète la boucle \(7\) fois.

  3. On passe au calcul du nombre de déplacements. Au départ, le résultat vaut \(0\) ; ce programme calcule le nombre de déplacements pour une tour de six disques. Dérouler le programme en écrivant le résultat après chaque tour de boucle, puis entourer les deux résultats déjà trouvés aux questions 1 et 2. Combien de déplacements faut-il pour six disques ?
    Le programme : répéter 6 fois, calculer le résultat fois 2 plus 1 ; puis afficher le résultat. À côté, un tableau : après les tours 1 à 6, une case vide pour le résultat répéter 6 fois : calculer [ résultat × 2 + 1 ] afficher [ résultat ] après le tour résultat 1 2 3 4 5 6
    Le déroulement : après les tours 1 à 6, le résultat vaut 1, 3, 7, 15, 31 et 63 ; 7 et 15 sont entourés répéter 6 fois : calculer [ résultat × 2 + 1 ] afficher [ résultat ] après le tour résultat 1 1 2 3 3 7 4 15 5 31 6 63

    Après le tour \(3\), on retrouve les \(7\) déplacements de trois disques ; après le tour \(4\), les \(15\) de quatre disques.

    Il faut \(63\) déplacements pour six disques.

Le minigolf du lutin

Au minigolf du collège, la balle est un lutin : elle part dans la direction de la flèche bleue, suit son programme, et tombe dans le trou si le programme est juste. Les deux parcours sont en vraie grandeur.

« Tourner de \(60 \ [°]\) » : l'angle se mesure entre le prolongement du côté qu'on vient de tracer et le côté suivant.

Deux parcours de minigolf en vraie grandeur. Trou 1 : programme répéter 3 fois, avancer de 4 cm, tourner de 60° vers la gauche ; la balle part vers le haut, un étang au milieu, le trou à gauche. Trou 2 : programme répéter … fois, avancer de 3.5 cm, tourner de … vers la droite ; la balle part vers la droite, un étang au milieu, le trou à gauche répéter 3 fois : avancer de 4 cm tourner de 60° vers la gauche répéter …… fois : avancer de 3.5 cm tourner de …… vers la droite Trou 1 étang départ Trou 2 étang départ
Les deux trajets tracés en vraie grandeur. Trou 1 : trois côtés de 4 cm, en tournant de 60° vers la gauche à chaque sommet, autour de l'étang ; la balle tombe dans le trou. Trou 2 : quatre côtés de 3.5 cm, en tournant de 72° vers la droite ; la balle tombe dans le trou. En bleu, les prolongements des côtés et les angles mesurés répéter 3 fois : avancer de 4 cm tourner de 60° vers la gauche répéter 4 fois : avancer de 3.5 cm tourner de 72° vers la droite Trou 1 étang 60° 60° départ Trou 2 étang 72° 72° 72° départ
  1. Tracer, à la règle et au rapporteur, le trajet de la balle au trou 1.

    À chaque sommet, on prolonge le côté tracé et on mesure \(60 \ [°]\) vers la gauche : deux côtés du trajet font entre eux un angle de \(120 \ [°]\). Après trois côtés, la balle tombe dans le trou.

    Mesurer \(60 \ [°]\) entre les deux côtés ferait tourner la balle de \(120 \ [°]\) : elle manquerait le trou.

  2. On passe au trou 2. Ses côtés mesurent \(3.5 \ \text{cm}\), et la balle tourne toujours du même angle vers la droite : prolongé au-delà du trou, son trajet reviendrait au départ au bout de cinq côtés, en dessinant un pentagone régulier. Calculer l'angle dont la balle tourne à chaque sommet, en justifiant.

    En cinq virages, la balle fait un tour complet sur elle-même : \(360 \ [°]\), partagés en cinq virages égaux.

    $$ 360 \ [°] \div 5 = 72 \ [°] $$
  3. Tracer le trajet du trou 2, côté après côté, jusqu'à ce que la balle tombe dans le trou, puis compléter son programme.

    La balle tombe dans le trou au bout de quatre côtés : la boucle se répète quatre fois.

    répéter \(4\) fois : \(\Bigl[\) avancer de \(3.5 \ \text{cm}\) ; tourner de \(72 \ [°]\) vers la droite \(\Bigr]\)