Algorithms and pseudocode · Algorithmes et pseudocode
| English | Français |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algorithme |
| sequence/ˈsiːkwəns/ | séquence |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | déterministe |
| identifier table/aɪˈdentɪfaɪə ˈteɪbl/ | tableau d'identifiants |
| variable/ˈveərɪəbl/ | variable |
| data type/ˈdeɪtə taɪp/ | type de donnée |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocode |
| assignment/əˈsaɪnmənt/ | affectation |
| loop/luːp/ | boucle |
| count-controlled loop/kaʊnt kənˈtrəʊld luːp/ | boucle comptée |
| pre-condition loop/priː kənˈdɪʃn luːp/ | boucle à précondition |
| post-condition loop/pəʊst kənˈdɪʃn luːp/ | boucle à postcondition |
| iteration/ˌɪtəˈreɪʃn/ | itération |
| selection/sɪˈlekʃn/ | naturelle |
| flowchart/ˈfləʊtʃɑːt/ | diagramme de flux |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | affinement successif |
The most expensive hyphen in history
- On 22 July 1962 the Mariner 1 rocket, bound for Venus, was blown up 293 seconds after launch.
- The cause was one missing bar over a symbol in the guidance equations. The computer followed the written steps exactly, and the written steps were wrong.
- A computer never fills in what you meant. Every step you give it must have exactly one meaning.
- That is why this lesson is about writing steps a machine can follow: algorithms 算法.
Le trait d'union le plus cher de l'histoire
- Le 22 juillet 1962, la fusée Mariner 1, destinée à Vénus, a été détruite 293 secondes après le lancement.
- La cause était une barre manquante au-dessus d'un symbole dans les équations de guidage. L'ordinateur a suivi les instructions écrites exactement, et ces instructions étaient erronées.
- Un ordinateur ne comble jamais ce que vous aviez voulu dire. Chaque étape que vous lui donnez doit avoir exactement un sens.
- C'est pourquoi cette leçon porte sur l'écriture d'étapes qu'une machine peut suivre : algorithms 算法.
What an algorithm is
- An algorithm is a solution to a problem expressed as a sequence of defined steps.
- Each step is unambiguous (one meaning), deterministic 确定性 (same input → same output), finite (the steps end) and effective (each step can actually be done).
- It says what to do, independent of any programming language, and every one follows input → process → output.
Every algorithm has the same shape: input, process, output
Qu'est-ce qu'un algorithme ?
- Un algorithme est une solution à un problème exprimée sous forme de série d'étapes définies.
- Chaque étape est non ambiguë (un seul sens), déterministe (même entrée → même sortie), finie (les étapes se terminent) et effective (chaque étape peut réellement être faite).
- Il dit quoi faire, indépendamment de tout langage de programmation, et chacun suit le schéma entrée → traitement → sortie.
Chaque algorithme a la même structure : entrée, processus, sortie
An algorithm is "deterministic". This means: · Un algorithme est « déterministe ». Cela signifie :
Deterministic = same input → same output every time. (Finite = the steps end; unambiguous = one meaning per step.) · Déterministe = même entrée → même sortie à chaque fois. (Fini = les étapes se terminent ; non ambigu = une signification par étape.)
Worked example: the identifier table
- Before writing code, list every piece of data in an identifier table 标识符表: its variable 变量 name, its data type 数据类型 and a description.
- A shop's stock program stores
"Fruit",20/02/2025,12.67andTRUE. The exam asks for a name and a type for each. Category : STRING(a category of stock),DateSold : DATE(when it was sold),ItemCost : REAL(the cost),InStock : BOOLEAN(is it in stock?).- One mark per row for the name and the type, so write the type exactly as the pseudocode guide does:
INTEGER,REAL,STRING,CHAR,BOOLEAN,DATE.
An identifier table names every piece of data before you write code
Exemple résolu : le tableau des identifiants
- Avant d'écrire du code, listez chaque élément de données dans un identifier table 标识符表 : son variable 变量 nom, son data type 数据类型 et une description.
- Un programme de stock de magasin stocke
"Fruit",20/02/2025,12.67etTRUE. L'examen demande un nom et un type pour chacun. Category : STRING(une catégorie de stock),DateSold : DATE(quand il a été vendu),ItemCost : REAL(le coût),InStock : BOOLEAN(est-il en stock ?).- Un point par ligne pour le nom ET le type, donc écrivez le type exactement comme le guide pseudocode le fait :
INTEGER,REAL,STRING,CHAR,BOOLEAN,DATE.
Un tableau des identifiants nomme chaque élément de données avant d'écrire du code
In an identifier table, the data type for a value such as 12.67 (a cost) is ____. · Dans une table d'identifiants, le type de données pour une valeur telle que 12.67 (un coût) est ____.
A number with a decimal part is a REAL. INTEGER is for whole numbers, STRING for text, BOOLEAN for TRUE/FALSE and DATE for a date. · Un nombre avec une partie décimale est un RÉEL. INTEGER est pour les nombres entiers, STRING pour le texte, BOOLEAN pour VRAI/FAUX et DATE pour une date.
The three constructs
IF … THEN … ELSE … ENDIF
- Assignment 赋值 stores a value with an arrow,
Total ← Total + Value;=is for comparison.DIVis whole-number division andMODthe remainder, so17 MOD 5 = 2.
The three building blocks of any algorithm
Les trois constructeurs
SI … ALORS … SINON … FIN SI
- L'affectation stocke une valeur avec une flèche,
Total ← Total + Value;=est utilisé pour la comparaison.DIVest la division entière etMODle reste, donc17 MOD 5 = 2.
INPUT Age # sequence
IF Age >= 18 THEN
# selection
ENDIF
OUTPUT "Adult"
ELSE
OUTPUT "Minor"
ENDIF
FOR Count <- 1 TO 10 # iteration
OUTPUT Count
NEXT Count
Les trois briques de base de tout algorithme
Selection: follow the IF / ELSE branches · Sélection : suivez les branches IF / ELSE
Drag the score and watch which branch runs. Selection tests each condition in turn and takes the FIRST one that is true — that is how IF … ELSE IF … ELSE works. · Faites glisser la note et observez quelle branche s'exécute. La sélection teste chaque condition à tour de rôle et prend la PREMIÈRE qui est vraie — c'est ainsi que fonctionne IF … ELSE IF … ELSE.
Match each of the three programming constructs to what it does. · Reliez chacun des trois constructeurs de programmation à ce qu'il fait.
Every algorithm is built from just three constructs — sequence, selection and iteration. · Tout algorithme est construit à partir de seulement trois constructeurs — séquence, sélection et itération.
In this pseudocode, which symbol means assignment (store a value)? · Dans ce pseudocode, quel symbole signifie affectation (stocker une valeur) ?
Assignment uses ← (e.g. x ← 5); = is reserved for comparison. · L'affectation utilise ← (par ex. x ← 5) ; = est réservé pour la comparaison.
What is the value of 17 MOD 5? · Quelle est la valeur de 17 MOD 5 ?
MOD gives the remainder: $17 = 3 \times 5 + 2$, so 17 MOD 5 = 2. (17 DIV 5 = 3.) · MOD donne le reste : $17 = 3 \times 5 + 2$, donc 17 MOD 5 = 2. (17 DIV 5 = 3.)
Which loop?
FOR … NEXTwhen you know how many times: a count-controlled loop 计数循环.WHILE … ENDWHILEtests the condition before each pass, so the body may run zero times: a pre-condition loop 前测循环.REPEAT … UNTILtests after each pass, so the body always runs at least once: a post-condition loop 后测循环. Validating an input is the classic case.- A "describe the iteration construct" answer names the loop, says where the condition is tested, and gives the consequence.
A WHILE loop tests before the body runs; a REPEAT … UNTIL loop tests after it
Quelle boucle ?
FOR … NEXTquand vous savez combien de fois : une boucle contrôlée par compteur 计数循环.WHILE … ENDWHILEteste la condition avant chaque passage, donc le corps peut s'exécuter zéro fois : une boucle à précondition 前测循环.REPEAT … UNTILteste après chaque passage, donc le corps s'exécute toujours au moins une fois : une boucle à postcondition 后测循环. Valider une saisie est le cas classique.- Une réponse « décrire le constructeur d'itération » nomme la boucle, dit où la condition est testée, et donne la conséquence.
Une boucle WHILE teste avant que le corps s'exécute ; une boucle REPEAT … UNTIL teste après
How does a WHILE loop differ from a REPEAT...UNTIL loop? · Comment une boucle WHILE diffère-t-elle d'une boucle REPEAT...UNTIL ?
WHILE checks first (can run 0 times); REPEAT...UNTIL checks after, so it always runs at least once. · WHILE vérifie d'abord (peut s'exécuter 0 fois) ; REPEAT...UNTIL vérifie après, donc elle s'exécute toujours au moins une fois.
A FOR loop is count-controlled (it repeats a fixed number of times), while a WHILE loop is condition-controlled (it repeats until a condition changes). · Une boucle FOR est contrôlée par un compteur (elle répète un nombre fixe de fois), tandis qu'une boucle WHILE est contrôlée par une condition (elle répète jusqu'à ce qu'une condition change).
Use FOR when you know how many passes; use WHILE/REPEAT when you loop until something becomes true. · Utilisez FOR lorsque vous savez combien de passages sont nécessaires ; utilisez WHILE/REPEAT lorsque vous bouclez jusqu'à ce que quelque chose devienne vrai.
Worked example: from words to pseudocode
- Task: input 100 integer values, add up only the positive ones, and output the total.
- Plan the data first:
Count,TotalandNextNumber, allINTEGER. Then the three constructs do the rest.
- The follow-up asks you to identify the constructs: iteration (the
FORloop repeats the input 100 times), selection (theIFdecides whether a value is added) and sequence (the statements run in order).
Exemple résolu : des mots au pseudocode
- Tâche : saisir 100 valeurs entières, additionner uniquement les positives, et afficher le total.
- Planifier les données d'abord :
Count,TotaletNextNumber, tousINTEGER. Puis les trois constructeurs font le reste.
DECLARE Count, Total, NextNumber : INTEGER
Total <- 0
FOR Count <- 1 TO 100
INPUT NextNumber
IF NextNumber > 0 THEN
Total <- Total + NextNumber
ENDIF
NEXT Count
OUTPUT Total
- La question suivante demande d'identifier les constructeurs : itération (la boucle
FORrépète la saisie 100 fois), sélection (leIFdécide si une valeur est ajoutée) et séquence (les instructions s'exécutent dans l'ordre).
Spotting constructs in an extract
- A favourite question shows five pseudocode extracts and asks you to tick which of assignment, selection, iteration each one uses.
Result ← CalculateTotal()is an assignment.WHILE IsClosedis iteration.REPEAT … INPUT Value … UNTIL Sales[4] > Valueis iteration and assignment (INPUTstores a value). IF Sales[Current] <= 150 THEN Discount ← TRUE ENDIF- Look at every line of the extract, not only the first one. A row may need two ticks.
Repérer des constructeurs dans un extrait
- Une question favorite montre cinq extraits de pseudocode et demande de cocher lesquels utilisent l'affectation, la sélection, l'itération.
Result ← CalculateTotal()est une affectation.WHILE IsClosedest une itération.REPEAT … INPUT Value … UNTIL Sales[4] > Valueest une itération et une affectation (INPUTstocke une valeur). IF Sales[Current] <= 150 THEN Discount ← TRUE FIN SI- Regardez chaque ligne de l'extrait, pas seulement la première. Une ligne peut nécessiter deux coches.
Which constructs does this extract use? REPEAT … INPUT Value … UNTIL Total > 100. Select all · tout that apply. · Quels constructeurs cette extraire utilise-t-yle ? REPEAT … INPUT Value … UNTIL Total > 100. Sélectionnez tous ceux qui s'appliquent.
REPEAT … UNTIL is iteration, and INPUT Value stores a value, which counts as assignment. There is no IF or CASE, so no selection — the UNTIL condition controls the loop, it does not choose between branches. · REPEAT … UNTIL est une itération, et INPUT Value stocke une valeur, ce qui compte comme une affectation. Il n'y a ni IF ni CASE, donc pas de sélection — la condition UNTIL contrôle la boucle, elle ne choisit pas entre des branches.
Flowcharts
- A flowchart 流程图 documents the same algorithm as a picture. Ovals are
STARTandEND, rectangles are processes, parallelograms areINPUT/OUTPUT, and a diamond is a decision. - A diamond is where selection happens, and a flow line that goes back up the chart is a loop.
- The exam asks both ways: pseudocode from a flowchart, and a flowchart from pseudocode or structured English. Every symbol you draw should map to one line of pseudocode.
Each flowchart symbol maps to one kind of pseudocode statement
Fluxogrammes
- Un diagramme de flux 流程图 documente le même algorithme qu'une image. Les ovales sont
STARTetEND, les rectangles sont des processus, les parallélogrammes sontINPUT/OUTPUT, et un losange est une décision. - Un losange est là où se fait la sélection, et une ligne de flux qui revient vers le haut du diagramme est une boucle.
- L'examen demande les deux sens : pseudocode à partir de un diagramme de flux, et un diagramme de flux à partir de pseudocode ou anglais structuré. Chaque symbole que vous dessinez doit correspondre à une ligne de pseudocode.
Chaque symbole de diagramme de flux correspond à un type de déclaration de pseudocode
In a flowchart, what does a diamond represent? · Dans un organigramme, que représente un losange ?
Diamonds are where selection happens, and a diamond whose flow line goes back up the chart is a loop test. Rectangles are processes, parallelograms input/output, ovals START and END. · Les losanges sont là où la sélection se produit, et un losange dont la ligne de flux remonte dans l'organigramme est un test de boucle. Les rectangles sont des processus, les parallélogrammes entrées/sorties, les ovales DÉBUT et FIN.
Worked example: the guessing game
- The program picks a random integer from 1 to 100, then asks for guesses until the user gets it. The user must guess at least once, so the loop is a
REPEAT … UNTIL.
- Follow the flowchart: one decision diamond for the loop test, two for the hints, and every flow line ends up back at
INPUT Guessor atEND.
The guessing game as a flowchart: the loop returns to the input until the guess matches
Exemple résolu : le jeu de devinettes
- Le programme tire un entier aléatoire de 1 à 100, puis demande des indivinettes jusqu'à ce que l'utilisateur trouve. L'utilisateur doit indiviner au moins une fois, donc la boucle est une
REPEAT … UNTIL.
DECLARE Target, Guess : INTEGER
Target <- INT(RAND(100)) + 1
REPEAT
INPUT Guess
IF Guess < Target THEN
OUTPUT "Too low"
ELSE
IF Guess > Target THEN
OUTPUT "Too high"
ENDIF
ENDIF
UNTIL Guess = Target
OUTPUT "Correct"
- Suivez le diagramme de flux : un losange de décision pour le test de boucle, deux pour les indices, et chaque ligne de flux aboutit soit à
INPUT Guess, soit àEND.
Le jeu de devinettes sous forme de diagramme de flux : la boucle retourne vers la saisie jusqu'à ce que l'indovinette corresponde
Why is REPEAT … UNTIL the right loop for the guessing game? · Pourquoi REPEAT … UNTIL est-il la bonne boucle pour le jeu de devinettes ?
A post-condition loop always runs its body once before testing, which matches a game that needs at least one guess. A WHILE loop would need a guess before the loop just to have something to test. · Une boucle à post-condition exécute toujours son corps une fois avant de tester, ce qui correspond à un jeu nécessitant au moins une tentative. Une boucle WHILE aurait besoin d'une tentative avant la boucle juste pour avoir quelque chose à tester.
Stepwise refinement
- Stepwise refinement 逐步求精 means starting from an outline and expanding each step into more detailed steps, again and again, until every step can be written directly as pseudocode.
- "Process an order" → "get the items", "calculate the total", "take payment" → "calculate the total" becomes "for each item, add price × quantity; apply any discount".
- Each level is a refinement of the one above, and the finished levels together are the design. "Describe stepwise refinement" wants the outline, the expansion and the stopping rule.
Refine each step until it can be coded directly
Affinement progressif
- Affinement progressif 逐步求精 signifie commencer par un plan et développer chaque étape en étapes plus détaillées, encore et encore, jusqu'à ce que chaque étape puisse être écrite directement en pseudocode.
- "Traiter une commande" → "obtenir les articles", "calculer le total", "encaisser le paiement" → "calculer le total" devient "pour chaque article, ajouter prix × quantité ; appliquer une réduction éventuelle".
- Chaque niveau est un affinement du niveau supérieur, et l'ensemble des niveaux finaux constitue la conception. "Décrire l'affinement progressif" demande le plan, le développement et la règle d'arrêt.
Affinez chaque étape jusqu'à ce qu'elle puisse être codée directement
Put the stages of stepwise refinement in order. · Mettez les étapes de la raffinement progressif dans l'ordre.
Outline first, then refine level by level; you stop when a step is one line of pseudocode. · Esquissez d'abord, puis raffinez niveau par niveau ; vous arrêtez lorsqu'une étape tient en une ligne de pseudocode.
Logic statements
- Parts of a solution are defined by logic statements: conditions built from comparisons (
=,<>,<,>,<=,>=) joined byAND,ORandNOT. - A valid mark:
Mark >= 0 AND Mark <= 100. A discount applies if the customer is a member or spends over 50:IsMember OR Total > 50. NOT (Mark < 40)says the same thing asMark >= 40. Write the statement, then test it with a value on each side of the boundary.
Comparisons joined by AND, OR and NOT build the conditions an algorithm needs
Déclarations logiques
- Des parties de la solution sont définies par des déclarations logiques : des conditions construites à partir de comparaisons (
=,<>,<,>,<=,>=) jointes parAND,ORetNOT. - Une note valide :
Mark >= 0 AND Mark <= 100. Une réduction s'applique si le client est membre ou dépense plus de 50 :IsMember OR Total > 50. NOT (Mark < 40)dit la même chose queMark >= 40. Écrivez la déclaration, puis testez-la avec une valeur de chaque côté de la limite.
Les comparaisons jointes par AND, OR et NOT construisent les conditions dont un algorithme a besoin
NOT (Mark < 40) is true for exactly the same values of Mark as Mark >= 40. · NOT (Mark < 40) est vrai pour exactement les mêmes valeurs de Mark que Mark >= 40.
Negating "less than 40" gives "40 or more". Test the boundary: Mark = 40 makes Mark < 40 false, so NOT of it is true, and 40 >= 40 is also true. · Négater « inférieur à 40 » donne « 40 ou plus ». Testez la limite : Mark = 40 rend Mark < 40 faux, donc sa négation est vraie, et 40 >= 40 est également vraie.
Marks that slip away
←assigns and=compares.IF Total = 0is a test;Total = 0on its own line earns nothing.- Every construct closes:
ENDIF,ENDWHILE,UNTIL,NEXT,ENDCASE. A missing closer breaks the structure mark. - Declare before you use, and initialise a running total to
0. WHILEmay never run,REPEATalways runs once. Choose the loop that matches the task, and say why if asked.
Pièges qui font perdre des points
←affecte et=compare.IF Total = 0est un test ;Total = 0sur sa propre ligne ne rapporte aucun point.- Chaque construction se ferme :
ENDIF,ENDWHILE,UNTIL,NEXT,ENDCASE. Un fermant manquant brise la structure marquée. - Déclarez avant d'utiliser, et initialisez un total cumulé à
0. WHILEpeut ne jamais s'exécuter,REPEATs'exécute toujours une fois. Choisissez la boucle qui correspond à la tâche, et expliquez pourquoi si on vous le demande.
You've got it
- an algorithm's steps are unambiguous, deterministic, finite, effective; plan the data in an identifier table
- three constructs: sequence, selection (
IF/CASE), iteration (FOR/WHILE/REPEAT);WHILEtests before,REPEATafter - a flowchart and pseudocode describe the same algorithm; stepwise refinement expands an outline until it can be coded
- conditions are logic statements: comparisons joined with
AND,OR,NOT
Vous avez compris
- Les étapes d'un algorithme sont non ambiguës, déterministes, finies, effectives ; planifiez les données dans un tableau des identifiants
- trois constructions : séquence, sélection (
IF/CASE), itération (FOR/WHILE/REPEAT) ;WHILEteste avant,REPEATaprès - un diagramme de flux et un pseudocode décrivent le même algorithme ; l'affinement progressif développe un plan jusqu'à ce qu'il puisse être codé
- les conditions sont des déclarations logiques : des comparaisons jointes par
AND,OR,NOT