Moon Arrows Sun
Arrows
Return Retour
Accueil Home
Imprimer

Problèmes sur la pensée informatique

Un robot livreur, un tracé de figure, un mur à contourner : le programme fait ce qu'on écrit, pas ce qu'on voulait écrire.

Ces problèmes se traitent sans machine. On se repère sur un quadrillage dont les colonnes vont de \(\mathrm{A}\) à \(\mathrm{H}\) et les lignes de \(1\) à \(8\).

Le robot livreur

Un robot part de la case \(\mathrm{B2}\) et doit livrer un colis en \(\mathrm{F5}\).

  1. De combien de colonnes doit-il se déplacer ? Et de combien de lignes ?

    De \(\mathrm{B}\) à \(\mathrm{F}\), on compte \(\mathrm{C}\), \(\mathrm{D}\), \(\mathrm{E}\), \(\mathrm{F}\), soit \(4\) colonnes. De la ligne \(2\) à la ligne \(5\) :

    $$ 5 - 2 = 3 $$
    $$ 4 \text{ colonnes} \quad \text{et} \quad 3 \text{ lignes} $$
  2. Écrire un programme qui l'amène à destination.

    Avancer de \(4\) vers la droite ; avancer de \(3\) vers le haut

  3. Un camarade propose un autre programme, qui fonctionne aussi. Lequel peut-il avoir écrit ?

    Il suffit d'inverser l'ordre des deux déplacements :

    Avancer de \(3\) vers le haut ; avancer de \(4\) vers la droite

    Le chemin emprunté est différent, mais la case d'arrivée est la même : un chemin n'est jamais unique.

L'ordre des instructions

On compare deux programmes appliqués à un robot posé en \(\mathrm{A1}\), tourné vers la droite.

  1. Exécuter le programme \(1\) pas à pas et donner la case d'arrivée.

    Le robot regarde vers la droite. Il avance de \(3\) : il atteint \(\mathrm{D1}\). Il pivote vers la gauche, donc regarde vers le haut. Il avance de \(2\) :

    $$ \mathrm{D3} $$
  2. Faire de même avec le programme \(2\).

    Le robot pivote d'abord : il regarde vers le haut. Il avance de \(2\), puis encore de \(3\), toujours vers le haut, soit \(5\) cases en tout :

    $$ \mathrm{A6} $$
  3. Que faut-il conclure de la comparaison de ces deux programmes ?

    Les deux programmes contiennent exactement les mêmes instructions, mais dans un ordre différent, et n'aboutissent pas au même endroit. L'ordre fait partie du programme.

