Séance 1 — Variables et affectation
Nommer, ranger, calculer, lire et écrire
Amont. Un algorithme est une suite finie d’instructions, exécutées dans l’ordre, que l’on peut suivre à la main ; il s’écrit entre un en-tête et les mots Début et Fin (Séance 0). Il lui manque une mémoire : un endroit où ranger une donnée lue ou un résultat, pour s’en servir plus loin.
Aval. Les conditions (Séance 2) comparent des valeurs de variables pour choisir les lignes à exécuter ; les boucles (Séance 3) répètent des affectations comme s \(\leftarrow\) s + x ; le tableau (Séance 4) range plusieurs valeurs sous un seul nom ; les fonctions (Séance 5) reçoivent des valeurs dans leurs paramètres.
- Déclarer une variable avec son type : entier, réel, booléen, caractère, chaîne ; écrire un algorithme complet, de l’en-tête à Fin.
- Lire une affectation de droite à gauche et dire ce que devient l’ancienne valeur de la variable.
- Prévoir ce que range Lire et ce qu’écrit Écrire, au caractère près.
- Évaluer une expression selon les priorités ; distinguer la division réelle \(/\) de la division entière div, et le quotient div du reste mod.
- Dérouler un algorithme dans une trace complète : pas, ligne, instruction, variables, écrit.
- Échanger deux variables ; repérer une variable sans valeur, une flèche lue à l’envers, une valeur du mauvais type, une division par zéro.
Les conventions du pseudo-code
Tout le cours écrit ses algorithmes dans un même pseudo-code français, indépendant de tout langage de programmation. La Séance 0 en a fixé la forme générale ; la présente séance fixe la déclaration des variables, l’affectation, la lecture, l’écriture et le calcul des expressions. Le tableau ci-dessous rassemble ces conventions ; les séances suivantes les reprennent telles quelles.
| Écriture | Sens |
|---|---|
Algorithme Nom, Variables, Début, Fin |
l’en-tête, la partie des déclarations, puis les instructions entre Début et Fin ; le nom de l’algorithme commence par une majuscule, sans accent (Duree, Recu) ; un algorithme sans variable n’a pas de partie Variables |
x : entier ; a, b : réel |
déclaration : un ou plusieurs noms, deux-points, un type ; un type par ligne |
650 ; 12,5 ; vrai, faux ; 'B' ; "Awa" |
une valeur entière, réelle (avec une virgule), booléenne, un caractère entre apostrophes, une chaîne entre guillemets |
| \(x\leftarrow e\) | \(x\) reçoit la valeur de l’expression \(e\) (se lit « \(x\) reçoit \(e\) ») ; l’ancienne valeur de \(x\) est perdue |
Lire n |
n reçoit la valeur tapée au clavier ; une valeur par ligne |
Écrire "prix :", p |
écrit les valeurs séparées par une espace, puis passe à la ligne : prix : 650 ; un texte entre guillemets est écrit sans ses guillemets |
| réel lu ou écrit | avec une virgule et au moins une décimale : 13,5, 12,0 ; écrit, il prend la plus courte écriture décimale qui désigne la valeur rangée en machine (au plus 17 chiffres significatifs) ; un entier tapé pour une variable réelle est rangé comme réel (20 devient 20,0) |
| booléen écrit | Écrire écrit vrai ou faux |
| \(+\), \(-\), \(\times\), \(/\) | opérations ; \(/\) donne toujours un réel (\(6/3\) donne 2,0) |
| div, mod | quotient et reste de la division entière de deux entiers (\(7\) div \(2=3\), \(7\) mod \(2=1\)) |
| priorités | parenthèses, puis \(\times\), \(/\), div, mod, puis \(+\), \(-\) ; à priorité égale, de gauche à droite |
| types dans un calcul | résultat entier si tous les opérandes sont entiers (sauf pour \(/\)), réel sinon ; un entier rangé dans une variable réelle devient un réel (5 donne 5,0) |
| erreur | arrêt de l’exécution : une variable sans valeur utilisée, une division par zéro (\(/\), div ou mod par 0), une valeur d’un autre type que la variable qui la reçoit |
// texte |
commentaire, jusqu’à la fin de la ligne ; ignoré à l’exécution |
| retrait de deux espaces | sous Variables, et pour les instructions entre Début et Fin |
Les lignes des algorithmes sont numérotées. Une trace d’exécution les suit dans l’ordre où elles sont exécutées : chaque ligne du tableau de trace est un pas, qui donne le numéro de la ligne exécutée, l’instruction, l’état de toutes les variables déclarées après ce pas et ce qu’écrit Écrire. La variable qui vient de recevoir une valeur est en gras ; une case vide signifie que la variable n’a pas encore de valeur. Une chaîne figure entre guillemets et un caractère entre apostrophes, pour distinguer "7" de '7' et de 7. L’en-tête, la partie Variables, les lignes de commentaire, Début et Fin ne produisent aucun pas : elles décrivent l’algorithme, elles ne s’exécutent pas.
La variable et son type
Pourquoi des variables
Au marché Tilène, à Dakar, Fatou achète 3 kg d’oignons à 650 F le kilo (prix illustratif). Pour savoir ce qu’elle doit payer, la vendeuse retient le prix du kilo, retient la quantité, puis multiplie : le calcul demande de garder deux nombres le temps d’en fabriquer un troisième. Un algorithme a le même besoin. Il reçoit des données, calcule des résultats intermédiaires et des résultats finaux ; chacun doit être rangé quelque part, sous un nom, pour être utilisé par une instruction suivante. Cet endroit nommé est une variable.
La variable, une case nommée
Une variable est une case de la mémoire désignée par un nom. Elle contient une valeur d’un type fixé à la déclaration, et garde cette valeur jusqu’à ce qu’une instruction en range une autre. Une variable qui vient d’être déclarée n’a pas encore de valeur.
La figure montre cinq variables, une par type du cours. Le nom est l’étiquette de la case ; il ne change jamais. La valeur est ce que contient la case ; elle change à chaque affectation. Le type dit quelles valeurs la case accepte : prix ne peut contenir qu’un entier, nom qu’une chaîne.
Un nom de variable commence par une lettre, suivie de lettres ou de chiffres, sans espace ni accent : prix, n1, b5000, duree. Les majuscules comptent : prix et Prix désignent deux variables différentes. Un nom parlant (total plutôt que t) rend l’algorithme lisible sans commentaire ; une lettre convient quand le rôle de la variable est dit à côté.
Les cinq types
| Type | Valeurs | Exemples | Opérations de la séance |
|---|---|---|---|
| entier | nombres sans partie décimale | 650, 0, -15 |
\(+\), \(-\), \(\times\), div, mod ; \(/\) donne un réel |
| réel | nombres à virgule | 12,5, 0,03, 12,0 |
\(+\), \(-\), \(\times\), \(/\) |
| booléen | deux valeurs, vrai et faux | vrai, faux |
rangés et écrits (la Séance 2 les calcule et les combine) |
| caractère | un seul symbole, entre apostrophes | 'B', '7', ' ' |
rangés et écrits |
| chaîne | suite de caractères, entre guillemets | "Awa", "à payer :" |
rangées et écrites |
Le type n’est pas un détail d’écriture : il dit ce que la case accepte et quelles opérations ont un sens. On multiplie deux prix, on ne multiplie pas deux noms. Les entiers servent à compter (des kilos entiers, des billets, des minutes) ; les réels servent aux mesures et aux moyennes. Les booléens prennent leur intérêt avec les conditions de la Séance 2 ; dès maintenant, une variable booléenne peut recevoir vrai ou faux et être écrite.
12 est un entier et 12,0 un réel : même nombre, deux types. '7' est un caractère, le symbole du chiffre sept ; "650" est une chaîne de trois caractères. Ni l’un ni l’autre n’est un nombre, et aucun calcul ne s’y applique.
La déclaration et la structure d’un algorithme
Une déclaration x : type crée la variable x et fixe son type pour tout l’algorithme. Plusieurs variables d’un même type se déclarent sur une même ligne, séparées par des virgules : prix, qte, total : entier. Toute variable utilisée est déclarée, une seule fois, dans la partie Variables.
Un algorithme complet a trois parties. L’en-tête donne son nom ; la partie Variables déclare toutes les variables ; les instructions, entre Début et Fin, s’exécutent dans l’ordre, une par ligne. L’algorithme du prix au marché s’écrit ainsi :
Le texte qui suit // est un commentaire : il s’adresse au lecteur et l’exécution l’ignore (lignes 2, 4 et 8). Le retrait de deux espaces montre ce qui appartient à la partie Variables et au corps. Seules les lignes 6 à 9 s’exécutent. La déclaration de la ligne 4 ne donne aucune valeur aux trois variables : leurs cases restent vides jusqu’à la ligne qui les remplit.
Exemple pas à pas : les cinq types
L’algorithme suivant prépare un billet de car : il lit le nom du voyageur, puis range une classe, un prix et l’état du paiement. L’entrée au clavier est Awa.
| Pas | Ligne | Instruction | nom |
classe |
prix |
paye |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 8 | Lire nom |
"Awa" |
||||
| 2 | 9 | classe ← 'B' |
"Awa" |
'B' |
|||
| 3 | 10 | prix ← 3500 |
"Awa" |
'B' |
3500 | ||
| 4 | 11 | paye ← faux |
"Awa" |
'B' |
3500 | faux | |
| 5 | 12 | Écrire nom, classe, prix, paye |
"Awa" |
'B' |
3500 | faux | Awa B 3500 faux |
Au pas 1, Lire range la chaîne tapée ; une chaîne se tape sans guillemets, et la trace la note "Awa" parce que c’est une valeur de type chaîne. Les pas 2 à 4 rangent un caractère, un entier et un booléen, chacun dans une variable de son type. Au pas 5, Écrire écrit les quatre valeurs séparées par une espace : les guillemets et les apostrophes ne sont pas écrits, et le booléen s’écrit faux. La ligne écrite est Awa B 3500 faux.
La forme courte
Les traces des séances suivantes écrivent seulement les instructions, numérotées à partir de 1 : l’en-tête, la partie Variables, Début et Fin sont sous-entendus, et le type de chaque variable se lit sur la valeur qu’elle reçoit (12 pour un entier, 12,0 pour un réel). À gauche, la forme complète, à droite la forme courte du même algorithme :
Les deux formes donnent la même trace tant que chaque valeur est du type de sa variable ; seuls les numéros de ligne diffèrent, de 4 : la multiplication est la ligne 7 de la forme complète et la ligne 3 de la forme courte. Pour les mêmes entrées, 650 et 3, la trace de la forme courte est :
| Pas | Ligne | Instruction | prix |
qte |
total |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 1 | Lire prix |
650 | |||
| 2 | 2 | Lire qte |
650 | 3 | ||
| 3 | 3 | total ← prix × qte |
650 | 3 | 1950 | |
| 4 | 4 | Écrire “à payer :”, total |
650 | 3 | 1950 | à payer : 1950 |
Sans déclarations, la forme courte n’a pas de contrôle de type ; dans les séances suivantes, chaque variable garde le type de sa première valeur. La déclaration d’un tableau (Séance 4) s’écrit parmi les instructions et compte un pas ; Début et Fin reviennent en Séance 5 pour le programme principal. Dans ce document, les algorithmes sont écrits sous la forme complète, car la déclaration des variables est l’objet même de la séance.
Affecter, lire, écrire
Une variable reçoit une valeur de deux façons : par une affectation, qui range le résultat d’un calcul, ou par Lire, qui range une valeur venue du clavier. Écrire fait le chemin inverse : il montre des valeurs à l’écran.
L’affectation
L’affectation \(x\leftarrow e\) calcule la valeur de l’expression \(e\) avec les valeurs actuelles des variables, puis range cette valeur dans \(x\). L’ancienne valeur de \(x\) est perdue ; les variables qui figurent dans \(e\) ne changent pas. Elle se lit « \(x\) reçoit \(e\) ».
L’affectation se déroule toujours en deux temps, dans cet ordre : d’abord la droite est évaluée, entièrement, avec les valeurs présentes dans les cases ; ensuite le résultat est rangé dans la case de gauche. La flèche dessine ce mouvement, de droite à gauche. À gauche de \(\leftarrow\) se trouve toujours une seule variable, la case qui reçoit ; à droite, une expression : une valeur (5), une variable (b), un calcul (a + 1, prix × qte). Une ligne comme 5 \(\leftarrow\) x ou x + 1 \(\leftarrow\) x n’a pas de sens : ni 5 ni x + 1 ne sont des cases.
Lire et Écrire
Lire x attend une valeur tapée au clavier et la range dans x, comme une affectation ; une valeur par Lire, de la forme du type de x : 650 pour un entier, 12,5 pour un réel, Awa pour une chaîne (sans guillemets).
Écrire \(e_1\), \(e_2\), … écrit les valeurs des expressions, séparées par une espace, puis passe à la ligne. Un texte entre guillemets est écrit tel quel, sans ses guillemets. Écrire ne modifie aucune variable.
La forme de ce qui est écrit dépend du type de la valeur : un entier s’écrit avec ses chiffres (1950), un réel avec une virgule et au moins une décimale (12,0, 0,03), un booléen par vrai ou faux, un caractère et une chaîne sans leurs apostrophes ni leurs guillemets. Les espaces d’une ligne écrite viennent des séparateurs et des textes : Écrire "à payer :", total écrit le texte à payer :, une espace, puis la valeur, soit à payer : 1950.
Premier exemple pas à pas : le prix au marché
L’algorithme lit le prix du kilo et la quantité, calcule le prix à payer et l’écrit. L’entrée au clavier est 650, puis 3.
| Pas | Ligne | Instruction | prix |
qte |
total |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 5 | Lire prix |
650 | |||
| 2 | 6 | Lire qte |
650 | 3 | ||
| 3 | 7 | total ← prix × qte |
650 | 3 | 1950 | |
| 4 | 8 | Écrire “à payer :”, total |
650 | 3 | 1950 | à payer : 1950 |
La trace commence à la ligne 5 : les quatre premières lignes ne s’exécutent pas. Le pas 1 range 650 dans prix, le pas 2 range 3 dans qte ; à chaque pas, une seule case reçoit une valeur, et la colonne de total reste vide jusqu’au pas 3. Ce pas calcule \(650\times3=1950\) avec les valeurs présentes dans les cases, puis range le résultat dans total. Au pas 4, Écrire écrit à payer : 1950 ; les variables n’ont pas changé. La figure suivante montre le pas 3 tel qu’il se suit à la main : la ligne exécutée est surlignée, la case qui vient de recevoir une valeur est encadrée en rouge, le pas courant en orange.
Exemple pas à pas : des affectations successives
Une variable peut recevoir plusieurs valeurs au cours d’une exécution ; à chaque instant, elle n’en contient qu’une.
| Pas | Ligne | Instruction | a |
b |
Écrit |
|---|---|---|---|---|---|
| 1 | 5 | a ← 5 |
5 | ||
| 2 | 6 | b ← a + 3 |
5 | 8 | |
| 3 | 7 | a ← b × 2 |
16 | 8 | |
| 4 | 8 | a ← a + 1 |
17 | 8 | |
| 5 | 9 | b ← a - b |
17 | 9 | |
| 6 | 10 | Écrire a, b |
17 | 9 | 17 9 |
Le pas 2 range dans b la valeur de \(\texttt{a}+3\), soit 8. Au pas 3, a passe de 5 à 16 : la valeur 5 est perdue, et b garde 8. L’affectation de la ligne 6 a rangé une valeur dans b, pas un lien avec a : changer a ensuite ne change pas b.
Le pas 4 exécute a \(\leftarrow\) a + 1. La variable figure des deux côtés de la flèche, et l’ordre en deux temps de l’affectation lève toute ambiguïté : la droite est calculée avec l’ancienne valeur, \(16+1=17\), puis 17 est rangé dans a. Cette instruction n’est pas une équation (aucun nombre n’est égal à lui-même plus un) : c’est un ordre, « ajouter 1 à a ». Elle reviendra dans toutes les boucles de la Séance 3 pour compter. Au pas 5, \(17-8=9\) est rangé dans b, et la ligne 10 écrit 17 9. Au total, a a reçu trois valeurs, 5, 16 et 17 ; seule la dernière reste.
L’échange de deux variables
Échanger les valeurs de deux variables est une tâche courante : remettre deux nombres dans l’ordre, permuter deux places. La première idée, ranger b dans a puis a dans b, échoue. L’entrée est 3, puis 8.
| Pas | Ligne | Instruction | a |
b |
Écrit |
|---|---|---|---|---|---|
| 1 | 5 | Lire a |
3 | ||
| 2 | 6 | Lire b |
3 | 8 | |
| 3 | 7 | a ← b |
8 | 8 | |
| 4 | 8 | b ← a |
8 | 8 | |
| 5 | 9 | Écrire a, b |
8 | 8 | 8 8 |
Au pas 3, a reçoit 8 : la valeur 3 est perdue, et plus aucune variable ne la contient. Au pas 4, b reçoit la valeur actuelle de a, soit 8, qu’elle avait déjà. L’algorithme écrit 8 8 : deux copies de b, et non un échange.
Pour ne pas perdre la valeur de a, il faut la mettre de côté avant de l’écraser, dans une troisième variable, appelée ici tmp (temporaire). Comme pour échanger le contenu de deux verres, il faut un troisième verre : l’échange demande trois affectations, dans l’ordre de la figure.
| Pas | Ligne | Instruction | a |
b |
tmp |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 5 | Lire a |
3 | |||
| 2 | 6 | Lire b |
3 | 8 | ||
| 3 | 7 | tmp ← a |
3 | 8 | 3 | |
| 4 | 8 | a ← b |
8 | 8 | 3 | |
| 5 | 9 | b ← tmp |
8 | 3 | 3 | |
| 6 | 10 | Écrire a, b |
8 | 3 | 3 | 8 3 |
Le pas 3 copie 3 dans tmp ; le pas 4 peut alors écraser a par 8 sans dommage, et le pas 5 range dans b la valeur gardée par tmp. L’algorithme écrit 8 3. L’ordre des trois affectations est imposé : chacune copie une valeur avant que la suivante ne l’écrase.
Les expressions
Opérateurs et priorités
À droite de la flèche, une expression combine des valeurs et des variables par des opérateurs. Comme en calcul, une expression sans parenthèses s’évalue selon des priorités : d’abord les parenthèses, puis \(\times\), \(/\), div et mod, enfin \(+\) et \(-\) ; entre deux opérateurs de même priorité, de gauche à droite. Avec \(a=7\) et \(b=2\) :
| expression | valeur écrite |
|---|---|
(a + b) × 3 |
27 |
a + b × 3 |
13 |
a × b div 3 |
4 |
a - b - 1 |
4 |
a / b |
3,5 |
6 / 3 |
2,0 |
a div b |
3 |
a + b × 3 vaut \(7+6=13\) et non \(9\times3=27\) : la multiplication passe avant l’addition. a × b div 3 se lit de gauche à droite, \((7\times2)\) div \(3=14\) div \(3=4\) ; a - b - 1 se lit \((7-2)-1=4\). Dans le doute, des parenthèses disent l’ordre voulu ; elles ne changent rien quand elles suivent la priorité.
La division réelle et la division entière
Le cours distingue deux divisions. La division réelle \(/\) donne toujours un réel, même quand elle tombe juste : \(7/2\) donne 3,5 et \(6/3\) donne 2,0, et non 2. La division entière se fait par deux opérateurs.
Pour deux entiers \(a\geq0\) et \(b>0\), \(q=a\) div \(b\) est le nombre de fois que \(b\) tient entièrement dans \(a\), et \(r=a\) mod \(b\) est ce qui reste : \[a=b\times q+r,\qquad 0\leq r<b.\] div et mod s’appliquent à deux entiers et donnent des entiers ; un diviseur nul arrête l’exécution, comme pour \(/\).
Une durée de 263 minutes contient 4 heures entières, \(263\) div \(60=4\), et il reste \(263\) mod \(60=23\) minutes : \(263=60\times4+23\). Ce découpage revient chaque fois qu’une quantité s’exprime dans deux unités : des minutes en heures et minutes, une somme en billets et en reste, un nombre en dizaines et unités (\(n\) mod 10 donne le chiffre des unités de \(n\), \(n\) div 10 le nombre privé de ce chiffre).
Le type du résultat suit une règle courte : une opération entre entiers donne un entier, sauf \(/\) ; dès qu’un réel intervient, le résultat est réel. La machine range un réel en base 2, avec un nombre limité de chiffres : la valeur rangée est l’arrondi de la valeur exacte, et chaque opération arrondit son résultat. Un nombre comme 0,1 n’a pas d’écriture finie en base 2, de même que \(1/3\) n’en a pas en base 10 : il est rangé arrondi. Un réel s’écrit avec la plus courte écriture décimale qui désigne la valeur rangée en machine (au plus 17 chiffres significatifs), avec au moins une décimale : \(43/3\) s’écrit 14,333333333333334. Le 4 final ne vient pas d’une erreur de calcul : il vient de l’arrondi de \(43/3\) en machine : la valeur rangée, 14,33333333333333392…, est légèrement supérieure à \(43/3\), et sa plus courte écriture qui la distingue de ses voisines finit par 4.
Exemple pas à pas : la conversion d’une durée
En car, un trajet de Dakar à Saint-Louis dure 263 minutes (durée illustrative). L’algorithme convertit une durée en minutes en heures et minutes.
| Pas | Ligne | Instruction | duree |
h |
mn |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 5 | Lire duree |
263 | |||
| 2 | 6 | h ← duree div 60 |
263 | 4 | ||
| 3 | 7 | mn ← duree mod 60 |
263 | 4 | 23 | |
| 4 | 8 | Écrire duree, “min =”, h, “h”, mn, “min” |
263 | 4 | 23 | 263 min = 4 h 23 min |
Le pas 2 calcule le quotient, \(263\) div \(60=4\), le pas 3 le reste, \(263\) mod \(60=23\). La variable duree n’est pas modifiée : elle sert deux fois, et l’algorithme peut l’écrire à la fin. Le tableau suivant donne le résultat pour d’autres durées, dont trois cas limites : moins d’une heure (59), une heure exacte (60), une durée nulle (0). La dernière colonne vérifie la relation \(\texttt{duree}=60\times\texttt{h}+\texttt{mn}\).
duree lue |
h |
mn |
\(60\times h+mn\) |
|---|---|---|---|
| 263 | 4 | 23 | 263 |
| 59 | 0 | 59 | 59 |
| 60 | 1 | 0 | 60 |
| 120 | 2 | 0 | 120 |
| 0 | 0 | 0 | 0 |
Exemple pas à pas : le rendu de monnaie
La BCEAO émet des billets de 10000, 5000, 2000, 1000 et 500 F (gamme 2003). Un commerçant de Thiès doit rendre une somme r ; l’algorithme compte les billets de 5000, 2000 et 1000 F à rendre, en commençant par le plus gros, et laisse le reste, moins de 1000 F, à rendre en pièces ou en billet de 500 F. L’entrée est 17500.
| Pas | Ligne | Instruction | r |
b5000 |
b2000 |
b1000 |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 5 | Lire r |
17500 | ||||
| 2 | 6 | b5000 ← r div 5000 |
17500 | 3 | |||
| 3 | 7 | r ← r mod 5000 |
2500 | 3 | |||
| 4 | 8 | b2000 ← r div 2000 |
2500 | 3 | 1 | ||
| 5 | 9 | r ← r mod 2000 |
500 | 3 | 1 | ||
| 6 | 10 | b1000 ← r div 1000 |
500 | 3 | 1 | 0 | |
| 7 | 11 | r ← r mod 1000 |
500 | 3 | 1 | 0 | |
| 8 | 12 | Écrire b5000, b2000, b1000, r |
500 | 3 | 1 | 0 | 3 1 0 500 |
Chaque coupure demande deux affectations : div compte les billets, puis mod remplace r par ce qui reste à rendre. Au pas 2, \(17500\) div \(5000=3\) billets de 5000 F ; au pas 3, r passe à \(17500\) mod \(5000=2500\). Le pas 6 donne 0 billet de 1000 F, car \(500<1000\) : un quotient nul est un résultat normal, et le pas 7 laisse r à 500 (en gras, puisque la variable a été affectée, même si sa valeur n’a pas changé). L’algorithme écrit 3 1 0 500 : \(3\times5000+1\times2000+0\times1000+500=17500\). L’ordre des lignes compte : si la ligne 7 était oubliée, r vaudrait encore 17500 à la ligne 8, et l’algorithme compterait 8 billets de 2000 F au lieu de 1.
r lu |
b5000 |
b2000 |
b1000 |
reste r |
contrôle |
|---|---|---|---|---|---|
| 17500 | 3 | 1 | 0 | 500 | \(17500\) |
| 8750 | 1 | 1 | 1 | 750 | \(8750\) |
| 4999 | 0 | 2 | 0 | 999 | \(4999\) |
| 1000 | 0 | 0 | 1 | 0 | \(1000\) |
| 0 | 0 | 0 | 0 | 0 | \(0\) |
Exemple pas à pas : la moyenne de trois notes
Au lycée de Kaolack, Cheikh a obtenu trois notes entières sur 20 : 12, 15 et 9. Leur moyenne est un réel.
| Pas | Ligne | Instruction | n1 |
n2 |
n3 |
moy |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 6 | Lire n1 |
12 | ||||
| 2 | 7 | Lire n2 |
12 | 15 | |||
| 3 | 8 | Lire n3 |
12 | 15 | 9 | ||
| 4 | 9 | moy ← (n1 + n2 + n3) / 3 |
12 | 15 | 9 | 12,0 | |
| 5 | 10 | Écrire “moyenne :”, moy |
12 | 15 | 9 | 12,0 | moyenne : 12,0 |
Au pas 4, la somme \(12+15+9=36\) est calculée d’abord, à cause des parenthèses, puis divisée par 3 : \(36/3\) donne 12,0, un réel, et l’algorithme écrit moyenne : 12,0. Sans les parenthèses, la ligne 9 devient moy \(\leftarrow\) n1 + n2 + n3 / 3 ; la division passe avant les additions, et seule la dernière note est divisée :
| Pas | Ligne | Instruction | n1 |
n2 |
n3 |
moy |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 6 | Lire n1 |
12 | ||||
| 2 | 7 | Lire n2 |
12 | 15 | |||
| 3 | 8 | Lire n3 |
12 | 15 | 9 | ||
| 4 | 9 | moy ← n1 + n2 + n3 / 3 |
12 | 15 | 9 | 30,0 | |
| 5 | 10 | Écrire “moyenne :”, moy |
12 | 15 | 9 | 30,0 | moyenne : 30,0 |
L’algorithme écrit moyenne : 30,0, soit \(12+15+3{,}0\) : aucune erreur n’arrête l’exécution, et le résultat est faux. Pour les notes 13, 14 et 16, la moyenne \(43/3\) ne tombe pas juste :
| Pas | Ligne | Instruction | n1 |
n2 |
n3 |
moy |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 6 | Lire n1 |
13 | ||||
| 2 | 7 | Lire n2 |
13 | 14 | |||
| 3 | 8 | Lire n3 |
13 | 14 | 16 | ||
| 4 | 9 | moy ← (n1 + n2 + n3) / 3 |
13 | 14 | 16 | 14,333333333333334 | |
| 5 | 10 | Écrire “moyenne :”, moy |
13 | 14 | 16 | 14,333333333333334 | moyenne : 14,333333333333334 |
Exemple pas à pas : la surface d’une parcelle
À Ziguinchor, Aïssatou mesure une parcelle rectangulaire de 20,0 m sur 15,0 m (dimensions illustratives). L’algorithme calcule sa surface en mètres carrés, puis la convertit en hectares : un hectare vaut 10000 m².
| Pas | Ligne | Instruction | long |
larg |
surf |
ha |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 5 | Lire long |
20,0 | ||||
| 2 | 6 | Lire larg |
20,0 | 15,0 | |||
| 3 | 7 | surf ← long × larg |
20,0 | 15,0 | 300,0 | ||
| 4 | 8 | ha ← surf / 10000 |
20,0 | 15,0 | 300,0 | 0,03 | |
| 5 | 9 | Écrire surf, “m² =”, ha, “ha” |
20,0 | 15,0 | 300,0 | 0,03 | 300,0 m² = 0,03 ha |
Les longueurs sont des mesures : elles se tapent avec une virgule et se rangent dans des réels. La surface, \(20{,}0\times15{,}0=300{,}0\) m², est un réel ; sa conversion, \(300{,}0/10000\), donne 0,03 ha. L’algorithme écrit 300,0 m² = 0,03 ha. Les deux commentaires de l’algorithme rappellent l’unité de chaque variable : c’est leur meilleur usage.
Les erreurs fréquentes
Trois erreurs arrêtent l’exécution : une variable utilisée sans valeur, une valeur d’un autre type que la variable qui la reçoit, une division par zéro. Une quatrième, la flèche lue comme une égalité, n’arrête rien et donne un résultat faux.
La variable sans valeur
Un commerçant cumule ses achats de la journée ; l’algorithme lit un achat et l’ajoute au total.
| Pas | Ligne | Instruction | achat |
total |
Écrit |
|---|---|---|---|---|---|
| 1 | 5 | Lire achat |
2500 | ||
| 2 | 6 | total ← total + achat |
2500 | ? | arrêt : total sans valeur |
Au pas 2, la droite total + achat demande la valeur de total, et la case est vide : déclarer une variable ne lui donne pas de valeur. L’exécution s’arrête. Il faut donner à total une valeur de départ avant de s’en servir :
| Pas | Ligne | Instruction | achat |
total |
Écrit |
|---|---|---|---|---|---|
| 1 | 5 | total ← 0 |
0 | ||
| 2 | 6 | Lire achat |
2500 | 0 | |
| 3 | 7 | total ← total + achat |
2500 | 2500 | |
| 4 | 8 | Écrire “total :”, total |
2500 | 2500 | total : 2500 |
L’algorithme écrit total : 2500. Cette valeur de départ s’appelle une initialisation ; toute variable qui figure à droite d’une flèche, ou dans un Écrire, doit avoir reçu une valeur auparavant, par une affectation ou par Lire.
Une valeur d’un autre type
Une tontine de Saint-Louis partage une somme entre n membres ; chaque part est un nombre entier de francs. Une première version écrit la part avec \(/\). Pour 10000 F et 4 membres :
| Pas | Ligne | Instruction | somme |
n |
part |
reste |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 5 | Lire somme |
10000 | ||||
| 2 | 6 | Lire n |
10000 | 4 | |||
| 3 | 7 | part ← somme / n |
10000 | 4 | arrêt : part entier, valeur réelle |
\(10000/4\) donne 2500,0, un réel, même si la division tombe juste ; part est déclarée entière et ne peut pas le recevoir : l’exécution s’arrête. La division entière convient : part \(\leftarrow\) somme div n. Pour 10000 F et 3 membres :
| Pas | Ligne | Instruction | somme |
n |
part |
reste |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 5 | Lire somme |
10000 | ||||
| 2 | 6 | Lire n |
10000 | 3 | |||
| 3 | 7 | part ← somme div n |
10000 | 3 | 3333 | ||
| 4 | 8 | reste ← somme mod n |
10000 | 3 | 3333 | 1 | |
| 5 | 9 | Écrire “part :”, part, “reste :”, reste |
10000 | 3 | 3333 | 1 | part : 3333 reste : 1 |
Chaque membre reçoit 3333 F et il reste 1 F : \(3\times3333+1=10000\). Le sens inverse est permis : un entier rangé dans une variable réelle devient un réel (5 donne 5,0), puisqu’aucune information n’est perdue.
La division par zéro
Avec 0 membre, le même algorithme demande \(10000\) div \(0\) :
| Pas | Ligne | Instruction | somme |
n |
part |
reste |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 5 | Lire somme |
10000 | ||||
| 2 | 6 | Lire n |
10000 | 0 | |||
| 3 | 7 | part ← somme div n |
10000 | 0 | arrêt : division par zéro |
Aucun nombre multiplié par 0 ne donne 10000 : la division par zéro n’a pas de résultat, et l’exécution s’arrête à la ligne 7. Les conditions de la Séance 2 permettent de tester le diviseur avant de diviser.
La flèche lue comme une égalité
a \(\leftarrow\) b range la valeur de b dans a ; b \(\leftarrow\) a range la valeur de a dans b. En mathématiques, \(a=b\) et \(b=a\) disent la même chose ; en pseudo-code, ces deux affectations font deux choses différentes. De même, n \(\leftarrow\) n + 1 n’est pas une équation sans solution, mais l’ordre d’ajouter 1 à n. Le pseudo-code du cours n’écrit jamais l’affectation avec \(=\) ; ce signe sert, à partir de la Séance 2, à comparer deux valeurs.
Exercices corrigés
Les trois exercices suivants reprennent les gestes de la séance : suivre des affectations successives dans une trace, décomposer une quantité par div et mod en vérifiant les cas limites, prévoir la valeur et le type d’une expression. Chaque correction énonce la règle appliquée, donne la trace, résume les résultats dans un tableau, conclut et signale l’erreur la plus répandue.
Exercice 1 : affectations successives
- Donner les valeurs de
x,yetzaprès chaque ligne de 5 à 10. - Qu’écrit l’algorithme ?
- Quelle valeur de
xest perdue, et à quelle ligne ? - On échange les lignes 9 et 10. Qu’écrit l’algorithme ?
(a) Règle appliquée. Une affectation calcule sa droite avec les valeurs présentes dans les cases, puis range le résultat dans la seule variable de gauche ; les autres variables ne changent pas. On remplit donc la trace ligne par ligne, en recopiant les valeurs qui ne changent pas.
| Pas | Ligne | Instruction | x |
y |
z |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 5 | x ← 4 |
4 | |||
| 2 | 6 | y ← x × 3 |
4 | 12 | ||
| 3 | 7 | z ← y - x |
4 | 12 | 8 | |
| 4 | 8 | x ← z + y |
20 | 12 | 8 | |
| 5 | 9 | y ← y + 1 |
20 | 13 | 8 | |
| 6 | 10 | z ← x mod y |
20 | 13 | 7 | |
| 7 | 11 | Écrire x, y, z |
20 | 13 | 7 | 20 13 7 |
Ligne 6 : \(4\times3=12\). Ligne 7 : \(12-4=8\). Ligne 8 : \(8+12=20\). Ligne 9 : \(12+1=13\). Ligne 10 : \(20\) mod \(13=7\), car \(20=13\times1+7\). En résumé :
| Ligne | x |
y |
z |
variable affectée |
|---|---|---|---|---|
| 5 | 4 | x |
||
| 6 | 4 | 12 | y |
|
| 7 | 4 | 12 | 8 | z |
| 8 | 20 | 12 | 8 | x |
| 9 | 20 | 13 | 8 | y |
| 10 | 20 | 13 | 7 | z |
(b) La ligne 11 écrit les trois valeurs séparées par une espace : 20 13 7.
(c) La valeur 4, rangée à la ligne 5, est perdue à la ligne 8, quand x reçoit 20. Elle a servi avant de disparaître, aux lignes 6 et 7.
(d) Règle appliquée : une expression utilise les valeurs au moment où elle est calculée. Après l’échange, z est calculée quand y vaut encore 12 :
| Pas | Ligne | Instruction | x |
y |
z |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 5 | x ← 4 |
4 | |||
| 2 | 6 | y ← x × 3 |
4 | 12 | ||
| 3 | 7 | z ← y - x |
4 | 12 | 8 | |
| 4 | 8 | x ← z + y |
20 | 12 | 8 | |
| 5 | 9 | z ← x mod y |
20 | 12 | 8 | |
| 6 | 10 | y ← y + 1 |
20 | 13 | 8 | |
| 7 | 11 | Écrire x, y, z |
20 | 13 | 8 | 20 13 8 |
\(20\) mod \(12=8\), puis y passe à 13 : l’algorithme écrit 20 13 8. Les mêmes instructions, dans un autre ordre, donnent un autre résultat.
Conclusion. Une trace se remplit pas à pas, une case modifiée par pas ; la valeur d’une variable est celle de son dernier rangement, et l’ordre des lignes fait partie de l’algorithme.
Calculer une ligne avec une valeur qui n’est pas encore, ou n’est plus, dans la case : la ligne 7 avec la valeur finale de x (20 au lieu de 4) donnerait \(12-20=-8\) au lieu de 8 ; après l’échange de (d), la ligne 9 avec la valeur finale de y donnerait \(20\) mod \(13=7\) au lieu de \(20\) mod \(12=8\). Une trace écrite case par case évite cette erreur : à chaque pas, on ne lit que la ligne précédente du tableau.
Exercice 2 : une durée en secondes
Un chronomètre donne le temps d’une course en secondes (temps illustratif).
- Pour l’entrée 8125, donner les valeurs de
t,h,mnetsaprès chaque ligne. - Qu’écrit l’algorithme pour 3600 ? Pour 59 ?
- On supprime la ligne 7. Qu’écrit l’algorithme pour 8125 et pour 3600 ?
- Quelle expression redonne la durée lue à partir de
h,mnets?
(a) Règle appliquée : \(a=b\times q+r\), \(0\leq r<b\). Une heure vaut 3600 secondes : div 3600 compte les heures entières, mod 3600 donne les secondes qui restent, moins d’une heure, que l’on découpe ensuite en minutes de 60 secondes.
| Pas | Ligne | Instruction | t |
h |
mn |
s |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 5 | Lire t |
8125 | ||||
| 2 | 6 | h ← t div 3600 |
8125 | 2 | |||
| 3 | 7 | t ← t mod 3600 |
925 | 2 | |||
| 4 | 8 | mn ← t div 60 |
925 | 2 | 15 | ||
| 5 | 9 | s ← t mod 60 |
925 | 2 | 15 | 25 | |
| 6 | 10 | Écrire h, “h”, mn, “min”, s, “s” |
925 | 2 | 15 | 25 | 2 h 15 min 25 s |
\(8125=3600\times2+925\) : h reçoit 2 et la ligne 7 range 925 dans t. Puis \(925=60\times15+25\) : mn reçoit 15 et s reçoit 25. L’algorithme écrit 2 h 15 min 25 s.
(b) Pour 3600, \(3600\) div \(3600=1\) et le reste est nul : 1 h 0 min 0 s. Pour 59, aucune heure ni aucune minute entière : 0 h 0 min 59 s. Un quotient nul est un résultat comme un autre.
| Pas | Ligne | Instruction | t |
h |
mn |
s |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 5 | Lire t |
3600 | ||||
| 2 | 6 | h ← t div 3600 |
3600 | 1 | |||
| 3 | 7 | t ← t mod 3600 |
0 | 1 | |||
| 4 | 8 | mn ← t div 60 |
0 | 1 | 0 | ||
| 5 | 9 | s ← t mod 60 |
0 | 1 | 0 | 0 | |
| 6 | 10 | Écrire h, “h”, mn, “min”, s, “s” |
0 | 1 | 0 | 0 | 1 h 0 min 0 s |
(c) Sans la ligne 7, t garde la durée entière, et mn compte toutes les minutes, celles des heures comprises :
| Pas | Ligne | Instruction | t |
h |
mn |
s |
Écrit |
|---|---|---|---|---|---|---|---|
| 1 | 5 | Lire t |
8125 | ||||
| 2 | 6 | h ← t div 3600 |
8125 | 2 | |||
| 3 | 7 | mn ← t div 60 |
8125 | 2 | 135 | ||
| 4 | 8 | s ← t mod 60 |
8125 | 2 | 135 | 25 | |
| 5 | 9 | Écrire h, “h”, mn, “min”, s, “s” |
8125 | 2 | 135 | 25 | 2 h 135 min 25 s |
t lu |
h |
mn |
s |
écrit | écrit sans la ligne 7 |
|---|---|---|---|---|---|
| 8125 | 2 | 15 | 25 | 2 h 15 min 25 s |
2 h 135 min 25 s |
| 3600 | 1 | 0 | 0 | 1 h 0 min 0 s |
1 h 60 min 0 s |
| 59 | 0 | 0 | 59 | 0 h 0 min 59 s |
0 h 0 min 59 s |
Pour 8125, \(8125\) div \(60=135\) minutes au lieu de 15 ; pour 3600, 60 minutes au lieu de 0. Les secondes restent justes, car \(8125\) mod \(60=925\) mod \(60=25\). Pour 59, l’erreur ne se voit pas : les deux versions écrivent la même chose, et seul un cas d’au moins une heure révèle la ligne oubliée.
(d) h × 3600 + mn × 60 + s : \(2\times3600+15\times60+25=7200+900+25=8125\). La relation \(a=b\times q+r\) appliquée deux fois redonne la durée : c’est le contrôle d’une conversion.
Conclusion. Une conversion en plusieurs unités alterne div (combien d’unités entières) et mod (ce qui reste) ; elle se vérifie en recomposant la valeur de départ, et sur des cas limites : une unité exacte, moins d’une unité.
Oublier de remplacer la quantité par son reste entre deux unités (la ligne 7). Le test sur une petite valeur, comme 59, ne détecte pas l’oubli ; il faut un cas qui contient au moins une unité de chaque sorte.
Exercice 3 : types et priorités
Une moyenne compte le devoir d une fois et l’examen e deux fois.
- Qu’écrit l’algorithme pour 12 et 15 ?
- Avec \(d=12\) et \(e=15\), donner la valeur et le type de
d + 2 × e, puis de cette somme divisée par 3 avec \(/\), avec div, et de son reste par mod 3. - La ligne 8 devient
m\(\leftarrow\)d + 2 × e / 3. Qu’écrit l’algorithme ? - La partie Variables devient
d, e, m : entier(une ligne). Que se passe-t-il à la ligne 7 ? Que faut-il écrire, et que perd-on ?
(a) Règle appliquée : parenthèses, puis \(\times\), puis \(+\), puis \(/\) hors des parenthèses. \(12+2\times15=12+30=42\), puis \(42/3\) donne 14,0 :
| Pas | Ligne | Instruction | d |
e |
m |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 6 | Lire d |
12 | |||
| 2 | 7 | Lire e |
12 | 15 | ||
| 3 | 8 | m ← (d + 2 × e) / 3 |
12 | 15 | 14,0 | |
| 4 | 9 | Écrire “moyenne :”, m |
12 | 15 | 14,0 | moyenne : 14,0 |
L’algorithme écrit moyenne : 14,0 : m est réelle, et \(/\) donne un réel.
(b) Règle appliquée : entre entiers, le résultat est entier, sauf pour \(/\).
| expression | valeur | type |
|---|---|---|
d + 2 × e |
42 | entier |
(d + 2 × e) / 3 |
14,0 | réel |
(d + 2 × e) div 3 |
14 | entier |
(d + 2 × e) mod 3 |
0 | entier |
d + 2 × e / 3 |
22,0 | réel |
La dernière ligne du tableau prépare la question (c).
(c) Sans parenthèses, \(2\times15/3\) se calcule d’abord, de gauche à droite : \(30/3\) donne 10,0, ajouté à 12 :
| Pas | Ligne | Instruction | d |
e |
m |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 6 | Lire d |
12 | |||
| 2 | 7 | Lire e |
12 | 15 | ||
| 3 | 8 | m ← d + 2 × e / 3 |
12 | 15 | 22,0 | |
| 4 | 9 | Écrire “moyenne :”, m |
12 | 15 | 22,0 | moyenne : 22,0 |
L’algorithme écrit moyenne : 22,0, une moyenne supérieure aux deux notes : le signe d’une priorité oubliée.
(d) Avec une seule ligne de déclarations, l’affectation devient la ligne 7. \(42/3\) donne le réel 14,0, qu’une variable entière ne peut pas recevoir : l’exécution s’arrête à la ligne 7.
| Pas | Ligne | Instruction | d |
e |
m |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 5 | Lire d |
12 | |||
| 2 | 6 | Lire e |
12 | 15 | ||
| 3 | 7 | m ← (d + 2 × e) / 3 |
12 | 15 | arrêt : m entier, valeur réelle |
Avec m entière, il faut la division entière : m \(\leftarrow\) (d + 2 × e) div 3. Pour 12 et 15, elle donne 14, la même valeur. Pour 13 et 15, la somme vaut 43 : div donne 14, alors que \(43/3\) s’écrit 14,333333333333334 ; la partie décimale est perdue.
| Pas | Ligne | Instruction | d |
e |
m |
Écrit |
|---|---|---|---|---|---|---|
| 1 | 5 | Lire d |
13 | |||
| 2 | 6 | Lire e |
13 | 15 | ||
| 3 | 7 | m ← (d + 2 × e) div 3 |
13 | 15 | 14 | |
| 4 | 8 | Écrire “moyenne :”, m |
13 | 15 | 14 | moyenne : 14 |
Conclusion. Le type d’une expression se lit sur ses opérateurs : \(/\) donne un réel, div et mod des entiers ; le type de la variable qui reçoit doit être celui du résultat.
Croire que d + 2 × e / 3 « divise le tout par 3 ». La division ne porte que sur le terme écrit juste avant elle ; une moyenne s’écrit toujours avec des parenthèses autour de la somme.
À retenir
| Instruction | Effet | Pas | Arrêt possible |
|---|---|---|---|
x : entier |
crée la case x, de ce type, sans valeur |
aucun | — |
| \(x\leftarrow e\) | calcule \(e\), range la valeur dans \(x\) | 1 | variable sans valeur, division par zéro, type |
Lire x |
range dans x la valeur tapée |
1 | valeur d’un autre type |
| Écrire \(e_1\), \(e_2\) | écrit les valeurs, passe à la ligne | 1 | variable sans valeur, division par zéro |
- Une variable a un nom, un type et une valeur ; une affectation remplace la valeur, l’ancienne est perdue.
- \(x\leftarrow e\) se lit de droite à gauche, en deux temps : calculer \(e\), puis ranger ;
n\(\leftarrow\)n + 1n’est pas une équation. - Échanger deux variables demande une troisième :
tmp\(\leftarrow\)a,a\(\leftarrow\)b,b\(\leftarrow\)tmp. - \(/\) donne un réel ; div et mod donnent le quotient et le reste : \(a=b\times q+r\), \(0\leq r<b\).
- Toute variable reçoit une valeur avant de servir ; un réel ne se range pas dans un entier.
- Une trace : une ligne par pas, la ligne exécutée, les valeurs après le pas, ce qui est écrit.
Prochaine séance
La Séance 2 introduit les conditions : une comparaison de valeurs donne un booléen, vrai ou faux, et l’instruction Si … Alors … Sinon … FinSi choisit, d’après ce booléen, les lignes à exécuter ; les conditions se combinent par ET, OU et NON.
Références
- Cormen — Algorithms Unlocked, MIT Press, 2013 (ch. 1, « What Are Algorithms and Why Should You Care? », et ch. 2, « How to Describe and Evaluate Computer Algorithms »).
- Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4e éd., MIT Press, 2022 (ch. 2, « Getting Started », § 2.1 : conventions du pseudo-code, variables et affectation).
- Bhargava — Grokking Algorithms, 2e éd., Manning, 2024 (ch. 1, « Introduction to Algorithms »).
- Notes de cours en ligne : CS50 (Harvard), 6.100A (MIT), CS106A (Stanford), séances sur les variables, les types et les expressions.
Pour cette séance
Les slides
À lire en ligne