Problèmes sur la pensée informatique

Le programme mystère

Un programme demande \(\Bigl[\) un nombre \(\Bigr]\), puis calcule \(\Bigl[\) le nombre \(\times \ 4 \Bigr]\), puis \(\Bigl[\) le résultat \(- \ 6 \Bigr]\), et l'affiche.

1. Quelle est l'entrée du programme ? Quelle est sa sortie ?

   L'entrée est le nombre saisi ; la sortie est le nombre affiché à la fin.

2. Quelle est la sortie pour l'entrée \(7\) ? Détailler les étapes.
   $$ 7 \times 4 = 28 \hspace{2em} \text{puis} \hspace{2em} 28 - 6 $$

   $$ 22 $$
3. Écrire l'expression littérale calculée par ce programme, en notant \(x\) le nombre saisi.
   $$ 4x - 6 $$
4. Quelle entrée donne la sortie \(0\) ?

   On remonte le programme en défaisant chaque opération :

   $$ 0 + 6 = 6 \hspace{2em} \text{puis} \hspace{2em} 6 \div 4 $$

   $$ 1.5 $$

   On vérifie : \(1.5 \times 4 - 6 = 6 - 6 = 0\).

Le tracé du polygone

Un lutin doit tracer un hexagone régulier de \(4 \ \text{cm}\) de côté.

1. Quel angle le lutin doit-il tourner à chaque sommet ?

   Après avoir parcouru toute la figure, il a effectué un tour complet en six fois.

   $$ 360° \div 6 $$

   $$ 60° $$
2. Écrire le programme à l'aide d'une boucle.

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

3. Combien d'instructions faudrait-il pour écrire ce même programme sans boucle ?

   Chaque côté demande deux instructions, avancer puis tourner :

   $$ 6 \times 2 $$

   $$ 12 \ \text{instructions} $$
4. Quel est le périmètre de la figure tracée ?
   $$ 6 \times 4 $$

   $$ 24 \ \text{cm} $$

Corriger un programme

Un élève veut calculer l'aire d'un triangle. Il écrit : demander \(\Bigl[\) la base \(\Bigr]\) ; demander \(\Bigl[\) la hauteur \(\Bigr]\) ; calculer \(\Bigl[\) base \(\times\) hauteur \(\div \ 2 \Bigr]\).

1. Combien ce programme a-t-il d'entrées ?

   Le programme demande la base, puis la hauteur.

   $$ 2 \ \text{entrées} $$
2. Tester ce programme avec une base de \(8\) et une hauteur de \(5\).
   $$ 8 \times 5 \div 2 = 40 \div 2 $$

   $$ 20 $$

   Le programme est correct : la multiplication et la division se traitent de gauche à droite.

3. Un camarade écrit \(\Bigl[\) base \(\times\) hauteur \(+ \ 2 \Bigr]\). Son programme donne-t-il le bon résultat ? Que faut-il corriger ?
   $$ 8 \times 5 + 2 = 42 $$

   Il obtient \(42\) au lieu de \(20\) : il a écrit une addition là où il fallait une division. L'instruction correcte est \(\Bigl[\) base \(\times\) hauteur \(\div \ 2 \Bigr]\).

Deux programmes équivalents ?

Programme A : demander \(\Bigl[\) un nombre \(\Bigr]\) ; calculer \(\Bigl[\) le nombre \(+ \ 3 \Bigr]\) ; calculer \(\Bigl[\) le résultat \(\times \ 2 \Bigr]\).

Programme B : demander \(\Bigl[\) un nombre \(\Bigr]\) ; calculer \(\Bigl[\) le nombre \(\times \ 2 \Bigr]\) ; calculer \(\Bigl[\) le résultat \(+ \ 3 \Bigr]\).

1. Appliquer les deux programmes à l'entrée \(5\).
   $$ A : \ (5 + 3) \times 2 = 8 \times 2 \hspace{2em} B : \ 5 \times 2 + 3 = 10 + 3 $$

   $$ A : \ 16 \hspace{2em} B : \ 13 $$
2. Les deux programmes sont-ils équivalents ? Écrire l'expression littérale de chacun, en notant \(x\) le nombre saisi.
   $$ A : \ 2(x + 3) = 2x + 6 \hspace{2em} B : \ 2x + 3 $$

   Les deux expressions diffèrent, donc les programmes ne sont pas équivalents. L'ordre des instructions change le résultat.