Le tracé de figures

  1. Écrire, en utilisant une répétition, le programme qui trace un carré de \(6 \ \text{cm}\) de côté.

    Répéter \(4\) fois : \(\Bigl[\) avancer de \(6 \ \text{cm}\) ; tourner d'un quart de tour vers la droite \(\Bigr]\)

  2. Combien d'instructions seront réellement exécutées ?

    Chaque tour exécute \(2\) instructions, et il y a \(4\) tours :

    $$ 4 \times 2 $$
    $$ 8 \text{ instructions} $$
  3. Adapter le programme pour tracer un triangle équilatéral de \(6 \ \text{cm}\) de côté. Combien d'instructions cette fois ?

    Le triangle a trois côtés, et l'on tourne d'un tiers de tour à chaque sommet :

    Répéter \(3\) fois : \(\Bigl[\) avancer de \(6 \ \text{cm}\) ; tourner d'un tiers de tour vers la droite \(\Bigr]\)

    $$ 3 \times 2 = 6 \text{ instructions} $$

Le programme qui bogue

Un élève veut amener son robot de \(\mathrm{A1}\) à \(\mathrm{E4}\). Il écrit : avancer de \(3\) vers la droite ; avancer de \(3\) vers le haut. Le robot n'arrive pas au bon endroit.

  1. Exécuter son programme pas à pas et donner la case réellement atteinte.
    Étape
    Case atteinte
    Départ
    \(\mathrm{A1}\)
    Avancer de \(3\) à droite
    \(\mathrm{D1}\)
    Avancer de \(3\) vers le haut
    \(\mathrm{D4}\)
    $$ \text{le robot arrive en } \mathrm{D4} $$
  2. À quelle étape le programme dévie-t-il de ce qui était attendu ?

    La ligne d'arrivée est correcte : la seconde instruction est bonne. C'est la première qui est fautive, puisque la colonne atteinte est \(\mathrm{D}\) au lieu de \(\mathrm{E}\).

  3. Corriger le programme.

    De \(\mathrm{A}\) à \(\mathrm{E}\), il faut franchir \(4\) colonnes et non \(3\) :

    Avancer de \(4\) vers la droite ; avancer de \(3\) vers le haut

  4. Quelle méthode générale permet de trouver l'instruction fautive d'un programme ?

    On exécute le programme pas à pas en notant l'état après chaque instruction, puis on compare avec ce qui était attendu. La première différence désigne l'instruction à corriger.

D'où part le robot ?

Un robot a exécuté le programme suivant, et il est arrivé en \(\mathrm{E7}\) :

avancer de \(2\) vers la droite ; avancer de \(3\) vers le haut ; avancer de \(1\) vers la gauche.

Un quadrillage de huit colonnes, de A à H, et de huit lignes ; le robot, un disque, est arrivé en E7
\(\mathrm{A}\)
\(\mathrm{B}\)
\(\mathrm{C}\)
\(\mathrm{D}\)
\(\mathrm{E}\)
\(\mathrm{F}\)
\(\mathrm{G}\)
\(\mathrm{H}\)
\(1\)
\(2\)
\(3\)
\(4\)
\(5\)
\(6\)
\(7\)
\(8\)
  1. Retrouver la case de départ du robot, en expliquant la méthode.

    On remonte le programme à l'envers : on part de la dernière instruction, et chaque déplacement se fait dans le sens contraire.

    Étape
    Case atteinte
    Arrivée
    \(\mathrm{E7}\)
    Défaire « \(1\) vers la gauche » : \(1\) vers la droite
    \(\mathrm{F7}\)
    Défaire « \(3\) vers le haut » : \(3\) vers le bas
    \(\mathrm{F4}\)
    Défaire « \(2\) vers la droite » : \(2\) vers la gauche
    \(\mathrm{D4}\)
    $$ \text{le robot est parti de } \mathrm{D4} $$

    Vérification : de \(\mathrm{D4}\), \(2\) vers la droite donne \(\mathrm{F4}\), \(3\) vers le haut \(\mathrm{F7}\), \(1\) vers la gauche \(\mathrm{E7}\).

  2. Pour ramener le robot de \(\mathrm{E7}\) à son point de départ, Maëlle écrit : avancer de \(1\) vers la gauche ; avancer de \(3\) vers le bas ; avancer de \(2\) vers la droite. Exécuter son programme, puis expliquer son erreur.

    De \(\mathrm{E7}\), le robot de Maëlle passe par \(\mathrm{D7}\), puis \(\mathrm{D4}\), et finit en :

    $$ \mathrm{F4} \quad \text{et non} \quad \mathrm{D4} $$

    Maëlle a bien pris les instructions dans l'ordre inverse, mais elle n'a retourné que le déplacement vertical : elle a oublié de changer le sens des deux déplacements horizontaux. Le bon programme est : avancer de \(1\) vers la droite ; avancer de \(3\) vers le bas ; avancer de \(2\) vers la gauche.

  3. Écrire un programme de seulement deux instructions qui ramène ce même robot de \(\mathrm{E7}\) à \(\mathrm{D4}\).

    De \(\mathrm{E}\) à \(\mathrm{D}\), il y a \(1\) colonne vers la gauche ; de la ligne \(7\) à la ligne \(4\), \(3\) lignes vers le bas :

    Avancer de \(1\) vers la gauche ; avancer de \(3\) vers le bas

Le mur à contourner

Le robot, représenté par un disque, est en \(\mathrm{B2}\). Il doit livrer le colis, représenté par un carré, en \(\mathrm{G6}\). Les cases grisées, de \(\mathrm{D1}\) à \(\mathrm{D5}\), forment un mur : le robot ne peut pas y passer.

Un quadrillage de huit colonnes, de A à H, et de huit lignes ; un mur occupe les cases D1 à D5 ; le robot, un disque, est en B2 ; le colis, un carré, est en G6
\(\mathrm{A}\)
\(\mathrm{B}\)
\(\mathrm{C}\)
\(\mathrm{D}\)
\(\mathrm{E}\)
\(\mathrm{F}\)
\(\mathrm{G}\)
\(\mathrm{H}\)
\(1\)
\(2\)
\(3\)
\(4\)
\(5\)
\(6\)
\(7\)
\(8\)
  1. Le programme « avancer de \(5\) vers la droite ; avancer de \(4\) vers le haut » amène-t-il le robot au colis ? Justifier.

    Sur le papier, il mène bien en \(\mathrm{G6}\). Mais en avançant vers la droite depuis \(\mathrm{B2}\), le robot passe par \(\mathrm{C2}\) puis \(\mathrm{D2}\), qui fait partie du mur.

    $$ \text{Non, le robot est bloqué en } \mathrm{C2} $$
  2. Écrire un programme de deux instructions qui amène le robot au colis sans traverser le mur.

    Le mur s'arrête à la ligne \(5\) : on monte d'abord jusqu'à la ligne \(6\), où la voie est libre.

    Avancer de \(4\) vers le haut ; avancer de \(5\) vers la droite

    Le robot passe par \(\mathrm{B6}\), puis \(\mathrm{C6}\), \(\mathrm{D6}\), \(\mathrm{E6}\), \(\mathrm{F6}\) et arrive en \(\mathrm{G6}\).

  3. Combien de cases le robot doit-il franchir, au minimum, pour aller de \(\mathrm{B2}\) au colis ? Justifier.

    Quel que soit le chemin, il faut changer de colonne \(5\) fois, de \(\mathrm{B}\) à \(\mathrm{G}\), et de ligne \(4\) fois, de \(2\) à \(6\) :

    $$ 5 + 4 $$
    $$ 9 \text{ cases au minimum} $$

    Le programme de la question précédente en franchit exactement \(9\) : il est donc le plus court possible.

  4. La batterie du robot lui permet de franchir \(15\) cases au plus. Peut-il livrer le colis, puis revenir en \(\mathrm{B2}\) sans recharger ? Justifier.

    Le retour demande lui aussi au moins \(9\) cases :

    $$ 9 + 9 = 18 $$

    Or \(18 > 15\) : il peut livrer le colis, mais il lui manquerait au moins \(3\) cases pour revenir.

    $$ \text{Non, il doit recharger} $$

La chasse au trésor

Le robot, représenté par un disque, est en \(\mathrm{A1}\) ; le trésor, représenté par une étoile, est en \(\mathrm{G7}\). Les cases grisées \(\mathrm{C1}\), \(\mathrm{D4}\) et \(\mathrm{A5}\) sont des rochers : le robot ne peut pas y entrer. On cherche un programme de la forme :

Répéter \(\ldots\) fois : \(\Bigl[\) avancer de \(\ldots\) vers la droite ; avancer de \(\ldots\) vers le haut \(\Bigr]\)

On peut aussi échanger les deux instructions du bloc.

Un quadrillage de huit colonnes, de A à H, et de huit lignes ; des rochers occupent les cases C1, D4 et A5 ; le robot, un disque, est en A1 ; le trésor, une étoile, est en G7
\(\mathrm{A}\)
\(\mathrm{B}\)
\(\mathrm{C}\)
\(\mathrm{D}\)
\(\mathrm{E}\)
\(\mathrm{F}\)
\(\mathrm{G}\)
\(\mathrm{H}\)
\(1\)
\(2\)
\(3\)
\(4\)
\(5\)
\(6\)
\(7\)
\(8\)
  1. Exécuter le programme : Répéter \(2\) fois : \(\Bigl[\) avancer de \(3\) vers le haut ; avancer de \(3\) vers la droite \(\Bigr]\). Où le robot est-il arrêté ?

    Le robot monte de \(\mathrm{A1}\) à \(\mathrm{A4}\), puis part vers la droite : \(\mathrm{B4}\), \(\mathrm{C4}\). La case suivante, \(\mathrm{D4}\), est un rocher.

    $$ \text{le robot est bloqué en } \mathrm{C4} $$
  2. Sans tenir compte des rochers, pour quels nombres de répétitions un programme de cette forme peut-il mener le robot en \(\mathrm{G7}\) ? Justifier.

    De \(\mathrm{A}\) à \(\mathrm{G}\), le robot doit avancer de \(6\) colonnes en tout, et il avance du même nombre de cases vers la droite à chaque répétition. Le nombre de répétitions, multiplié par ce nombre de cases, doit donc donner \(6\) :

    $$ 1 \times 6 = 6 \hspace{2em} 2 \times 3 = 6 \hspace{2em} 3 \times 2 = 6 \hspace{2em} 6 \times 1 = 6 $$

    Avec \(4\) ou \(5\) répétitions, c'est impossible : \(6\) n'est ni dans la table de \(4\), ni dans celle de \(5\). Au-delà de \(6\) répétitions, il faudrait avancer de moins d'une case à chaque fois.

    $$ 1 \ ; \ 2 \ ; \ 3 \quad \text{ou} \quad 6 \text{ répétitions} $$

    De la ligne \(1\) à la ligne \(7\), il y a aussi \(6\) lignes : dans chaque bloc, le robot avance d'autant de cases vers le haut que vers la droite.

  3. Trouver tous les programmes de cette forme qui mènent le robot au trésor sans heurter de rocher, et montrer qu'il n'y en a pas d'autre.

    D'après la question précédente, il n'y a que \(4\) nombres de répétitions possibles, et deux ordres pour chacun : \(8\) programmes à suivre sur le quadrillage.

    Répétitions
    Bloc répété
    Ce qui arrive
    \(1\)
    \(6\) vers la droite ; \(6\) vers le haut
    bloqué en \(\mathrm{B1}\) par \(\mathrm{C1}\)
    \(1\)
    \(6\) vers le haut ; \(6\) vers la droite
    bloqué en \(\mathrm{A4}\) par \(\mathrm{A5}\)
    \(2\)
    \(3\) vers la droite ; \(3\) vers le haut
    bloqué en \(\mathrm{B1}\) par \(\mathrm{C1}\)
    \(2\)
    \(3\) vers le haut ; \(3\) vers la droite
    bloqué en \(\mathrm{C4}\) par \(\mathrm{D4}\)
    \(3\)
    \(2\) vers la droite ; \(2\) vers le haut
    bloqué en \(\mathrm{B1}\) par \(\mathrm{C1}\)
    \(3\)
    \(2\) vers le haut ; \(2\) vers la droite
    arrive en \(\mathrm{G7}\)
    \(6\)
    \(1\) vers la droite ; \(1\) vers le haut
    bloqué en \(\mathrm{D3}\) par \(\mathrm{D4}\)
    \(6\)
    \(1\) vers le haut ; \(1\) vers la droite
    bloqué en \(\mathrm{C4}\) par \(\mathrm{D4}\)

    Un seul programme convient :

    Répéter \(3\) fois : \(\Bigl[\) avancer de \(2\) vers le haut ; avancer de \(2\) vers la droite \(\Bigr]\)

    Vérification : le robot passe par \(\mathrm{A3}\), \(\mathrm{C3}\), \(\mathrm{C5}\), \(\mathrm{E5}\), \(\mathrm{E7}\), et arrive en \(\mathrm{G7}\) sans toucher de rocher.

Trente répétitions

Le robot, représenté par un triangle qui pointe dans la direction où il regarde, est en \(\mathrm{D4}\), tourné vers la droite. Voici un bloc d'instructions :

avancer de \(2\) ; tourner d'un quart de tour vers la gauche ; avancer de \(1\).

Un quadrillage de huit colonnes, de A à H, et de huit lignes ; le robot, un triangle, est en D4 et pointe vers la droite
\(\mathrm{A}\)
\(\mathrm{B}\)
\(\mathrm{C}\)
\(\mathrm{D}\)
\(\mathrm{E}\)
\(\mathrm{F}\)
\(\mathrm{G}\)
\(\mathrm{H}\)
\(1\)
\(2\)
\(3\)
\(4\)
\(5\)
\(6\)
\(7\)
\(8\)
  1. Le robot exécute ce bloc une fois. Sur quelle case arrive-t-il, et vers où regarde-t-il ?

    Le robot regarde vers la droite. Il avance de \(2\) : il atteint \(\mathrm{F4}\). Il pivote vers la gauche, donc regarde vers le haut. Il avance de \(1\) :

    $$ \mathrm{F5} \quad \text{tourné vers le haut} $$
  2. Le robot repart de \(\mathrm{D4}\), tourné vers la droite, et exécute : Répéter \(4\) fois : \(\Bigl[\) avancer de \(2\) ; tourner d'un quart de tour vers la gauche ; avancer de \(1\) \(\Bigr]\). Tracer son chemin sur le quadrillage et donner sa position finale. Que remarque-t-on ?
    Répétition
    Case atteinte
    Le robot regarde vers
    \(1\)
    \(\mathrm{F5}\)
    le haut
    \(2\)
    \(\mathrm{E7}\)
    la gauche
    \(3\)
    \(\mathrm{C6}\)
    le bas
    \(4\)
    \(\mathrm{D4}\)
    la droite
    $$ \mathrm{D4} \quad \text{tourné vers la droite} $$
    Le chemin du robot après quatre répétitions du bloc : parti de D4 vers la droite, il suit le contour du carré de sommets C4, F4, F7 et C7 et revient en D4 ; des points marquent F5, E7 et C6, où finissent les trois premières répétitions
    \(\mathrm{A}\)
    \(\mathrm{B}\)
    \(\mathrm{C}\)
    \(\mathrm{D}\)
    \(\mathrm{E}\)
    \(\mathrm{F}\)
    \(\mathrm{G}\)
    \(\mathrm{H}\)
    \(1\)
    \(2\)
    \(3\)
    \(4\)
    \(5\)
    \(6\)
    \(7\)
    \(8\)

    Le robot est revenu à son point de départ, dans la même direction, après avoir suivi le contour d'un carré de \(3\) cases de côté : chaque « avancer de \(1\) » se prolonge par l'« avancer de \(2\) » de la répétition suivante, dans la même direction.

  3. Le robot repart de \(\mathrm{D4}\), tourné vers la droite, et répète ce même bloc \(30\) fois. Sur quelle case finit-il, et vers où regarde-t-il ? Justifier sans tout tracer.

    Toutes les \(4\) répétitions, le robot se retrouve en \(\mathrm{D4}\), tourné vers la droite. On effectue la division euclidienne de \(30\) par \(4\) :

    $$ 30 = 4 \times 7 + 2 $$

    Après \(28\) répétitions, le robot est en \(\mathrm{D4}\), tourné vers la droite. Les \(2\) répétitions qui restent le mènent, comme dans le tableau de la question précédente :

    $$ \mathrm{E7} \quad \text{tourné vers la gauche} $$
  4. Parti de \(\mathrm{D4}\), tourné vers la droite, ce même robot a répété le bloc un certain nombre de fois, entre \(1\) et \(20\), et il s'est arrêté en \(\mathrm{C6}\). Combien de répétitions a-t-il pu faire ? Donner toutes les possibilités.

    À la fin d'une répétition, le robot ne peut être qu'en \(\mathrm{F5}\), \(\mathrm{E7}\), \(\mathrm{C6}\) ou \(\mathrm{D4}\), selon le reste de la division du nombre de répétitions par \(4\) :

    Reste
    \(1\)
    \(2\)
    \(3\)
    \(0\)
    Case
    \(\mathrm{F5}\)
    \(\mathrm{E7}\)
    \(\mathrm{C6}\)
    \(\mathrm{D4}\)

    Le robot est en \(\mathrm{C6}\) après \(3\) répétitions, puis de nouveau à chaque fois qu'on en ajoute \(4\) :

    $$ 3 + 4 = 7 \hspace{2em} 7 + 4 = 11 \hspace{2em} 11 + 4 = 15 \hspace{2em} 15 + 4 = 19 $$

    La suivante, \(23\), dépasse \(20\).

    $$ 3 \ ; \ 7 \ ; \ 11 \ ; \ 15 \quad \text{ou} \quad 19 \text{ répétitions} $$