Selection and iteration · 选择与迭代
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| selection/sɪˈlekʃn/ | 选择 | xuǎn zé |
| iteration/ˌɪtəˈreɪʃn/ | 迭代 | dié dài |
| trace table/treɪs ˈteɪbl/ | 跟踪表 | gēn zōng biǎo |
| nested/ˈnestɪd/ | 嵌套 | qiàn tào |
| logic error/ˈlɒdʒɪk ˈerə/ | 逻辑错误 | luó jí cuò wù |
| count-controlled loop/kaʊnt kənˈtrəʊld luːp/ | 计数循环 | jì shù xún huán |
| array/əˈreɪ/ | 数组 | shù zǔ |
| pre-condition loop/priː kənˈdɪʃn luːp/ | 前测循环 | qián cè xún huán |
| post-condition loop/pəʊst kənˈdɪʃn luːp/ | 后测循环 | hòu cè xún huán |
| dry run/draɪ rʌn/ | 手工跟踪 | shǒu gōng gēn zōng |
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.
多出来的一行
- 2014 年,苹果因为一行重复的代码发布了安全更新。在检查网站证书的代码深处,
goto fail;连续出现了两次。 - 第二份副本落在了它的
IF之外,所以每次都执行,而它下面的检查再也没有运行过。几个月里,任何攻击者都可以假装成任何网站。 - 选择和迭代是决定什么运行、运行多少次的构造。把它们的一行写错,程序照样运行,只是运行得不对。
- 这一课讲 IF、CASE 和三种循环,以及能在考试之前抓住错误的跟踪表。
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
选择
IF age >= 18 THEN … ELSE … ENDIF
ELSE是可选的,ENDIF不是。每个IF都必须关闭。- 条件是任何布尔表达式:一个比较,或用
AND、OR和NOT连接的多个比较。
IF … ELSE 测试一次,然后恰好运行一个分支
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 和边界
- 嵌套(nested)IF 是一个 IF 在另一个 IF 的分支里面,每一个都需要自己的
ENDIF。 - 边界是丢分的地方。"50 分或以上通过"是
Mark >= 50,不是Mark > 50。 - 错误的比较是逻辑错误(logic error):程序运行,但对某些输入给出错误答案。用边界值——50 本身——跟踪一遍,就是找到它的方法。
"A mark of 50 or more passes" is written as IF Mark ____ 50 THEN. · "50 分或以上通过"写成 IF Mark ____ 50 THEN。
"Or more" includes 50 itself, so the comparison is greater than or equal. > would fail a student on exactly 50. · "或以上"包括 50 本身,所以比较是大于或等于。> 会让正好 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 … ENDCASE把一个值与多个选项比对,比一串嵌套 IF 更清晰。- 守卫可以是单个值
"A":、一个列表1, 2, 3:,或一个范围1 TO 5:。表示"其他任何情况"的最后一个分支是OTHERWISE,绝不是> 200这样的条件。 - 守卫按顺序测试。
1 TO 50:后面跟着40 TO 60:时,值 45 走第一个分支,所以第二个分支里的赋值可能永远不运行。如果前面的分支已经覆盖了所有可能的值,OTHERWISE也永远不会执行。
CASE 运行第一个守卫与值匹配的分支
A CASE statement is cleaner than nested IFs when you are: · 当你在以下情况时,一个 CASE 语句比嵌套的 IF 更清晰:
CASE matches one value against many possibilities; deep nested IFs become hard to read. · CASE 把一个值匹配许多可能性;深层嵌套的 IF 变得难以阅读。
Which of these are valid guards in a Cambridge CASE statement? Select all · 所有 that apply. · 以下哪些是剑桥 CASE 语句中合法的守卫?选出所有适用的。
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. · 单个值、值列表、范围和 OTHERWISE。> 200 这样的比较不是守卫;没有覆盖的情况都归 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:.
例题:不用 CASE 重写一个 CASE
CASE OF MySwitch,其中1: ThisChar ← 'a'、2: ThisChar ← 'y'、3: ThisChar ← '7'、OTHERWISE: ThisChar ← '*'。- 每个值变成一串 IF 中的一个分支,
OTHERWISE变成最后的ELSE。
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
- 三个 IF,三个 ENDIF。反过来,两个赋同一个值的 CASE 分句合并成一个带值列表的守卫,
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
三种循环
- 迭代(iteration)重复一块代码,三种循环的区别在于条件在哪里测试。
- 计数循环(count-controlled loop),
FOR i ← 1 TO 10 … NEXT i,运行已知的次数;STEP -1倒数。用于固定次数或数组(array)的每个元素。 - 前测循环(pre-condition loop),
WHILE … DO … ENDWHILE,在每一轮之前测试,所以可能运行零次。后测循环(post-condition loop),REPEAT … UNTIL,在每一轮之后测试,所以总是至少运行一次。
条件所在的位置决定循环体能运行多少次
Match each loop to when you'd use it. · 把每个循环与你会用它的时机配对。
FOR = count-controlled; WHILE = condition tested before (0+ passes); REPEAT = condition tested after (1+ passes). · FOR = 计数控制;WHILE = 之前测试条件(0+ 遍);REPEAT = 之后测试条件(1+ 遍)。
REPEAT...UNTIL tests its condition AFTER the body, so the body always runs at least once. · REPEAT...UNTIL 在主体之后测试它的条件,所以主体总是至少运行一次。
That post-condition test is the difference from WHILE, which can run zero times. · 那个后置条件测试是与 WHILE 的区别,WHILE 能运行零次。
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.
选择循环:两分的答案
- 一分给名字,一分给理由,用评分标准的话。
- 计数循环,因为迭代次数在循环开始前已知。 后测循环,因为循环体必须至少执行一次。 前测循环,因为循环可能根本不需要执行。
- 对数组的四个元素用带计数器的
WHILE写的循环"不是最合适的";FOR 循环才是,因为次数已知。
A question asks you to "identify a more appropriate loop and justify your choice" for 2 marks. What earns the two marks? · 一道题要你"指出一种更合适的循环并说明理由",共 2 分。什么能拿到这两分?
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?
例题:每个任务用哪种循环?
- 打印 12 的乘法表:次数事先已知,所以用 FOR 循环。
- 持续读入数字直到用户输入 0:次数未知,而且第一个输入就可能已经是 0,所以测试必须在循环体之前:WHILE 循环。
- 要求输入密码直到正确:用户必须至少被问一次,所以用 REPEAT … UNTIL 循环。
- 问两个问题:运行多少次,以及循环体是否必须在第一次测试之前运行?
"Keep asking for a password until it is correct, but always ask at least once." Which loop fits? · “不断要一个密码直到它正确,但总是至少要一次。”哪个循环合适?
You must ask at least once, so the post-condition REPEAT...UNTIL is the natural choice. · 你必须至少要一次,所以后置条件的 REPEAT...UNTIL 是自然的选择。
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 table)记录你手工跟踪(dry run)算法时每个变量的值。它是在纸上测试循环的方法,也是多数 Paper 2 上的一道六分题。
- 每个变量一列,再加一列输出。只在值改变时写新的一行,并在循环到达条件的那一刻求条件的值。
- 一直进行到条件结束循环,然后记录最终输出。
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. · 一个追踪表在循环的每一遍之后记录每个变量。看计数器 i 爬升,同时运行总和累积起来——正是一个考试追踪题要你填写的。
After total = 0; FOR i = 1 TO 5: total = total + i, what is the value of total? · 在 total = 0; FOR i = 1 TO 5: total = total + i 之后,total 的值是多少?
Adding 1+2+3+4+5 = 15 — exactly what the trace table builds up pass by pass. · 把 1+2+3+4+5 = 15 加起来——正是追踪表一遍一遍累积起来的。
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.
例题:填好的跟踪表
Count <- 1
Total <- 0
WHILE Total < 10 DO
Total <- Total + Count
Count <- Count + 1
ENDWHILE
OUTPUT Count
- (Count, Total) 的各行:(1, 0) → (2, 1) → (3, 3) → (4, 6) → (5, 10)。
- Total = 10 时条件
Total < 10为假,循环结束,输出是 5。 - 最后一行最常出错:写输出之前再检查一次条件。
In the worked trace, the loop ends with Total = 10 and Count = 5, so the output is 5. · 在例题的跟踪中,循环结束时 Total = 10、Count = 5,所以输出是 5。
After the fourth pass Total reaches 10, the condition Total < 10 becomes false, and Count has been incremented to 5. · 第四轮后 Total 达到 10,条件 Total < 10 变为假,而 Count 已经加到 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.
容易丢掉的分
>=和>是不同的答案。写比较之前先在脑子里测试边界值。OTHERWISE是关键字,不是条件。每个IF、CASE、WHILE和FOR都用ENDIF、ENDCASE、ENDWHILE或NEXT关闭。WHILE可以运行零次;REPEAT不能。按循环体是否必须在第一次测试前运行一次来选。- 跟踪表里,没有改变的值不重写,输出只在
OUTPUT行运行时才写。
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
你掌握了
- IF … ELSE … ENDIF 做选择;嵌套 IF 各自关闭;CASE 把一个值与多个守卫比对,按顺序测试,
OTHERWISE放最后 - FOR 次数已知 · WHILE 先测,可能零次 · REPEAT … UNTIL 后测,至少一次
- 用名字和理由论证循环:次数已知、可能不运行、必须运行一次
- 跟踪表逐行手工跟踪算法,每次改变一行;写最终输出前再检查一次条件