3. Quelle instruction faudrait-il changer dans le programme B pour qu'il devienne équivalent au programme A ?

   Puisque \(2(x + 3) = 2x + 6\), il faut ajouter \(6\) et non \(3\) : remplacer \(\Bigl[\) le résultat \(+ \ 3 \Bigr]\) par \(\Bigl[\) le résultat \(+ \ 6 \Bigr]\).

Du programme à la figure

1. Un lutin exécute : répéter \(8\) fois \(\Bigl[\) avancer de \(3 \ \text{cm}\) ; tourner de \(45°\) vers la droite \(\Bigr]\). Dire quelle figure il obtient et donner son périmètre, puis expliquer ce qui prouve que la figure se referme.

   Le lutin trace \(8\) côtés de même longueur et tourne \(8\) fois du même angle. En tout, il a tourné de :

   $$ 8 \times 45° = 360° $$

   Il revient donc à son point de départ, dans sa direction de départ : la figure est fermée.

   $$ \text{un octogone régulier} $$

   $$ 8 \times 3 $$

   $$ 24 \ \text{cm} $$
2. On change de programme : pour tracer un triangle équilatéral de \(5 \ \text{cm}\) de côté, Léo écrit répéter \(3\) fois \(\Bigl[\) avancer de \(5 \ \text{cm}\) ; tourner de \(60°\) vers la droite \(\Bigr]\). Que trace son lutin ? Corriger le programme.

   Léo a indiqué l'angle du triangle, pas l'angle dont il faut tourner. Le lutin ne tourne que de \(3 \times 60° = 180°\) en tout : il trace trois côtés d'un hexagone, et la figure ne se ferme pas.

   Pour revenir au départ en trois fois, il faut tourner de \(360° \div 3 = 120°\) :

   Répéter \(3\) fois : \(\Bigl[\) avancer de \(5 \ \text{cm}\) ; tourner de \(120°\) vers la droite \(\Bigr]\)

Le robot et le trésor

Un robot se déplace sur le quadrillage ci-dessous. Il part de la case \(\mathrm{A1}\) et regarde vers la droite. Il connaît trois instructions : « avancer d'une case », « tourner à gauche » et « tourner à droite » ; tourner le fait pivoter d'un quart de tour sur place. Il doit atteindre le trésor en \(\mathrm{E5}\), sans jamais entrer dans une case grisée ni sortir du quadrillage.

Deux élèves proposent chacun un programme :

Programme 1 : répéter \(4\) fois \(\Bigl[\) avancer ; tourner à gauche ; avancer ; tourner à droite \(\Bigr]\).

Programme 2 : répéter \(4\) fois \(\Bigl[\) tourner à gauche ; avancer ; tourner à droite ; avancer \(\Bigr]\).

1. Dérouler le programme 1 case par case. Que se passe-t-il ?

   Premier passage dans la boucle : le robot avance en \(\mathrm{B1}\), se tourne vers le haut, avance en \(\mathrm{B2}\), puis se tourne à nouveau vers la droite.

   Deuxième passage : il devrait avancer en \(\mathrm{C2}\), qui est une case grisée.

   $$ \text{le robot est bloqué devant } \mathrm{C2} $$
2. Dérouler le programme 2 case par case. Le robot atteint-il le trésor ?

   À chaque passage dans la boucle, le robot monte d'une case puis avance d'une case vers la droite. Il passe par :

   $$ \mathrm{A2} \ ; \ \mathrm{B2} \ ; \ \mathrm{B3} \ ; \ \mathrm{C3} \ ; \ \mathrm{C4} \ ; \ \mathrm{D4} \ ; \ \mathrm{D5} \ ; \ \mathrm{E5} $$

   Aucune de ces cases n'est grisée :

   $$ \text{le robot atteint le trésor en } \mathrm{E5} $$
3. Toujours avec le programme 2, sur quelle case s'arrêterait le robot si l'on remplaçait « répéter \(4\) fois » par « répéter \(3\) fois » ?

   Chaque passage fait gagner une case vers le haut et une case vers la droite. Après trois passages depuis \(\mathrm{A1}\), le robot est trois colonnes plus à droite et trois lignes plus haut.

   $$ \mathrm{D4} $$
