Une recette de cuisine, l'itinéraire pour aller au collège, la notice d'un meuble… ce sont des algorithmes : des suites d'instructions qu'on suit dans l'ordre pour arriver à un résultat.
Un algorithme est une suite d'instructions précises, dans un ordre donné, qui permet de résoudre un problème. Écrit dans un langage que comprend un ordinateur (comme Scratch), il devient un programme.
Un ordinateur fait exactement ce qu'on lui dit, ni plus ni moins. Si une instruction manque ou est dans le mauvais ordre, le résultat est faux !
Un robot se déplace d'une case à l'autre. Chaque flèche est une instruction : \(\rightarrow\) (une case à droite), \(\leftarrow\), \(\uparrow\), \(\downarrow\).
Il y a souvent plusieurs programmes qui conviennent. \(\uparrow \uparrow \rightarrow \rightarrow \rightarrow\) amène aussi le robot de B2 à E4.
Dans Scratch, un lutin se déplace sur la scène. Avec le stylo baissé, il dessine son trajet.
| Instruction | Ce que fait le lutin |
|---|---|
avancer de 100 pas |
il avance tout droit de \(100\) pas, dans la direction où il regarde |
tourner ↻ de 90 degrés |
il tourne sur place vers la droite, de \(90°\) |
stylo en position d'écriture |
il laisse une trace en se déplaçant |
relever le stylo |
il se déplace sans laisser de trace |
Exemple — un programme qui dessine un carré de côté \(100\) :
avancer de 100 pas
tourner ↻ de 90 degrés
avancer de 100 pas
tourner ↻ de 90 degrés
avancer de 100 pas
tourner ↻ de 90 degrés
avancer de 100 pas
tourner ↻ de 90 degrés
Dans le programme du carré, on écrit 4 fois la même chose. On peut le dire plus simplement avec une boucle :
Une boucle répéter n fois exécute les instructions qu'elle contient \(n\) fois de suite. Elle rend le programme plus court et plus facile à lire.
Les polygones réguliers. Pour revenir à son point de départ en traçant un polygone régulier, le lutin doit faire un tour complet (\(360°\)) en tout.
Pour un polygone régulier à \(n\) côtés, on répète \(n\) fois : avancer, puis tourner de \(360° \div n\).
| Polygone | triangle | carré | pentagone | hexagone |
|---|---|---|---|---|
| Nombre de côtés | 3 | 4 | 5 | 6 |
| Angle à tourner | \(120°\) | \(90°\) | \(72°\) | \(60°\) |
Pour un triangle équilatéral, les angles du triangle mesurent \(60°\), mais le lutin doit tourner de \(120°\). Il tourne de ce qui manque pour faire un demi-tour : \(180° - 60° = 120°\).
Une variable est une « boîte » qui porte un nom et qui contient une valeur. Cette valeur peut changer pendant le programme.
Exemple :
mettre score à 0
répéter 5 fois
ajouter 3 à score
dire score
Le score vaut \(0\), puis \(3\), \(6\), \(9\), \(12\), \(15\) : le lutin dit \(15\).
Contenu facultatif, non exigible.
L'instruction si … alors … sinon permet de choisir entre deux actions selon une condition (par exemple : « si le nombre est pair, alors le diviser par \(2\) »). Tu l'utiliseras beaucoup au cycle 4.
L’essentiel du chapitre, à relire avant un contrôle.
| Notion | Ce qu'il faut savoir |
|---|---|
| Algorithme | Suite d'instructions précises, dans un ordre donné |
| Programme | Algorithme écrit dans un langage informatique (Scratch…) |
avancer / tourner |
Le lutin avance dans sa direction / tourne sur place |
| Stylo | Baissé : il trace ; relevé : il ne trace pas |
Boucle répéter n fois |
Exécute \(n\) fois les instructions qu'elle contient |
| Polygone régulier à \(n\) côtés | Répéter \(n\) fois : avancer, tourner de \(360° \div n\) |
| Variable | Boîte nommée dont la valeur peut changer |
Sur un quadrillage, un robot est sur la case C3 (colonne C, ligne 3). Il exécute le programme : \[\rightarrow \; \rightarrow \; \uparrow \; \uparrow \; \uparrow \; \leftarrow\] Sur quelle case arrive-t-il ?
on suit les flèches une par une, sans en sauter.
Le robot arrive sur la case D6.
Un robot est sur la case B2. Il doit aller sur la case E4.
a) Écris un programme avec des flèches.
b) Écris un autre programme, différent, qui convient aussi.
c) Combien de flèches faut-il au minimum ?
a) De B à E : \(3\) colonnes vers la droite. De 2 à 4 : \(2\) lignes vers le haut. Un programme possible : \(\rightarrow \rightarrow \rightarrow \uparrow \uparrow\).
b) Par exemple : \(\uparrow \uparrow \rightarrow \rightarrow \rightarrow\), ou \(\rightarrow \uparrow \rightarrow \uparrow \rightarrow\).
c) Il faut au minimum \(3 + 2 = \mathbf{5}\) flèches (on ne peut pas faire moins que \(3\) pas à droite et \(2\) pas vers le haut).
Le lutin a le stylo baissé et exécute :
avancer de 50 pas
tourner ↻ de 90 degrés
avancer de 50 pas
tourner ↻ de 90 degrés
avancer de 50 pas
tourner ↻ de 90 degrés
avancer de 50 pas
a) Quelle figure dessine-t-il ?
b) Quelle est la longueur totale du tracé ?
a) Le lutin trace \(4\) segments de \(50\) pas en tournant de \(90°\) entre chacun : il dessine un carré de côté \(50\).
b) \(4 \times 50 = \mathbf{200}\) pas.
Il n'y a pas de tourner après le dernier côté. Le carré est bien dessiné, mais le lutin ne regarde pas dans sa direction de départ.
Réécris le script de l'exercice 3 en utilisant une boucle répéter.
répéter 4 fois
avancer de 50 pas
tourner ↻ de 90 degrés
Avec la boucle, le lutin tourne une 4e fois à la fin : il se retrouve dans sa direction de départ. Le dessin, lui, est le même.
Pour chaque script, quelle distance le lutin parcourt-il en tout ?
a) répéter 3 fois [ avancer de 10 pas ]
b) répéter 5 fois [ avancer de 20 pas , tourner ↻ de 72 degrés ]
c) répéter 10 fois [ avancer de 15 pas ]
distance totale \(=\) nombre de répétitions \(\times\) distance d'un passage. Les rotations ne changent pas la distance parcourue.
a) \(3 \times 10 = \mathbf{30}\) pas.
b) \(5 \times 20 = \mathbf{100}\) pas (le lutin dessine un pentagone régulier).
c) \(10 \times 15 = \mathbf{150}\) pas.
mettre nombre à 3
ajouter 5 à nombre
mettre nombre à (nombre × 2)
dire nombre
Qu'affiche le lutin ?
on suit la valeur de la variable ligne après ligne.
| Instruction | Valeur de nombre |
|---|---|
mettre nombre à 3 |
\(3\) |
ajouter 5 à nombre |
\(8\) |
mettre nombre à (nombre × 2) |
\(16\) |
Le lutin affiche \(\mathbf{16}\).
Sur un quadrillage, un robot part de la case A1 (colonne A, ligne 1). Il exécute : \[\rightarrow \; \rightarrow \; \uparrow \; \uparrow \; \rightarrow\] Sur quelle case arrive-t-il ?
Deux pas à droite : A → B → C. Deux pas en haut : ligne 1 → 3. Un pas à droite : C → D. Le robot arrive en D3.
répéter 4 fois
avancer de 80 pas
tourner ↻ de 90 degrés
a) Quelle figure le lutin dessine-t-il ?
b) Quelle est la longueur totale du tracé ?
a) Un carré de \(80\) pas de côté.
b) \(4 \times 80 = \mathbf{320}\) pas.
répéter 3 fois
avancer de 100 pas
tourner ↻ de 120 degrés
Quelle figure le lutin dessine-t-il ?
Trois côtés de même longueur, et le lutin tourne de \(360° \div 3 = 120°\) : c'est un triangle équilatéral de \(100\) pas de côté.
mettre x à 10
ajouter 5 à x
mettre x à (x × 2)
dire x
Qu'affiche le lutin ?
\(x\) vaut \(10\), puis \(15\), puis \(30\). Le lutin dit \(30\).
Le robot est en A1 et doit aller en D3.
a) Écris un programme avec des flèches.
b) Combien de flèches faut-il au minimum ?
a) Par exemple : \(\rightarrow \; \rightarrow \; \rightarrow \; \uparrow \; \uparrow\).
b) Il faut \(3\) pas vers la droite (A → D) et \(2\) vers le haut (1 → 3) : \(5\) flèches au minimum.
Pour dessiner un triangle équilatéral de côté \(100\), Lina écrit :
répéter 3 fois
avancer de 100 pas
tourner ↻ de 60 degrés
a) Le lutin dessine-t-il un triangle ? Explique.
b) Corrige le programme.
a) Non. En tournant de \(60°\) à chaque fois, le lutin ne fait en tout que \(3 \times 60° = 180°\), un demi-tour : il ne revient pas à son point de départ. Il dessine trois segments qui forment la moitié d'un hexagone.
b) Pour faire un tour complet en \(3\) fois, il faut tourner de \(360° \div 3 = 120°\) :
répéter 3 fois
avancer de 100 pas
tourner ↻ de 120 degrés
\(60°\) est l'angle du triangle, mais le lutin tourne de l'angle qui manque pour faire un demi-tour : \(180° - 60° = 120°\).
On veut dessiner un hexagone régulier (6 côtés de même longueur) de côté \(50\).
a) Combien de fois faut-il répéter les instructions ?
b) De quel angle le lutin doit-il tourner à chaque fois ?
c) Écris le programme.
d) Quel est le périmètre de l'hexagone ?
a) Un hexagone a \(6\) côtés : on répète \(6\) fois.
b) \(360° \div 6 = \mathbf{60°}\).
c)
répéter 6 fois
avancer de 50 pas
tourner ↻ de 60 degrés
d) \(6 \times 50 = \mathbf{300}\) pas.
Ce programme devait dessiner un carré, mais ce n'est pas le cas :
répéter 4 fois
avancer de 100 pas
tourner ↻ de 60 degrés
a) Pourquoi le dessin n'est-il pas un carré ?
b) Corrige le programme.
a) Pour un carré, il faut tourner de \(90°\) à chaque coin (angle droit). Ici, le lutin tourne de \(60°\) : les angles ne sont pas droits et il ne revient pas au départ (\(4 \times 60° = 240°\), moins d'un tour).
b) On remplace \(60\) par \(90\) :
répéter 4 fois
avancer de 100 pas
tourner ↻ de 90 degrés
répéter 2 fois
avancer de 100 pas
tourner ↻ de 90 degrés
avancer de 50 pas
tourner ↻ de 90 degrés
a) Quelle figure le lutin dessine-t-il ? Donne ses dimensions.
b) Quel est son périmètre ?
a) À chaque passage, le lutin trace un côté de \(100\), tourne d'un angle droit, trace un côté de \(50\) et tourne encore. Avec \(2\) passages, il trace \(4\) côtés avec \(4\) angles droits : c'est un rectangle de \(100\) sur \(50\).
b) \(2 \times (100 + 50) = \mathbf{300}\) pas.
Le lutin regarde vers la droite. Il exécute :
répéter 4 fois
avancer de 20 pas
tourner ↺ de 90 degrés
avancer de 20 pas
tourner ↻ de 90 degrés
(↺ : tourner vers la gauche.)
a) Dessine à main levée la figure obtenue.
b) Quelle est la longueur totale du tracé ?
c) À la fin, de combien de pas le lutin s'est-il déplacé vers la droite ? Vers le haut ?
a) À chaque passage, le lutin trace une marche : \(20\) pas vers la droite, puis il tourne à gauche et monte de \(20\) pas, puis il se remet face à la droite. Avec \(4\) passages, on obtient un escalier de \(4\) marches.
b) Chaque passage trace \(20 + 20 = 40\) pas : \(4 \times 40 = \mathbf{160}\) pas.
c) Vers la droite : \(4 \times 20 = \mathbf{80}\) pas. Vers le haut : \(4 \times 20 = \mathbf{80}\) pas.
mettre score à 0
répéter 5 fois
ajouter 3 à score
dire score
a) Qu'affiche le lutin ?
b) On remplace ajouter 3 par ajouter 2 et répéter 5 fois par répéter 10 fois. Qu'affiche-t-il ?
c) On veut que le lutin affiche \(40\) avec ajouter 4. Combien de fois faut-il répéter ?
a) Le score vaut successivement \(0\), \(3\), \(6\), \(9\), \(12\), \(15\) : le lutin affiche \(\mathbf{15}\) (c'est \(5 \times 3\)).
b) \(10 \times 2 = \mathbf{20}\).
c) On cherche combien de fois \(4\) pour faire \(40\) : \(40 \div 4 = \mathbf{10}\) fois.
Un robot est sur la case A1. Il exécute :
répéter 3 fois [ \(\rightarrow \; \rightarrow \; \uparrow\) ]
a) Écris toutes les flèches que le robot exécute.
b) Sur quelle case arrive-t-il ? (Les colonnes sont nommées A, B, C, D, E, F, G…)
a) \(\rightarrow \rightarrow \uparrow \; \rightarrow \rightarrow \uparrow \; \rightarrow \rightarrow \uparrow\) (soit \(9\) flèches).
b) En tout : \(6\) cases vers la droite et \(3\) cases vers le haut. Colonnes : A → B, C, D, E, F, G (\(6\) colonnes plus loin). Lignes : 1 → 4. Le robot arrive sur la case G4.
Pour dessiner un polygone régulier à \(n\) côtés, le lutin tourne de \(360° \div n\) à chaque sommet. Complète le tableau :
| Nombre de côtés | 3 | 4 | 5 | 6 | 8 | 10 |
|---|---|---|---|---|---|---|
| Angle à tourner |
angle \(= 360° \div\) nombre de côtés.
| Nombre de côtés | 3 | 4 | 5 | 6 | 8 | 10 |
|---|---|---|---|---|---|---|
| Angle à tourner | \(\mathbf{120°}\) | \(\mathbf{90°}\) | \(\mathbf{72°}\) | \(\mathbf{60°}\) | \(\mathbf{45°}\) | \(\mathbf{36°}\) |
Plus il y a de côtés, plus l'angle est petit, et plus le polygone ressemble à un cercle.
On veut dessiner un pentagone régulier (\(5\) côtés égaux) de \(60\) pas de côté. Complète le script :
répéter … fois
avancer de … pas
tourner ↻ de … degrés
répéter 5 fois
avancer de 60 pas
tourner ↻ de 72 degrés
\(360° \div 5 = 72°\).
mettre n à 1
répéter 4 fois
ajouter 2 à n
dire n
a) Donne la valeur de n après chaque tour.
b) Qu'affiche le lutin ?
a) \(n\) vaut \(3\), puis \(5\), puis \(7\), puis \(9\).
b) Le lutin dit \(9\).
Sami veut dessiner un carré :
répéter 4 fois
avancer de 50 pas
tourner ↻ de 60 degrés
Le dessin n'est pas un carré. Corrige le script.
Pour un carré, le lutin doit tourner de \(90°\) à chaque sommet (et non de \(60°\)) : on remplace par tourner ↻ de 90 degrés.
répéter 5 fois
avancer de 30 pas
tourner ↺ de 90 degrés
avancer de 30 pas
tourner ↻ de 90 degrés
a) Combien de fois le lutin avance-t-il ?
b) Quelle distance totale parcourt-il ?
a) \(2\) fois par tour, \(5\) tours : \(10\) fois.
b) \(10 \times 30 = \mathbf{300}\) pas (le lutin dessine un escalier).
demander "Choisis un nombre" et attendre
mettre résultat à ((réponse × 4) - 3)
dire résultat
a) Qu'affiche le lutin si l'on tape \(5\) ?
b) Quel nombre faut-il taper pour qu'il affiche \(25\) ?
a) \(5 \times 4 = 20\), puis \(20 - 3 = \mathbf{17}\).
b) On remonte : \(25 + 3 = 28\), puis \(28 \div 4 = \mathbf{7}\).
répéter 5 fois
avancer de 100 pas
tourner ↻ de 144 degrés
a) Combien de segments le lutin trace-t-il ?
b) De combien de degrés a-t-il tourné en tout ? Combien de tours complets cela fait-il ?
c) Le lutin revient-il à son point de départ ? Quelle figure dessine-t-il ?
a) La boucle est exécutée \(5\) fois : \(5\) segments.
b) \(5 \times 144° = \mathbf{720°}\), soit \(720 \div 360 = \mathbf{2}\) tours complets.
c) Le lutin a fait un nombre entier de tours et ses \(5\) segments sont identiques : il revient à son point de départ. Les segments se croisent : il dessine une étoile à 5 branches.
On veut dessiner un carré de côté \(80\) et que le lutin finisse à son point de départ, tourné dans la même direction qu'au début. Un élève propose :
répéter 3 fois
avancer de 80 pas
tourner ↻ de 90 degrés
a) Que dessine ce programme ?
b) Où se trouve le lutin à la fin, et dans quelle direction regarde-t-il ?
c) Corrige le programme.
a) La boucle ne tourne que \(3\) fois : le lutin trace \(3\) côtés du carré seulement (il manque le 4e côté).
b) Il s'arrête au 4e coin du carré (pas au départ), et regarde vers ce coin de départ, dans la direction du côté manquant.
c) Il faut répéter 4 fois :
répéter 4 fois
avancer de 80 pas
tourner ↻ de 90 degrés
Le lutin trace les \(4\) côtés et, après sa 4e rotation, il a fait un tour complet (\(4 \times 90° = 360°\)) : il est au départ, tourné comme au début ✓.
Le lutin regarde vers la droite, stylo baissé.
répéter 3 fois
répéter 4 fois
avancer de 30 pas
tourner ↺ de 90 degrés
relever le stylo
avancer de 40 pas
stylo en position d'écriture
a) Combien de carrés le lutin dessine-t-il ? Quelle est la longueur de leur côté ?
b) Quel est l'espace entre deux carrés voisins ?
c) Quelle est la longueur totale tracée ?
il y a une boucle dans une autre boucle. La boucle intérieure (répéter 4 fois) dessine un carré ; la boucle extérieure (répéter 3 fois) recommence \(3\) fois : carré, puis déplacement sans tracer.
a) \(3\) carrés de côté \(30\) pas.
b) Après chaque carré, le lutin est revenu à son coin de départ ; il avance alors de \(40\) pas sans tracer. Le carré suivant commence \(40\) pas plus loin, et le carré précédent occupait déjà \(30\) pas : l'espace entre deux carrés est de \(40 - 30 = \mathbf{10}\) pas.
c) Seuls les carrés sont tracés : \(3 \times (4 \times 30) = 3 \times 120 = \mathbf{360}\) pas.
On applique l'algorithme suivant à un nombre entier :
Si le nombre est pair, on le divise par \(2\). Sinon, on le multiplie par \(3\) et on ajoute \(1\).
a) Applique l'algorithme à \(6\), puis à \(7\).
b) En partant de \(6\), on recommence l'algorithme sur chaque résultat. Écris la liste des nombres obtenus jusqu'à arriver à \(1\).
c) Combien d'étapes a-t-il fallu ?
a)
b) On part de \(6\) :
Liste : \(6 ; 3 ; 10 ; 5 ; 16 ; 8 ; 4 ; 2 ; 1\).
c) Il a fallu \(8\) étapes.
Personne n'a encore réussi à prouver qu'on arrive toujours à \(1\), quel que soit le nombre de départ ! C'est un problème célèbre, encore non résolu.
mettre nombre à 47
mettre compteur à 0
répéter jusqu'à ce que nombre < 6
ajouter -6 à nombre
ajouter 1 à compteur
dire compteur
dire nombre
a) Fais fonctionner l'algorithme « à la main » en notant les valeurs de nombre et compteur à chaque passage dans la boucle.
b) Qu'affiche le lutin à la fin ?
c) Quel lien y a-t-il avec la division euclidienne de \(47\) par \(6\) ?
a) On enlève \(6\) tant que le nombre n'est pas plus petit que \(6\) :
| Passage | 0 (départ) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
nombre |
47 | 41 | 35 | 29 | 23 | 17 | 11 | 5 |
compteur |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Après le 7e passage, nombre vaut \(5\) : comme \(5 < 6\), la boucle s'arrête.
b) Le lutin dit \(7\), puis \(5\).
c) On a enlevé \(7\) fois \(6\) à \(47\), et il reste \(5\) :
\[47 = 6 \times 7 + 5\]
compteur est le quotient et nombre est le reste de la division euclidienne de \(47\) par \(6\).
Le lutin part du coin en bas à gauche, en regardant vers le haut, stylo baissé.
répéter 4 fois
avancer de 100 pas
tourner ↻ de 90 degrés
avancer de 100 pas
tourner ↻ de 30 degrés
avancer de 100 pas
tourner ↻ de 120 degrés
avancer de 100 pas
a) Que dessine la boucle ? Où se trouve le lutin à la sortie de la boucle, et vers où regarde-t-il ?
b) Que fait l'instruction avancer de 100 pas qui suit la boucle ?
c) Que dessinent les quatre dernières instructions ? Quelle est la nature de cette figure ?
d) Quelle est la longueur totale parcourue par le lutin ? Quel est le périmètre de la maison ?
a) La boucle trace un carré de côté \(100\) : le lutin monte le côté gauche, puis tourne et trace le haut, le côté droit et le bas. Après le 4e tourner, il a fait un tour complet : il est revenu en bas à gauche, et regarde vers le haut.
b) Il remonte le long du côté gauche (déjà tracé) et arrive au coin en haut à gauche du carré.
c) Il tourne de \(30°\) vers la droite et trace un segment de \(100\) en montant (premier pan du toit), puis tourne de \(120°\) et trace un segment de \(100\) en redescendant : il arrive sur le coin en haut à droite du carré. Les deux pans du toit et le haut du carré mesurent tous \(100\) : le toit est un triangle équilatéral.
d) Le lutin a parcouru : \(4 \times 100\) (carré) \(+ 100\) (remontée) \(+ 100 + 100\) (toit) \(= \mathbf{700}\) pas. Le contour de la maison est formé de \(3\) côtés du carré (le haut du carré est à l'intérieur de la maison) et des \(2\) pans du toit : \(5 \times 100 = \mathbf{500}\) pas.