Selection and iteration · Sélection et itération
| English | Français |
|---|---|
| selection/sɪˈlekʃn/ | naturelle |
| iteration/ˌɪtəˈreɪʃn/ | itération |
| trace table/treɪs ˈteɪbl/ | tableau de traçage |
| nested/ˈnestɪd/ | imbriqué |
| logic error/ˈlɒdʒɪk ˈerə/ | erreur logique |
| count-controlled loop/kaʊnt kənˈtrəʊld luːp/ | boucle comptée |
| array/əˈreɪ/ | tableau |
| 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 |
| dry run/draɪ rʌn/ | exécution manuelle |
One line too many
- In 2014 Apple shipped a security update because of a single repeated line. Deep inside the code that checked a website's certificate,
goto fail;appeared twice in a row. - The second copy sat outside its
IF, so it ran every time, and the check below it never did. For months, any attacker could pretend to be any website. - Selection and iteration are the constructs that decide what runs and how often. Get one line of them wrong and the program still runs, just wrongly.
- This lesson is IF, CASE and the three loops, and the trace table that catches the mistake before the exam does.
Une ligne trop longue
- En 2014, Apple a expédié une mise à jour de sécurité en raison d'une ligne répétée unique. Profondément dans le code vérifiant le certificat d'un site web,
goto fail;apparaissait deux fois de suite. - La deuxième copie se trouvait hors de son
IF, donc elle s'exécutait à chaque fois, et la vérification en dessous ne le faisait jamais. Pendant des mois, tout attaquant pouvait se faire passer pour n'importe quel site web. - La sélection et l'itération sont les structures qui décident ce qui s'exécute et combien de fois. Faussez une seule ligne et le programme s'exécute toujours, juste mal.
- Cette leçon porte sur IF, CASE et les trois boucles, ainsi que sur la table de traçage qui repère l'erreur avant l'examen.
Selection
IF age >= 18 THEN … ELSE … ENDIF
- The
ELSEis optional, theENDIFis not. EveryIFmust be closed. - A condition is any Boolean expression: a comparison, or comparisons joined by
AND,ORandNOT.
An IF … ELSE tests once, then runs exactly one branch
Sélection
IF age >= 18 THEN … SINON … FIN SI
- Le
ELSEest optionnel, leENDIFne l'est pas. ToutIFdoit être fermé. - Une condition est n'importe quelle expression booléenne : une comparaison, ou des comparaisons jointes par
AND,ORetNOT.
Un IF … ELSE teste une seule fois, puis exécute exactement une branche
Nested IFs and boundaries
- A nested 嵌套 IF is an IF inside a branch of another IF, and each one needs its own
ENDIF. - Boundaries are where marks are lost. "A mark of 50 or more passes" is
Mark >= 50, notMark > 50. - A wrong comparison is a logic error 逻辑错误: the program runs and gives the wrong answer for some inputs. A trace with the boundary value, 50 itself, is how you find it.
IF imbriqués et limites
- Un nested 嵌套 (imbriqué) IF est un IF dans une branche d'un autre IF, et chacun nécessite son propre
ENDIF. - Les limites sont où les marques sont perdues. "Une note de 50 ou plus réussit" est
Mark >= 50, pasMark > 50. - Une mauvaise comparaison est une logic error 逻辑错误 (erreur logique) : le programme s'exécute et donne la mauvaise réponse pour certaines entrées. Un traçage avec la valeur limite, 50 lui-même, permet de la trouver.
"A mark of 50 or more passes" is written as IF Mark ____ 50 THEN. · "Une note de 50 ou plus réussit" s'écrit IF Mark ____ 50 THEN.
"Or more" includes 50 itself, so the comparison is greater than or equal. > would fail a student on exactly 50. · "ou plus" inclut 50 lui-même, donc la comparaison est supérieur ou égal. > ferait échouer un élève ayant exactement 50.
CASE
CASE OF Grade … ENDCASEtests one value against several options and is cleaner than a chain of nested IFs.- A guard can be a single value
"A":, a list1, 2, 3:, or a range1 TO 5:. The last branch for "anything else" isOTHERWISE, never a condition such as> 200. - Guards are tested in order. With
1 TO 50:followed by40 TO 60:, a value of 45 takes the first branch, so an assignment in the second may never run. If the earlier branches cover every possible value,OTHERWISEis never performed either.
A CASE runs the first branch whose guard matches the value
CASE
CASE OF Grade … ENDCASEteste une valeur contre plusieurs options et est plus propre qu'une chaîne de IF imbriqués.- Un garde peut être une valeur unique
"A":, une liste1, 2, 3:, ou une plage1 TO 5:. La dernière branche pour "tout le reste" estOTHERWISE, jamais une condition telle que> 200. - Les gardes sont testés dans l'ordre. Avec
1 TO 50:suivi de40 TO 60:, une valeur de 45 suit la première branche, donc une affectation dans la seconde peut ne jamais s'exécuter. Si les branches précédentes couvrent toutes les valeurs possibles,OTHERWISEne s'exécute jamais non plus.
Un CASE exécute la première branche dont le garde correspond à la valeur
A CASE statement is cleaner than nested IFs when you are: · Une instruction CASE est plus propre que des IF imbriqués lorsque vous êtes :
CASE matches one value against many possibilities; deep nested IFs become hard to read. · CASE correspond une valeur à de nombreuses possibilités ; les IF profonds imbriqués deviennent difficiles à lire.
Which of these are valid guards in a Cambridge CASE statement? Select all · tout that apply. · Lesquels de ces éléments sont des garde valides dans une instruction CASE de Cambridge ? Sélectionnez tous ceux qui s'appliquent.
A single value, a value list, a range and OTHERWISE. A comparison such as > 200 is not a guard; anything not covered goes to OTHERWISE. · Une valeur unique, une liste de valeurs, une plage et OTHERWISE. Une comparaison telle que > 200 n'est pas une garde ; tout ce qui n'est pas couvert va à OTHERWISE.
Worked example: rewrite a CASE without a CASE
CASE OF MySwitchwith1: ThisChar ← 'a',2: ThisChar ← 'y',3: ThisChar ← '7',OTHERWISE: ThisChar ← '*'.- Each value becomes one branch of a chain of IFs, and
OTHERWISEbecomes the finalELSE.
- Three IFs, three ENDIFs. Going the other way, two CASE clauses that assign the same value merge into one guard with a value list,
1, 2:.
Exemple résolu : réécrire un CASE sans un CASE
CASE OF MySwitchavec1: ThisChar ← 'a',2: ThisChar ← 'y',3: ThisChar ← '7',OTHERWISE: ThisChar ← '*'.- Chaque valeur devient une branche d'une chaîne de IF, et
OTHERWISEdevient le finalELSE.
IF MySwitch = 1 THEN
ThisChar <- 'a'
ELSE
IF MySwitch = 2 THEN
ThisChar <- 'y'
ELSE
IF MySwitch = 3 THEN
ThisChar <- '7'
ELSE
ThisChar <- '*'
ENDIF
ENDIF
ENDIF
- Trois IF, trois ENDIF. Dans l'autre sens, deux clauses CASE qui attribuent la même valeur fusionnent en un seul garde avec une liste de valeurs,
1, 2:.
The three loops
- Iteration 迭代 repeats a block, and the three loops differ in where the condition is tested.
- A count-controlled loop 计数循环,
FOR i ← 1 TO 10 … NEXT i, runs a known number of times;STEP -1counts down. Use it for a fixed count or every element of an array 数组. - A pre-condition loop 前测循环,
WHILE … DO … ENDWHILE, tests before each pass, so it may run zero times. A post-condition loop 后测循环,REPEAT … UNTIL, tests after each pass, so it always runs at least once.
Where the condition sits decides how many times the body can run
Les trois boucles
- Iteration 迭代 (itération) répète un bloc, et les trois boucles diffèrent par l'emplacement où la condition est testée.
- Une count-controlled loop 计数循环 (boucle contrôlée par compteur),
FOR i ← 1 TO 10 … NEXT i, s'exécute un nombre connu de fois ;STEP -1compte à rebours. Utilisez-la pour un décompte fixe ou pour chaque élément d'un array 数组 (tableau). - Une pre-condition loop 前测循环 (boucle à précondition),
WHILE … DO … ENDWHILE, teste avant chaque passage, donc elle peut ne s'exécuter zéro fois. Une post-condition loop 后测循环 (boucle à postcondition),REPEAT … UNTIL, teste après chaque passage, donc elle s'exécute toujours au moins une fois.
L'emplacement de la condition décide combien de fois le corps peut s'exécuter
Match each loop to when you'd use it. · Associez chaque boucle au moment où vous l'utiliserez.
FOR = count-controlled; WHILE = condition tested before (0+ passes); REPEAT = condition tested after (1+ passes). · POUR = contrôlé par compteur ; TANT QUE = condition testée avant (0+ passages) ; RÉPÉTER = condition testée après (1+ passages).
REPEAT...UNTIL tests its condition AFTER the body, so the body always runs at least once. · RÉPÉTER...JUSQU'À CE QUE teste sa condition APRÈS le corps, donc le corps s'exécute toujours au moins une fois.
That post-condition test is the difference from WHILE, which can run zero times. · Ce test post-condition est la différence avec TANT QUE, qui peut s'exécuter zéro fois.
Choosing the loop: the two-mark answer
- One mark for the name, one for the reason, in the scheme's words.
- Count-controlled, because the number of iterations is known before the loop starts. Post-condition, because the loop body must be executed at least once. Pre-condition, because the loop may not need to execute at all.
- A loop over the four elements of an array written as a
WHILEwith a counter is "not the most appropriate"; the FOR loop is, because the count is known.
Choisir la boucle : la réponse à deux marques
- Une marque pour le nom, une pour la raison, dans les termes de la grille.
- Contrôlé par un compteur, car le nombre d'itérations est connu avant le début de la boucle. Post-condition, car le corps de la boucle doit être exécuté au moins une fois. Pré-condition, car la boucle peut ne pas avoir besoin de s'exécuter du tout.
- Une boucle sur les quatre éléments d'un tableau écrit comme un
WHILEavec un compteur est "pas le plus approprié" ; la boucle FOR l'est, car le décompte est connu.
A question asks you to "identify a more appropriate loop and justify your choice" for 2 marks. What earns the two marks? · Une question demande d'« identifier une boucle plus appropriée et justifier votre choix » pour 2 points. Que rapporte les deux points ?
One mark for the loop, one for the reason: the count is known, the body must run once, or the loop may not run at all. · Un point pour la boucle, un pour la raison : le compteur est connu, le corps doit s'exécuter une fois, ou la boucle peut ne pas s'exécuter du tout.
Worked example: which loop fits each task?
- Print the 12 times table: the count is known in advance, so a FOR loop.
- Keep reading numbers until the user enters 0: the count is unknown and the very first input might already be 0, so the test must come before the body: a WHILE loop.
- Ask for a password until it is correct: the user must be asked at least once, so a REPEAT … UNTIL loop.
- Ask two questions: how many times, and must the body run before the first test?
Exemple résolu : quelle boucle convient à chaque tâche ?
- Imprimer la table de multiplication de 12 : le compteur est connu à l'avance, donc une boucle FOR.
- Continuer à lire des nombres jusqu'à ce que l'utilisateur saisisse 0 : le compteur est inconnu et la toute première entrée pourrait déjà être 0, donc le test doit venir avant le corps : une boucle WHILE.
- Demander un mot de passe jusqu'à ce qu'il soit correct : l'utilisateur doit être interrogé au moins une fois, donc une boucle REPEAT … UNTIL.
- Poser deux questions : combien de fois, et le corps doit-il s'exécuter avant le premier test ?
"Keep asking for a password until it is correct, but always ask at least once." Which loop fits? · « Demander un mot de passe tant qu'il est incorrect, mais toujours demander au moins une fois. » Quelle boucle convient ?
You must ask at least once, so the post-condition REPEAT...UNTIL is the natural choice. · Vous devez demander au moins une fois, donc RÉPÉTER...JUSQU'À CE QUE (post-condition) est le choix naturel.
Trace tables
- A trace table 跟踪表 records every variable's value as you dry run 手工跟踪 the algorithm by hand. It is how a loop is tested on paper and a six-mark question on most Paper 2s.
- One column per variable, plus a column for any output. Write a new row only when a value changes, and evaluate the loop condition at the moment the loop reaches it.
- Keep going until the condition ends the loop, then record the final output.
Tables de traçage
- Une table de traçage 跟踪表 enregistre la valeur de chaque variable alors que vous faites un dry run 手工跟踪 de l'algorithme à la main. C'est ainsi qu'une boucle est testée sur papier et c'est une question de six points sur la plupart des Paper 2s.
- Une colonne par variable, plus une colonne pour toute sortie. Écrivez une nouvelle ligne uniquement lorsqu'une valeur change, et évaluez la condition de boucle au moment où la boucle y accède.
- Continuez jusqu'à ce que la condition arrête la boucle, puis enregistrez la sortie finale.
Trace a loop, pass by pass · Suivez une boucle, passage par passage
A trace table records each variable after every pass of the loop. Watch the counter i climb while the running total builds up — exactly what an exam trace question asks you to fill in. · Un tableau de traçage enregistre chaque variable après chaque passage de la boucle. Observez le compteur i grimper pendant que le total cumulatif se construit — exactement ce qu'une question de traçage d'examen vous demande de remplir.
After total = 0; FOR i = 1 TO 5: total = total + i, what is the value of total? · Après total = 0; FOR i = 1 TO 5: total = total + i, quelle est la valeur de total ?
Adding 1+2+3+4+5 = 15 — exactly what the trace table builds up pass by pass. · Ajouter 1+2+3+4+5 = 15 — exactement ce que la table de traçage accumule passage par passage.
Worked example: a trace table filled
- Rows of (Count, Total): (1, 0) → (2, 1) → (3, 3) → (4, 6) → (5, 10).
- At Total = 10 the condition
Total < 10is false, the loop ends, and the output is 5. - The last row is the one most often wrong: check the condition one more time before writing the output.
Exemple résolu : une table de traçage remplie
Count <- 1
Total <- 0
WHILE Total < 10 DO
Total <- Total + Count
Count <- Count + 1
ENDWHILE
OUTPUT Count
- Lignes de (Count, Total) : (1, 0) → (2, 1) → (3, 3) → (4, 6) → (5, 10).
- À Total = 10, la condition
Total < 10est fausse, la boucle se termine, et la sortie est 5. - La dernière ligne est celle qui fait le plus souvent erreur : vérifiez la condition une fois de plus avant d'écrire la sortie.
In the worked trace, the loop ends with Total = 10 and Count = 5, so the output is 5. · Dans le traçage illustré, la boucle se termine avec Total = 10 et Count = 5, donc la sortie est 5.
After the fourth pass Total reaches 10, the condition Total < 10 becomes false, and Count has been incremented to 5. · Après le quatrième passage, Total atteint 10, la condition Total < 10 devient fausse, et Count a été incrémenté à 5.
Marks that slip away
>=and>are different answers. Test the boundary value in your head before you write the comparison.OTHERWISEis a keyword, not a condition. And everyIF,CASE,WHILEandFORcloses withENDIF,ENDCASE,ENDWHILEorNEXT.- A
WHILEcan run zero times; aREPEATcannot. Choose by whether the body must run once before the first test. - In a trace table, a value that does not change is not rewritten, and the output is written only when the
OUTPUTline runs.
Pièges qui font perdre des points
>=et>sont des réponses différentes. Testez la valeur limite mentalement avant d'écrire la comparaison.OTHERWISEest un mot-clé, pas une condition. Et chaqueIF,CASE,WHILEetFORse termine parENDIF,ENDCASE,ENDWHILEouNEXT.- Un
WHILEpeut s'exécuter zéro fois ; unREPEATne peut pas. Choisissez selon si le corps doit s'exécuter une fois avant le premier test. - Dans une table de traçage, une valeur qui ne change pas n'est pas réécrite, et la sortie n'est écrite que lorsque la ligne
OUTPUTs'exécute.
You've got it
- IF … ELSE … ENDIF for a choice; nested IFs each closed; CASE for one value against many guards, tested in order,
OTHERWISElast - FOR count known · WHILE tests before, may run zero times · REPEAT … UNTIL tests after, runs at least once
- justify a loop with its name and reason: known count, may not run, must run once
- a trace table dry-runs the algorithm one row per change; check the condition once more before the final output
Vous avez compris
- IF … ELSE … ENDIF pour un choix ; IF imbriqués chacun fermé ; CASE pour une valeur contre plusieurs garde-fous, testés dans l'ordre,
OTHERWISEen dernier - FOR compteur connu · WHILE teste avant, peut s'exécuter zéro fois · REPEAT … UNTIL teste après, s'exécute au moins une fois
- Justifier une boucle avec son nom et raison : compteur connu, peut ne pas s'exécuter, doit s'exécuter une fois
- une table de traçage fait un dry-run de l'algorithme une ligne par changement ; vérifiez la condition une fois de plus avant la sortie finale