3ᵉ · Chapitre 14 · Algorithmique et programmation

Algorithmique et programmation (Scratch)

Boucles, conditions, variables, blocs personnalisés — exercice quasi systématique au DNB.

Sommaire

Ce qu'il faut savoir faire

Boucles
Conditions
Variables
Blocs personnalisés — exercice quasi systématique au DNB

Derrière chaque jeu vidéo, chaque application de ton téléphone et chaque site web, il y a la même chose : des instructions écrites par des humains et exécutées par une machine. Ce chapitre t'apprend à lire et à écrire ces instructions avec Scratch, le langage par blocs que tu utilises depuis la cinquième. Et c'est un chapitre à ne surtout pas négliger : un exercice d'algorithmique tombe quasi systématiquement au brevet, presque toujours sous l'une de ces trois formes : un programme de calcul à décortiquer, une figure à tracer (souvent un polygone régulier), ou un petit jeu avec du hasard. Bonne nouvelle : aucune de ces trois situations n'a de secret quand on maîtrise une poignée de notions, toujours les mêmes. C'est exactement le programme de ce chapitre.

Algorithme, programme, script

Commençons par le vocabulaire. Quand tu suis une recette de cuisine, tu exécutes une suite d'instructions dans un ordre précis : casser les œufs, puis les battre, puis ajouter la farine. Inverser deux étapes peut ruiner le gâteau. Un algorithme, c'est exactement cela : une marche à suivre, écrite noir sur blanc, où l'ordre des instructions compte.

Définition

Un algorithme est une suite d'instructions, données dans un ordre précis, qui permet de résoudre un problème ou d'accomplir une tâche.
Un programme est un algorithme écrit dans un langage compréhensible par une machine (Scratch, par exemple).
Dans Scratch, un programme s'appelle un script : c'est une pile de blocs emboîtés, qui s'exécute de haut en bas, un bloc après l'autre.

Dans Scratch, les instructions s'adressent à un personnage appelé le lutin (par défaut, le petit chat orange). Le lutin vit sur la scène, la zone rectangulaire où tout se passe : c'est lui qui parle, se déplace et dessine quand on exécute un script.

Exemple

Voici un premier script, composé d'un bloc de déclenchement et de trois instructions :

quand le drapeau vert est cliqué
dire « Bonjour ! » pendant 2 secondes
dire « Je suis un lutin. » pendant 2 secondes
dire « Et voici mon premier script ! » pendant 2 secondes

Quand on clique sur le drapeau vert, le lutin affiche les trois phrases dans l'ordre, l'une après l'autre, chacune pendant $2$ secondes. L'exécution dure donc $3 \times 2 = 6$ secondes en tout. Si on échangeait les deuxième et troisième instructions, le lutin se présenterait dans le désordre : l'ordre des blocs fait partie du programme.

Retiens bien ce réflexe de lecture, car c'est la compétence numéro un au brevet : face à un script, on le lit de haut en bas, ligne par ligne, en faisant exactement ce qui est écrit, ni plus ni moins. L'ordinateur n'improvise jamais ; toi non plus quand tu joues son rôle.

Les événements : déclencher un script

Un script ne démarre jamais tout seul : il attend un signal de départ, qu'on appelle un événement. Le bloc d'événement est toujours le premier bloc du script, celui qui a une forme arrondie de « chapeau » en haut.

Définition

Un événement est le signal qui déclenche l'exécution d'un script. Les principaux événements de Scratch sont :

le clic sur le drapeau vert (quand le drapeau vert est cliqué), qui lance le programme ;
l'appui sur une touche du clavier (quand la touche espace est pressée) ;
la réception d'un message envoyé par un autre script (envoyer [message] à tous déclenche tous les scripts qui commencent par quand je reçois [message]).

