Notations, stepwise refinement and logic · 记法、逐步求精与逻辑
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| notation/nəʊˈteɪʃn/ | 记法 | jì fǎ |
| structured English/ˈstrʌktʃəd ˈɪŋɡlɪʃ/ | 结构化英语 | jié gòu huà yīng yǔ |
| pseudocode/ˈsuːdəʊkəʊd/ | 伪代码 | wěi dài mǎ |
| flowchart/ˈfləʊtʃɑːt/ | 流程图 | liú chéng tú |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | 逐步求精 | zhú bù qiú jīng |
| logic statement/ˈlɒdʒɪk ˈsteɪtmənt/ | 逻辑语句 | luó jí yǔ jù |
| Boolean/ˈbuːlɪən/ | 布尔 | bù ěr |
| precedence/ˈpresɪdəns/ | 优先级 | yōu xiān jí |
| De Morgan's law/də ˈmɔːɡənz lɔː/ | 德摩根定律 | dé mó gēn dìng lǜ |
The first algorithm had no language to be written in
- In 1843 Ada Lovelace published the steps for computing Bernoulli numbers on Babbage's Analytical Engine, a machine that was never built.
- There was no programming language, so she wrote the algorithm as a numbered table of operations: a notation 记法 of her own.
- Every algorithm still starts that way. You write it down in some notation, check it, and only then turn it into code.
- This lesson is about the three notations the exam uses, how to move between them, and how to write the conditions inside them.
第一个算法没有可以书写它的语言
- 1843 年,Ada Lovelace 发表了在 Babbage 的分析机上计算伯努利数的步骤——那台机器从未被造出来。
- 当时没有编程语言,所以她把算法写成一张带编号的操作表:一种她自己的记法(notation)。
- 每个算法至今仍然这样开始。你先用某种记法把它写下来,检查它,然后才把它变成代码。
- 这一课讲考试用的三种记法、如何在它们之间转换,以及如何写它们里面的条件。
Three notations
- Structured English 结构化英语: ordinary sentences, indented, with a few fixed words such as
IF,FOR EACH,REPEAT. Good for a first outline. - Pseudocode 伪代码: the keyword notation (
IF … ENDIF,WHILE … ENDWHILE,FOR … NEXT), closest to real code and marked against Cambridge's guide. - Flowchart 流程图: a diagram of standard shapes. Rounded rectangle for
START/STOP, parallelogram for input and output, rectangle for a process, diamond for a decision, arrows for the flow.
A flowchart for averaging a list of numbers, drawn with the standard shapes
三种记法
- 结构化英语(structured English):普通的句子,带缩进,加上少量固定词,比如
IF、FOR EACH、REPEAT。适合写第一版大纲。 - 伪代码(pseudocode):关键字记法(
IF … ENDIF、WHILE … ENDWHILE、FOR … NEXT),最接近真正的代码,并按剑桥的指南评分。 - 流程图(flowchart):用标准形状画的图。圆角矩形是
START/STOP,平行四边形是输入和输出,矩形是处理,菱形是判断,箭头是流程。
用标准形状画的对一列数求平均的流程图
In a flowchart, which shape represents a decision? · 在一个流程图中,哪个形状表示一个判断?
A diamond is a decision; rounded rectangle = start/stop, parallelogram = input/output, rectangle = process. · 一个菱形是一个判断;圆角矩形 = 开始/停止,平行四边形 = 输入/输出,矩形 = 处理。
Match each flowchart shape to its meaning. · 把每个流程图形状与它的含义配对。
Parallelogram = I/O, rectangle = process, rounded rectangle = start/stop, diamond = decision. · 平行四边形 = 输入/输出,矩形 = 处理,圆角矩形 = 开始/停止,菱形 = 判断。
Match each notation to its description. · 把每种记法与它的描述配对。
All three describe the same algorithm at different distances from the code. · 三者描述的是同一个算法,只是离代码的距离不同。
Worked example: structured English to pseudocode
- Structured English: Set the total to zero. For each of the N numbers, add it to the total. Divide the total by N and output the result.
- Each sentence becomes one construct: an assignment, a
FORloop with an assignment inside it, then an assignment and an output.
- The order of the sentences is the order of the statements. Nothing is added and nothing is left out.
例题:从结构化英语到伪代码
- 结构化英语:把总和设为零。对 N 个数中的每一个,把它加到总和上。用总和除以 N 并输出结果。
- 每个句子变成一个构造:一个赋值,一个内部带赋值的
FOR循环,然后一个赋值和一个输出。
Total <- 0
FOR Index <- 1 TO N
Total <- Total + Number[Index]
NEXT Index
Average <- Total / N
OUTPUT Average
- 句子的顺序就是语句的顺序。什么也没加,什么也没漏。
In the averaging algorithm, the FOR loop that adds each number to the total is an example of the ____ construct. · 在求平均的算法中,把每个数加到总和上的 FOR 循环是 ____ 构造的一个例子。
Repeating a block for each number is iteration. The assignment inside it stores the running total. · 对每个数重复一块代码就是迭代。它里面的赋值存储累加的总和。
Worked example: pseudocode to flowchart
- Take the same algorithm.
STARTgoes in a rounded rectangle,Total ← 0andIndex ← 1in rectangles. - The
FORloop becomes a diamond askingIndex <= N?. The Yes exit leads to the rectangleTotal ← Total + Number[Index], thenIndex ← Index + 1, and an arrow back up to the diamond. - The No exit continues to
Average ← Total / N, an output parallelogram, andSTOP. - Label both exits of every diamond. A diamond with one unlabelled exit is not a decision.
例题:从伪代码到流程图
- 用同一个算法。
START放在圆角矩形里,Total ← 0和Index ← 1放在矩形里。 FOR循环变成一个问Index <= N?的菱形。Yes 出口通向矩形Total ← Total + Number[Index],然后是Index ← Index + 1,再用一条箭头向上折回菱形。- No 出口继续到
Average ← Total / N、一个输出平行四边形,以及STOP。 - 给每个菱形的两个出口都标上标签。只有一个无标签出口的菱形不是判断。
Stepwise refinement
- Stepwise refinement 逐步求精 means writing an algorithm as a short outline, then expanding each step into more detailed sub-steps, and repeating until every step can be coded directly.
- Each level keeps the structure of the level above and adds detail. The outline is not thrown away: it becomes the structure of the program.
- The design stops when a step is one line of pseudocode or one module you already have.
Stepwise refinement expands each step until it can be coded
逐步求精
- 逐步求精(stepwise refinement)意味着把算法写成一个简短大纲,然后把每一步展开成更详细的子步骤,重复,直到每一步都能直接编码。
- 每一层都保留上一层的结构并增加细节。大纲不会被丢掉:它成为程序的结构。
- 当一步是一行伪代码,或是一个你已经有的模块时,设计就停止。
逐步求精把每一步展开,直到它可以编码
Stepwise refinement is the technique of: · 逐步求精是以下的技术:
You refine a high-level outline level by level, adding detail while keeping the structure. · 你逐层求精一个高层提纲,在保持结构的同时增加细节。
Worked example: three levels
- Level 1: Process the exam results.
- Level 2: Input each mark. Calculate the mean. Count how many passed. Output the report.
- Level 3, refining "count how many passed":
Passes ← 0, thenFOReach mark,IF Mark >= 40 THEN Passes ← Passes + 1. - Asked to "describe stepwise refinement", give the three ideas: start from an outline, expand each step into smaller steps, stop when each step can be programmed.
例题:三个层级
- 第 1 层:处理考试成绩。
- 第 2 层:输入每个分数。计算平均分。统计多少人通过。输出报告。
- 第 3 层,细化"统计多少人通过":
Passes ← 0,然后对每个分数FOR循环,IF Mark >= 40 THEN Passes ← Passes + 1。 - 被要求"描述逐步求精"时,给出三个要点:从大纲开始,把每一步展开成更小的步骤,当每一步都能编程时停止。
Stepwise refinement: outline to code · 逐步求精:从提纲到代码
Step down the levels. You start with the whole task in one line and keep expanding each step into smaller ones — until every step is simple enough to code directly. · 逐层下降。你从一行里的整个任务开始,不断把每个步骤扩展成更小的——直到每个步骤都简单到能直接编码。
In stepwise refinement, each new level replaces the level above it, so the original outline is thrown away. · 在逐步求精中,每个新层级都取代上一层,所以原来的大纲被丢掉了。
Each level keeps the structure of the one above and adds detail. The outline becomes the shape of the finished program. · 每一层都保留上一层的结构并增加细节。大纲成为最终程序的形状。
Logic statements
- A logic statement 逻辑语句 is a Boolean 布尔 condition: it is either
TRUEorFALSE, and it controls anIF, aWHILEor anUNTIL. - It is built from comparisons (
=,<>,<,>,<=,>=) joined byAND,ORandNOT. Mark >= 0 AND Mark <= 100is true only for marks in range.Age < 12 OR Age >= 65is true for children and pensioners.
Comparisons joined by AND, OR and NOT make one condition
逻辑语句
- 一个逻辑语句(logic statement)是一个布尔(Boolean)条件:它要么是
TRUE要么是FALSE,并控制一个IF、一个WHILE或一个UNTIL。 - 它由比较(
=、<>、<、>、<=、>=)组成,用AND、OR和NOT连接。 Mark >= 0 AND Mark <= 100只对范围内的分数为真。Age < 12 OR Age >= 65对儿童和老人为真。
用 AND、OR 和 NOT 连接的比较构成一个条件
Precedence and brackets
- Operators are applied in a fixed order of precedence 优先级:
NOTfirst, thenAND, thenOR. - So
A OR B AND CmeansA OR (B AND C), not(A OR B) AND C. WithA = TRUE,B = FALSE,C = FALSEthe first isTRUEand the second isFALSE. - Use brackets whenever a condition mixes
ANDandOR. They cost nothing and remove the ambiguity.
优先级和括号
- 运算符按固定的优先级(precedence)顺序应用:先
NOT,然后AND,然后OR。 - 所以
A OR B AND C的意思是A OR (B AND C),而不是(A OR B) AND C。当A = TRUE、B = FALSE、C = FALSE时,前者为TRUE,后者为FALSE。 - 只要一个条件同时含有
AND和OR,就用括号。括号不花任何代价,却消除了歧义。
Put the logic operators in order of precedence, highest (evaluated first) to lowest. · 把逻辑运算符按优先级顺序排列,最高(先求值)到最低。
NOT binds tightest, then AND, then OR — use brackets when in doubt. · NOT 结合最紧,然后 AND,然后 OR——不确定时用括号。
With no brackets, what does A OR B AND C mean? · 没有括号时,A OR B AND C 的意思是什么?
AND has higher precedence than OR, so it is evaluated first. Bracket the condition anyway, so nobody has to remember. · AND 的优先级高于 OR,所以先算 AND。无论如何都加上括号,这样没人需要去记。
De Morgan's laws
- De Morgan's law 德摩根定律:
NOT (A AND B)is the same as(NOT A) OR (NOT B), andNOT (A OR B)is the same as(NOT A) AND (NOT B). - In words: "not (registered and paid)" means "not registered, or not paid".
- Use it to simplify a condition, or to check one: pick values for
AandB, work out both sides, and they must agree in every case.
德摩根定律
- 德摩根定律(De Morgan's law):
NOT (A AND B)等同于(NOT A) OR (NOT B),NOT (A OR B)等同于(NOT A) AND (NOT B)。 - 用话说:"并非(已注册且已付款)"意味着"未注册,或未付款"。
- 用它来化简一个条件,或检查一个条件:给
A和B取值,算出两边,它们在每种情况下都必须一致。
By De Morgan's law, NOT (A AND B) is the same as (NOT A) OR (NOT B). · 由德摩根定律,NOT (A AND B) 和 (NOT A) OR (NOT B) 一样。
NOT distributes over the bracket and flips AND↔OR; likewise NOT (A OR B) = (NOT A) AND (NOT B). · NOT 分配到括号上并翻转 AND↔OR;同样 NOT (A OR B) = (NOT A) AND (NOT B)。
Worked example: a condition from words
- Rule: a student may sit the exam if they are registered and have either paid or hold a bursary, but not if they are suspended.
- Name the Boolean variables:
Registered,Paid,Bursary,Suspended. - Statement:
Registered AND (Paid OR Bursary) AND NOT Suspended. - The brackets around
Paid OR Bursaryare essential. Without them,ANDbinds first and a student with a bursary but no registration would get in.
例题:从文字写出条件
- 规则:学生已注册并且已付款或持有助学金时可以参加考试,但如果被停学则不可以。
- 命名布尔变量:
Registered、Paid、Bursary、Suspended。 - 语句:
Registered AND (Paid OR Bursary) AND NOT Suspended。 Paid OR Bursary外面的括号必不可少。没有它们,AND先结合,一个有助学金但没注册的学生也会被放进去。
Which conditions are equivalent to NOT (Registered AND Paid)? Select all · 所有 that apply. · 哪些条件等同于 NOT (Registered AND Paid)?选出所有适用的。
De Morgan turns NOT of an AND into an OR of the NOTs. The AND version is too strict: a student who is registered but has not paid should make the original condition TRUE, and it makes the AND version FALSE. · 德摩根把 AND 的 NOT 变成各个 NOT 的 OR。AND 那个版本太严格:一个已注册但未付款的学生应让原条件为 TRUE,却让 AND 版本为 FALSE。
Marks that slip away
a = 1 OR 2is not a condition. Writea = 1 OR a = 2: each side ofORmust be a complete comparison.NOTapplies only to what follows it.NOT A AND Bmeans(NOT A) AND B.- A diamond needs two labelled exits, and a loop needs an arrow that goes back up. A flowchart with no arrow returning is not a loop.
- Structured English is still precise. "Deal with the marks" is not a step; "add the mark to the total" is.
容易丢掉的分
a = 1 OR 2不是一个条件。要写a = 1 OR a = 2:OR的每一边都必须是完整的比较。NOT只作用于紧跟它的部分。NOT A AND B的意思是(NOT A) AND B。- 一个菱形需要两个带标签的出口,一个循环需要一条向上折回的箭头。没有折回箭头的流程图不是循环。
- 结构化英语仍然要精确。"处理分数"不是一步;"把分数加到总和上"才是。
To test whether a is 1 or 2, the correct condition is: · 要测试 a 是 1 还是 2,正确的条件是:
Each side of OR must be a full comparison: a = 1 OR a = 2. Writing a = 1 OR 2 is a common error. · OR 的每一边都必须是一个完整的比较:a = 1 OR a = 2。写 a = 1 OR 2 是一个常见的错误。
You've got it
- three notations for one algorithm: structured English, pseudocode, flowchart (diamond = decision, back-arrow = loop)
- stepwise refinement: outline → expand each step → stop when a step can be coded
- a logic statement is a Boolean condition; precedence NOT → AND → OR, so bracket anything that mixes them
- De Morgan:
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B
你掌握了
- 同一个算法的三种记法:结构化英语、伪代码、流程图(菱形 = 判断,折回箭头 = 循环)
- 逐步求精:大纲 → 展开每一步 → 当一步可以编码时停止
- 逻辑语句是一个布尔条件;优先级 NOT → AND → OR,所以混用时要加括号
- 德摩根:
NOT (A AND B)=NOT A OR NOT B;NOT (A OR B)=NOT A AND NOT B