4. Comparer les instructions des deux programmes. Qu'est-ce qui les distingue ? Qu'en conclure ?

   Les deux boucles contiennent exactement les mêmes quatre instructions, deux « avancer », un « tourner à gauche » et un « tourner à droite ». Seul leur ordre change : le programme 1 avance avant de monter, le programme 2 monte avant d'avancer.

   L'ordre des instructions compte : les mêmes instructions dans un autre ordre ne mènent pas au même endroit.

L'étoile du lutin

Un lutin part du point bleu, tourné vers la droite, et exécute : répéter \(5\) fois \(\Bigl[\) avancer de \(5 \ \text{cm}\) ; tourner de \(144°\) vers la droite \(\Bigr]\). Il trace cette étoile.

1. Prévoir l'angle formé à chaque pointe de l'étoile, puis le vérifier au rapporteur. De combien de degrés le lutin a-t-il tourné en tout ?

   À chaque pointe, le nouveau côté fait un angle de \(144°\) avec le prolongement du côté qui arrive. Avec le côté qui arrive lui-même, il forme l'angle qui complète \(144°\) à \(180°\) :

   $$ 180° - 144° $$

   $$ 36° $$

   Au rapporteur, chaque pointe mesure bien \(36°\). En tout, le lutin a tourné de :

   $$ 5 \times 144° = 720° = 2 \times 360° $$

   $$ 2 \ \text{tours complets} $$
2. On change de programme : le lutin exécute répéter \(12\) fois \(\Bigl[\) avancer de \(4 \ \text{cm}\) ; tourner de \(a°\) vers la droite \(\Bigr]\), où \(a\) est un nombre entier compris entre \(0\) et \(180\), ces deux valeurs exclues. Trouver toutes les valeurs de \(a\) pour lesquelles le lutin termine tourné dans sa direction de départ, et prouver qu'il n'y en a pas d'autre.

   Le lutin retrouve sa direction de départ lorsqu'il a tourné d'un nombre entier de tours : \(12 \times a\) doit être un multiple de \(360\). Comme \(a\) est plus petit que \(180\), \(12 \times a\) est plus petit que \(12 \times 180 = 2 \ 160 = 6 \times 360\) : le lutin fait au plus \(5\) tours.

   $$ 12 \times a = 360 \quad \text{ou} \quad 720 \quad \text{ou} \quad 1 \ 080 \quad \text{ou} \quad 1 \ 440 \quad \text{ou} \quad 1 \ 800 $$

   On divise chacun de ces multiples par \(12\) ; il n'y a pas d'autre possibilité :

   $$ a = 30 \quad \text{ou} \quad 60 \quad \text{ou} \quad 90 \quad \text{ou} \quad 120 \quad \text{ou} \quad 150 $$
3. Pour chacun de ces angles, quelle figure ce programme trace-t-il ? Écrire le programme le plus court qui trace la même figure.

   La figure se referme dès que le lutin a tourné d'un nombre entier de tours ; les répétitions suivantes repassent sur les mêmes côtés. Pour \(60°\), c'est au bout de \(6\) répétitions, car \(6 \times 60° = 360°\).

   Angle	Tours en \(12\) répétitions	Figure tracée	Répétitions utiles
   \(30°\)	\(1\)	polygone régulier à \(12\) côtés	\(12\)
   \(60°\)	\(2\)	hexagone régulier parcouru \(2\) fois	\(6\)
   \(90°\)	\(3\)	carré parcouru \(3\) fois	\(4\)
   \(120°\)	\(4\)	triangle équilatéral parcouru \(4\) fois	\(3\)
   \(150°\)	\(5\)	étoile à \(12\) pointes	\(12\)

   Pour \(150°\), il faut que \(150 \times r\) soit un multiple de \(360\) ; en divisant par \(30\), que \(5 \times r\) soit un multiple de \(12\), ce qui n'arrive pas pour \(r\) de \(1\) à \(11\). Les \(12\) répétitions sont nécessaires, comme pour \(30°\). Dans les trois autres cas, on garde le même bloc et on réduit le nombre de répétitions :

   $$ 60° : \ \text{répéter } 6 \ \text{fois} \hspace{2em} 90° : \ \text{répéter } 4 \ \text{fois} \hspace{2em} 120° : \ \text{répéter } 3 \ \text{fois} $$