Les messages servent à faire dialoguer les scripts entre eux : un script termine son travail, envoie un message, et un autre script (du même lutin ou d'un autre lutin) prend le relais.

Exemple

Le chat donne le signal, le chien lui répond. Script du chat :

quand le drapeau vert est cliqué
dire « À toi de jouer ! » pendant 2 secondes
envoyer [top départ] à tous

Script du chien :

quand je reçois [top départ]
attendre 1 seconde
dire « Message reçu ! » pendant 2 secondes

Au clic sur le drapeau vert, seul le script du chat démarre. Après $2$ secondes de parole, il envoie le message « top départ » ; le script du chien se déclenche alors, patiente $1$ seconde, puis répond. Les deux lutins agissent l'un après l'autre.

Mais que se passe-t-il si deux scripts commencent par le même événement ? Ils se déclenchent tous les deux au même instant, et s'exécutent en même temps : on dit qu'ils s'exécutent en parallèle.

Propriété

Lorsque plusieurs scripts commencent par le même événement, ils démarrent tous à cet événement et s'exécutent en parallèle (simultanément), que ces scripts appartiennent au même lutin ou à des lutins différents.

Exemple

Le chat et le chien ont chacun un script déclenché par le drapeau vert. Script du chat :

quand le drapeau vert est cliqué
dire « Salut, je suis le chat ! » pendant 2 secondes

Script du chien :

quand le drapeau vert est cliqué
dire « Et moi le chien ! » pendant 2 secondes

Au clic sur le drapeau vert, les deux bulles apparaissent en même temps à l'écran, et disparaissent en même temps $2$ secondes plus tard. C'est très différent de l'exemple précédent avec les messages, où le chien attendait son tour. Au brevet, on te demande parfois ce qu'affiche l'écran à un instant donné : demande-toi toujours quels scripts sont déclenchés par le même événement.

Les boucles

Imagine que tu veuilles faire dire dix fois « Bravo ! » au lutin. Empiler dix blocs identiques fonctionne, mais c'est long, illisible, et source d'erreurs. Les boucles règlent le problème : elles répètent un groupe d'instructions sans qu'on ait à les réécrire. Scratch en propose trois, et savoir les distinguer est essentiel.

Définition

Une boucle répète les instructions placées à l'intérieur d'elle (le corps de la boucle). Scratch propose trois boucles :

répéter (n) fois : le corps est exécuté exactement $n$ fois ;
répéter indéfiniment : le corps est exécuté sans fin (jusqu'à l'arrêt du programme) ;
répéter jusqu'à ce que <condition> : avant chaque passage, Scratch teste la condition ; tant qu'elle est fausse, le corps est exécuté ; dès qu'elle devient vraie, la boucle s'arrête.

La boucle répéter indéfiniment sert surtout dans les jeux et les animations : un décor qui défile, un lutin qui surveille en permanence si on le touche. Elle ne s'arrête que lorsqu'on stoppe le programme.

Les deux autres boucles se ressemblent, mais reposent sur des logiques opposées, et c'est LA question piège du brevet.

Propriété

Bien distinguer les deux boucles qui s'arrêtent.

Avec répéter (n) fois, le nombre de répétitions est connu à l'avance : c'est le nombre $n$ écrit dans le bloc.
Avec répéter jusqu'à ce que <condition>, le nombre de répétitions n'est pas connu à l'avance : la boucle tourne tant que la condition est fausse, et s'arrête dès qu'elle devient vraie.
Cas limite à connaître : si la condition est déjà vraie avant le premier passage, le corps de la boucle n'est exécuté aucune fois.

Exemple

Voici un script qui utilise une variable nommée « score » (une valeur gardée en mémoire, que nous étudierons en détail dans la section suivante) :

quand le drapeau vert est cliqué
mettre [score] à 0
répéter jusqu'à ce que <score = 10>
    ajouter 2 à [score]
dire (score)

Suivons l'exécution pas à pas dans une trace d'exécution : au départ, la variable score vaut $0$ , puis chaque tour de boucle lui ajoute $2$ .

Tour de boucle	Valeur de score après le tour
$1$	$2$
$2$	$4$
$3$	$6$
$4$	$8$
$5$	$10$

Après le cinquième tour, score vaut $10$ : la condition « score $= 10$ » devient vraie, la boucle s'arrête, et le lutin dit $10$ . Le corps de la boucle a été exécuté $5$ fois, un nombre qu'on découvre en déroulant le script, pas en le lisant.

La trace d'exécution que tu viens de voir est un outil précieux : au brevet, quand un script te résiste, prends un brouillon et note la valeur de chaque variable après chaque tour de boucle. C'est lent, mais infaillible.

Les variables

Un programme a souvent besoin de mémoriser des nombres : un score, un compteur de vies, la réponse d'un utilisateur. C'est le rôle des variables.

Définition

Une variable est une « boîte » qui porte un nom et qui contient une valeur. Cette valeur peut changer au cours de l'exécution du programme. Deux blocs permettent de modifier une variable :

mettre [nombre] à 5 remplace le contenu de la boîte par la valeur indiquée (on dit qu'on affecte la valeur $5$ à la variable) ;
ajouter 3 à [score] augmente le contenu de la boîte de la valeur indiquée (l'ancienne valeur n'est pas oubliée, on lui ajoute $3$ ).

Ne confonds pas ces deux blocs : si score vaut $7$ , alors mettre [score] à 3 lui donne la valeur $3$ , tandis que ajouter 3 à [score] lui donne la valeur $7 + 3 = 10$ . Le bloc ajouter utilisé à l'intérieur d'une boucle crée un compteur : c'est exactement ce que faisait la variable score de la section précédente, qui comptait de $2$ en $2$ .

Passons maintenant au grand classique du brevet : le programme de calcul. C'est un script qui demande un nombre à l'utilisateur, lui applique une suite d'opérations, puis annonce le résultat.

Exemple

Voici un programme de calcul complet :

quand le drapeau vert est cliqué
demander « Choisis un nombre » et attendre
mettre [nombre] à (réponse)
mettre [nombre] à (nombre * 3)
ajouter 5 à [nombre]
dire (nombre) pendant 2 secondes

Le bloc demander … et attendre affiche une question et stocke ce que tape l'utilisateur dans le bloc réponse. Le script triple ensuite le nombre, lui ajoute $5$ , et annonce le résultat. Exécutons-le pour deux valeurs de départ :

Instruction	Départ : $4$	Départ : $- 2$
`mettre [nombre] à (réponse)`	$4$	$- 2$
`mettre [nombre] à (nombre * 3)`	$12$	$- 6$
`ajouter 5 à [nombre]`	$17$	$- 1$

Pour $4$ , le lutin dit $17$ , car $3 \times 4 + 5 = 17$ . Pour $- 2$ , il dit $- 1$ , car $3 \times (- 2) + 5 = - 6 + 5 = - 1$ . Vérifie toujours tes calculs avec les nombres négatifs : c'est là que les points se perdent.

Le brevet ne s'arrête presque jamais là : il te demande ensuite d'exprimer le résultat du programme en fonction du nombre choisi. C'est le pont entre ce chapitre et le calcul littéral.

Méthode

Passer du script à l'expression littérale.

Nommer le nombre choisi au départ : on l'appelle $x$ .
Suivre le script ligne par ligne en appliquant chaque opération à l'expression : ici, « tripler » donne $3 x$ , puis « ajouter $5$ » donne $3 x + 5$ .
Conclure : le résultat du programme est $3 x + 5$ .
Vérifier avec une valeur déjà testée : pour $x = 4$ , on a bien $3 \times 4 + 5 = 17$ .

Cette expression littérale ouvre la porte aux équations. Si l'énoncé demande « quel nombre faut-il choisir pour que le programme affiche $26$ ? », tu résous l'équation $3 x + 5 = 26$ , c'est-à-dire $3 x = 21$ , donc $x = 7$ . Et tu vérifies : $3 \times 7 + 5 = 21 + 5 = 26$ . Un exercice de Scratch cache souvent un exercice de calcul littéral ou d'équation : c'est même sa raison d'être au brevet.

Les instructions conditionnelles et le hasard

Jusqu'ici, nos scripts déroulaient toujours les mêmes instructions. Pour qu'un programme réagisse différemment selon la situation (bonne ou mauvaise réponse, victoire ou défaite), il faut des instructions conditionnelles.

Définition

Une condition est une affirmation qui est soit vraie, soit fausse, construite le plus souvent avec les opérateurs de comparaison < (inférieur à), > (supérieur à) et = (égal à). Les instructions conditionnelles sont :

si <condition> alors : les instructions du bloc ne sont exécutées que si la condition est vraie ; sinon, le script saute directement à la suite ;
si <condition> alors … sinon : si la condition est vraie, on exécute le premier groupe d'instructions ; si elle est fausse, on exécute le groupe du sinon. Un seul des deux groupes est exécuté, jamais les deux.

Exemple

Un quiz de calcul mental :

quand le drapeau vert est cliqué
demander « Combien font 7 fois 8 ? » et attendre
si <réponse = 56> alors
    dire « Bravo ! »
sinon
    dire « Non, la réponse était 56. »

Si l'utilisateur tape $56$ (et c'est bien $7 \times 8 = 56$ ), la condition est vraie : le lutin félicite. Pour toute autre réponse, la condition est fausse : c'est la branche sinon qui s'exécute. Remarque que le lutin dit toujours exactement une des deux phrases, jamais les deux, jamais aucune.

Deuxième ingrédient de cette section : le hasard. Scratch sait tirer un nombre au hasard, ce qui permet de programmer des dés, des tirages et des jeux.

Propriété

Le bloc nombre aléatoire entre (1) et (6) renvoie un nombre entier au hasard entre $1$ et $6$ , chacun des six nombres ayant la même probabilité d'être obtenu, à savoir $\frac{1}{6}$ .

Ce bloc simule donc le lancer d'un dé équilibré à six faces, exactement au sens du chapitre de probabilités : les six issues sont équiprobables.

Exemple

Un mini-jeu de dé : on gagne si on obtient un $6$ .

quand la touche espace est pressée
mettre [dé] à (nombre aléatoire entre (1) et (6))
dire (dé) pendant 2 secondes
si <dé = 6> alors
    dire « Gagné ! »
sinon
    dire « Perdu, retente ta chance. »

À chaque appui sur la touche espace, la variable dé reçoit un nombre entier au hasard entre $1$ et $6$ . Le lutin l'annonce, puis affiche « Gagné ! » si c'est un $6$ . Comme les six valeurs sont équiprobables, la probabilité de gagner à une partie est $\frac{1}{6}$ , et celle de perdre est $1 - \frac{1}{6} = \frac{5}{6}$ . Ce type de question, à cheval entre l'algorithmique et les probabilités, est un format très apprécié des sujets de brevet.

Déplacements et tracés de figures

Le lutin sait aussi se déplacer sur la scène et dessiner en laissant une trace derrière lui. Pour piloter ses déplacements, il faut d'abord comprendre comment la scène est repérée.

Définition

La scène de Scratch est munie d'un repère : l'abscisse $x$ varie de $- 240$ à $240$ et l'ordonnée $y$ varie de $- 180$ à $180$ . Le centre de la scène est le point de coordonnées $(0; 0)$ . La position du lutin est donnée par ses coordonnées $(x; y)$ .

La scène de Scratch et son repère

Sur cette figure, le lutin se trouve au point de coordonnées $(120; 80)$ : il est à droite du centre (abscisse positive) et au-dessus (ordonnée positive). Le bloc aller à x: (120) y: (80) l'y téléporte directement, quel que soit son point de départ.

Pour les déplacements, retiens ces blocs et leurs effets :

avancer de (60) pas : le lutin avance de $60$ pas dans la direction où il regarde ;
tourner à droite de (90) degrés et tourner à gauche de (90) degrés : le lutin pivote sur place, sans avancer ;
s'orienter à (90) degrés : le lutin prend une direction absolue ; dans Scratch, $90$ degrés signifie « vers la droite » et $0$ degré « vers le haut ».

Pour dessiner, le lutin dispose d'un stylo : stylo en position d'écriture abaisse la pointe (le lutin laisse une trace à chaque déplacement), relever le stylo l'interrompt, et effacer tout nettoie la scène. Un script de tracé commence presque toujours par effacer tout, pour repartir d'une scène vierge.

Venons-en au tracé vedette du brevet : les polygones réguliers. L'idée est simple : pour dessiner un carré, le lutin trace un côté, tourne, trace le côté suivant, tourne, et ainsi de suite. Toute la question est : de quel angle tourner ?

Propriété

Tracer un polygone régulier à $n$ côtés. On répète $n$ fois le motif « avancer (d'une longueur de côté), puis tourner de $\frac{360}{n}$ degrés » (toujours dans le même sens).

L'angle de rotation est l'angle extérieur du polygone : en faisant le tour complet de la figure, le lutin a tourné au total de $n \times \frac{360}{n} = 360$ degrés, soit un tour complet. Attention, ce n'est pas l'angle intérieur du polygone !

Exemple

Le script du carré : $4$ côtés, donc un angle de rotation de $360 \div 4 = 90$ degrés.

quand le drapeau vert est cliqué
effacer tout
aller à x: (-100) y: (0)
s'orienter à (90) degrés
stylo en position d'écriture
répéter (4) fois
    avancer de (60) pas
    tourner à droite de (90) degrés
relever le stylo

Le lutin part du point de coordonnées $(- 100; 0)$ , orienté vers la droite, stylo baissé. La boucle trace les $4$ côtés de $60$ pas, en tournant de $90$ degrés après chacun. Vérification : $4 \times 90 = 360$ degrés, le lutin a fait un tour complet et retrouve exactement sa position et son orientation de départ.

Exemple

Et pour un hexagone régulier ( $6$ côtés) ? L'angle de rotation est $360 \div 6 = 60$ degrés :

quand le drapeau vert est cliqué
effacer tout
stylo en position d'écriture
répéter (6) fois
    avancer de (50) pas
    tourner à droite de (60) degrés

Le piège classique : tu sais peut-être que l'angle intérieur d'un hexagone régulier mesure $120$ degrés, et tu serais tenté d'écrire « tourner de $120$ degrés ». C'est faux ! Le lutin tourne de l'angle extérieur, et les deux angles sont supplémentaires : $120 + 60 = 180$ degrés. Retiens la formule $\frac{360}{n}$ , elle ne trompe jamais : pour un triangle équilatéral, $360 \div 3 = 120$ degrés ; pour un carré, $90$ degrés ; pour un hexagone, $60$ degrés.

Les blocs personnalisés

Dernière notion du chapitre, et sans doute la plus élégante : créer ses propres blocs. Quand un même motif d'instructions revient plusieurs fois dans un projet, plutôt que de le recopier, on lui donne un nom et on en fait un bloc personnalisé, qu'on peut ensuite utiliser comme n'importe quel bloc de Scratch.

Définition

Un bloc personnalisé est un bloc créé par le programmeur. On le construit avec un chapeau définir suivi des instructions qui composent le bloc ; on l'utilise ensuite dans n'importe quel script en écrivant simplement son nom.

Méthode

Quand créer un bloc personnalisé ? Dès qu'un même groupe d'instructions apparaît (ou apparaîtrait) plusieurs fois dans un projet :

Repérer le motif qui se répète.
Définir un bloc portant un nom clair (par exemple carré), contenant ce motif.
Remplacer chaque copie du motif par un appel au bloc.

Le script devient plus court, plus lisible, et une correction du motif ne se fait plus qu'à un seul endroit.

Exemple

Reprenons le tracé du carré et transformons-le en bloc personnalisé :

définir carré
répéter (4) fois
    avancer de (60) pas
    tourner à droite de (90) degrés

Ce bloc trace un carré de côté $60$ pas à partir de la position et de l'orientation actuelles du lutin. On peut maintenant l'appeler dans une boucle pour dessiner une rosace : douze carrés tracés en tournant un peu entre chaque.

quand le drapeau vert est cliqué
effacer tout
aller à x: (0) y: (0)
stylo en position d'écriture
répéter (12) fois
    carré
    tourner à droite de (30) degrés

À chaque tour de boucle, le lutin trace un carré complet (le bloc carré fait son travail et ramène le lutin à son orientation de départ, puisqu'il tourne de $4 \times 90 = 360$ degrés), puis pivote de $30$ degrés avant le carré suivant. Vérification : $12 \times 30 = 360$ degrés, les douze carrés se répartissent régulièrement autour du centre et la rosace se referme exactement. Sans bloc personnalisé, ce script aurait exigé d'imbriquer deux boucles l'une dans l'autre ; avec lui, chaque script reste simple et lisible.

L'essentiel

Un algorithme est une suite ordonnée d'instructions ; écrit en Scratch, il devient un script, qui s'exécute de haut en bas.
Un script démarre grâce à un événement (drapeau vert, touche, message reçu) ; plusieurs scripts déclenchés par le même événement s'exécutent en parallèle.
répéter (n) fois exécute le corps exactement $n$ fois ; répéter jusqu'à ce que <condition> s'arrête quand la condition devient vraie, après un nombre de tours qu'on ne connaît pas à l'avance.
Une variable est une boîte nommée contenant une valeur : mettre … à remplace la valeur, ajouter … à l'augmente.
Pour un programme de calcul, on nomme $x$ le nombre de départ et on suit le script ligne à ligne pour obtenir l'expression littérale (par exemple $3 x + 5$ ) ; une question « quel nombre choisir pour obtenir… ? » se traduit par une équation.
si … alors … sinon exécute exactement un des deux groupes d'instructions, selon que la condition est vraie ou fausse.
nombre aléatoire entre (1) et (6) simule un dé équilibré : chaque valeur a la probabilité $\frac{1}{6}$ .
Pour tracer un polygone régulier à $n$ côtés : répéter $n$ fois « avancer puis tourner de $\frac{360}{n}$ degrés » (angle extérieur, pas l'angle intérieur !).
Quand un motif d'instructions se répète, on en fait un bloc personnalisé (définir), qu'on appelle ensuite par son nom.

Le cours en PDF(PDF, 86 Ko)

Bloqué sur « Algorithmique et programmation (Scratch) » ?

On peut le travailler ensemble dès cette semaine. La première heure est offerte — on fait le point honnêtement, et vous repartez au minimum avec une méthode.

Réserver ma 1ʳᵉ heure offerte