Selection and iteration
Introduced| English | Meaning |
|---|---|
| selection/sɪˈlekʃn/ | Choosing which branch of instructions to execute according to a condition. |
| iteration/ˌɪtəˈreɪʃn/ | Repeating a sequence of instructions or calculations. |
| trace table/treɪs ˈteɪbl/ | A table recording variable values and outputs as an algorithm's steps are followed. |
| nested/ˈnestɪd/ | Contained within another structure of the same or a related kind, such as a loop inside a loop. |
| logic error/ˈlɒdʒɪk ˈerə/ | A mistake in an algorithm or program that produces an incorrect result despite valid syntax. |
| count-controlled loop/kaʊnt kənˈtrəʊld luːp/ | A loop that repeats according to a counter, usually for a specified number of iterations. |
| array/əˈreɪ/ | An indexed collection of elements arranged in one or more dimensions. |
| pre-condition loop/priː kənˈdɪʃn luːp/ | A loop that tests its continuation condition before executing its body, so the body may run zero times. |
| post-condition loop/pəʊst kənˈdɪʃn luːp/ | A loop that tests its continuation or termination condition after executing its body, so it runs at least once. |
| dry run/draɪ rʌn/ | Tracing an algorithm by hand using example inputs and recording changes in its values. |
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.
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
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.
"A mark of 50 or more passes" is written as IF Mark ____ 50 THEN.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
"Or more" includes 50 itself, so the comparison is greater than or equal. > would fail a student on exactly 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
A CASE statement is cleaner than nested IFs when you are:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
CASE matches one value against many possibilities; deep nested IFs become hard to read.
Which of these are valid guards in a Cambridge CASE statement? Select all that apply.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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.
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.
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
- 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:.
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
Match each loop to when you'd use it.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
FOR = count-controlled; WHILE = condition tested before (0+ passes); REPEAT = condition tested after (1+ passes).
REPEAT...UNTIL tests its condition AFTER the body, so the body always runs at least once.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
That post-condition test is the difference from WHILE, which can run zero times.
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.
A question asks you to "identify a more appropriate loop and justify your choice" for 2 marks. What earns the two marks?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
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?
"Keep asking for a password until it is correct, but always ask at least once." Which loop fits?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
You must ask at least once, so the post-condition REPEAT...UNTIL is the natural choice.
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.
Trace a loop, pass by pass
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.
After total = 0; FOR i = 1 TO 5: total = total + i, what is the value of total?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Adding 1+2+3+4+5 = 15 — exactly what the trace table builds up pass by pass.
Worked example: a trace table filled
Count <- 1
Total <- 0
WHILE Total < 10 DO
Total <- Total + Count
Count <- Count + 1
ENDWHILE
OUTPUT Count
- 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.
In the worked trace, the loop ends with Total = 10 and Count = 5, so the output is 5.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
After the fourth pass Total reaches 10, the condition Total < 10 becomes false, and Count has been incremented to 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.
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