4. On change de figure : Léa veut tracer une étoile à \(9\) pointes d'un seul trait, sans repasser sur un côté, avec un programme répéter \(9\) fois \(\Bigl[\) avancer de \(4 \ \text{cm}\) ; tourner de \(a°\) vers la droite \(\Bigr]\). Trouver tous les angles entiers \(a\), compris entre \(0\) et \(180\), qui conviennent.

   Comme à la question 2, \(9 \times a\) doit être un multiple de \(360\), plus petit que \(9 \times 180 = 1 \ 620\) :

   $$ 9 \times a = 360 \quad \text{ou} \quad 720 \quad \text{ou} \quad 1 \ 080 \quad \text{ou} \quad 1 \ 440 $$

   $$ a = 40 \quad \text{ou} \quad 80 \quad \text{ou} \quad 120 \quad \text{ou} \quad 160 $$

   Pour \(40°\) : un seul tour en neuf fois, le lutin trace un polygone régulier à \(9\) côtés, pas une étoile.

   Pour \(120°\) : le lutin a fait un tour dès la troisième répétition ; il parcourt trois fois le même triangle équilatéral.

   Pour \(80°\) et \(160°\) : les produits \(80 \times r\) et \(160 \times r\), pour \(r\) de \(1\) à \(8\), ne sont jamais des multiples de \(360\). La figure ne se referme qu'à la neuvième répétition, et ses neuf côtés sont tous différents.

   $$ a = 80 \quad \text{ou} \quad a = 160 $$

   Vérification en exécutant les deux programmes : ils tracent deux étoiles à \(9\) pointes différentes.

Le code du cadenas

Inès obtient le code de son cadenas en saisissant un nombre entier dans ce programme. Au départ, le résultat est le nombre saisi.

1. Dérouler le programme pour l'entrée \(4\), instruction par instruction.

   Passage dans la boucle	\(1\)	\(2\)	\(3\)
   Après \(\times \ 2\)	\(8\)	\(22\)	\(50\)
   Après \(+ \ 3\)	\(11\)	\(25\)	\(53\)

   $$ 53 $$
2. Le code d'Inès est \(237\). Retrouver le nombre qu'elle a saisi.

   On remonte le programme depuis la fin : chaque passage se défait en retranchant \(3\), puis en divisant par \(2\).

   $$ 237 - 3 = 234 \hspace{2em} 234 \div 2 = 117 $$

   $$ 117 - 3 = 114 \hspace{2em} 114 \div 2 = 57 $$

   $$ 57 - 3 = 54 \hspace{2em} 54 \div 2 = 27 $$

   $$ 27 $$

   Vérification en exécutant le programme : \(27 \rightarrow 54 \rightarrow 57 \rightarrow 114 \rightarrow 117 \rightarrow 234 \rightarrow 237\).

3. Son frère voudrait le code \(100\). Prouver qu'aucun nombre entier saisi ne donne ce code.

   En partant d'un nombre entier, tous les résultats restent entiers. La dernière instruction ajoute \(3\) au double d'un nombre entier : un nombre pair, plus \(3\), donne un nombre impair.

   $$ \text{le code est toujours impair, jamais } 100 $$

   Le mot « entier » compte : en saisissant \(9.875\), on obtiendrait bien \(100\).

4. Écrire un programme sans boucle, avec seulement deux instructions de calcul, qui affiche toujours le même code que celui d'Inès. Vérifier avec les entrées \(4\) et \(27\).

   On note \(x\) le nombre saisi et on écrit le résultat après chaque passage dans la boucle :

   $$ 2x + 3 $$

   $$ 2(2x + 3) + 3 = 4x + 6 + 3 = 4x + 9 $$

   $$ 2(4x + 9) + 3 = 8x + 18 + 3 = 8x + 21 $$

   Le programme calcule donc \(8x + 21\) :

   Demander \(\Bigl[\) un nombre \(\Bigr]\) ; calculer \(\Bigl[\) le nombre \(\times \ 8 \Bigr]\) ; calculer \(\Bigl[\) le résultat \(+ \ 21 \Bigr]\)

   Vérification : \(8 \times 4 + 21 = 53\) et \(8 \times 27 + 21 = 237\), comme aux questions 1 et 2.