Algorithms and pseudocode · 算法与伪代码
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| algorithm/ˈælɡərɪθəm/ | 算法 | suàn fǎ |
| sequence/ˈsiːkwəns/ | 顺序 | shùn xù |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | 确定性 | què dìng xìng |
| identifier table/aɪˈdentɪfaɪə ˈteɪbl/ | 标识符表 | biāo shí fú biǎo |
| variable/ˈveərɪəbl/ | 变量 | biàn liàng |
| data type/ˈdeɪtə taɪp/ | 数据类型 | shù jù lèi xíng |
| pseudocode/ˈsuːdəʊkəʊd/ | 伪代码 | wěi dài mǎ |
| assignment/əˈsaɪnmənt/ | 赋值 | fù zhí |
| loop/luːp/ | 循环 | xún huán |
| count-controlled loop/kaʊnt kənˈtrəʊld luːp/ | 计数循环 | jì shù xún huán |
| 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 |
| iteration/ˌɪtəˈreɪʃn/ | 迭代 | dié dài |
| selection/sɪˈlekʃn/ | 选择 | xuǎn zé |
| flowchart/ˈfləʊtʃɑːt/ | 流程图 | liú chéng tú |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | 逐步求精 | zhú bù qiú jīng |
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 算法.
史上最贵的一个连字符
- 1962 年 7 月 22 日,飞往金星的 Mariner 1 火箭在发射 293 秒后被引爆。
- 原因是制导方程里一个符号上少了一道横线。计算机完全按照写下的步骤执行,而写下的步骤是错的。
- 计算机从不替你补上"你想表达的意思"。你给它的每一步都必须只有一个含义。
- 所以这一课讲的是写出机器能遵循的步骤:算法(algorithm)。
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
什么是算法
- 一个算法是表达为一系列定义好的步骤的问题解决方案。
- 每一步都是无歧义的(只有一个意思)、确定的(deterministic,同样的输入 → 同样的输出)、有限的(步骤会结束)和有效的(每一步都真的能做到)。
- 它说的是做什么,与任何编程语言无关,而且每个算法都遵循输入 → 处理 → 输出。
每个算法都有同样的形状:输入、处理、输出
An algorithm is "deterministic". This means: · 一个算法是“确定的”。这意味着:
Deterministic = same input → same output every time. (Finite = the steps end; unambiguous = one meaning per step.) · 确定 = 同样的输入 → 每次同样的输出。(有限 = 步骤会结束;无歧义 = 每个步骤一个意思。)
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
例题:标识符表
- 写代码之前,在一张标识符表(identifier table)里列出每一项数据:它的变量(variable)名、数据类型(data type)和描述。
- 一家商店的库存程序存储
"Fruit"、20/02/2025、12.67和TRUE。考题要求为每一项给出名字和类型。 Category : STRING(一类库存)、DateSold : DATE(售出时间)、ItemCost : REAL(成本)、InStock : BOOLEAN(是否有货?)。- 每一行的名字和类型合计一分,所以类型要写得和伪代码指南完全一样:
INTEGER、REAL、STRING、CHAR、BOOLEAN、DATE。
标识符表在写代码之前给每一项数据命名
In an identifier table, the data type for a value such as 12.67 (a cost) is ____. · 在标识符表中,像 12.67(一个成本)这样的值的数据类型是 ____。
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. · 带小数部分的数是 REAL。INTEGER 用于整数,STRING 用于文本,BOOLEAN 用于 TRUE/FALSE,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
三种构造
IF … THEN … ELSE … ENDIF
- 赋值(assignment)用箭头存入一个值,
Total ← Total + Value;=用于比较。DIV是整数除法,MOD是余数,所以17 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
任何算法的三个构建块
Selection: follow the IF / ELSE 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. · 拖动分数,看哪个分支运行。选择依次测试每个条件,取第一个为真的——这就是 IF … ELSE IF … ELSE 的工作方式。
Match each of the three programming constructs to what it does. · 把三个编程构造的每一个与它做的事配对。
Every algorithm is built from just three constructs — sequence, selection and iteration. · 每个算法都只由三个构造构建——顺序、选择和迭代。
In this pseudocode, which symbol means assignment (store a value)? · 在这个伪代码中,哪个符号表示赋值(存储一个值)?
Assignment uses ← (e.g. x ← 5); = is reserved for comparison. · 赋值用 ←(例如 x ← 5);= 保留给比较。
What is the value of 17 MOD 5? · 17 MOD 5 的值是多少?
MOD gives the remainder: $17 = 3 \times 5 + 2$, so 17 MOD 5 = 2. (17 DIV 5 = 3.) · MOD 给出余数:$17 = 3 \times 5 + 2$,所以 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
用哪种循环?
- 知道要重复多少次时用
FOR … NEXT:计数循环(count-controlled loop)。 WHILE … ENDWHILE在每一轮之前测试条件,所以循环体可能运行零次:前测循环(pre-condition loop)。REPEAT … UNTIL在每一轮之后测试,所以循环体总是至少运行一次:后测循环(post-condition loop)。验证输入是经典的例子。- 一个"描述迭代构造"的答案要说出循环的名字、条件在哪里测试,以及由此带来的结果。
WHILE 循环在循环体运行前测试;REPEAT … UNTIL 循环在之后测试
How does a WHILE loop differ from a REPEAT...UNTIL loop? · 一个 WHILE 循环与一个 REPEAT...UNTIL 循环有什么不同?
WHILE checks first (can run 0 times); REPEAT...UNTIL checks after, so it always runs at least once. · WHILE 先检查(能运行 0 次);REPEAT...UNTIL 之后检查,所以它总是至少运行一次。
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). · 一个 FOR 循环是计数控制的(它重复固定的次数),而一个 WHILE 循环是条件控制的(它重复直到一个条件改变)。
Use FOR when you know how many passes; use WHILE/REPEAT when you loop until something becomes true. · 当你知道多少遍时用 FOR;当你循环直到某事变为真时用 WHILE/REPEAT。
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).
例题:从文字到伪代码
- 任务:输入 100 个整数,只把正数加起来,输出总和。
- 先规划数据:
Count、Total和NextNumber,都是INTEGER。然后三种构造完成其余部分。
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
- 后续问题要求你指出用到的构造:迭代(
FOR循环把输入重复 100 次)、选择(IF决定一个值是否被加上)和顺序(语句按次序运行)。
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.
在代码片段中识别构造
- 一道常考题给出五段伪代码,要你勾出每一段用了赋值、选择、迭代中的哪些。
Result ← CalculateTotal()是赋值。WHILE IsClosed是迭代。REPEAT … INPUT Value … UNTIL Sales[4] > Value既是迭代又是赋值(INPUT存入一个值)。 IF Sales[Current] <= 150 THEN Discount ← TRUE ENDIF- 看片段的每一行,不只是第一行。一行可能需要两个勾。
Which constructs does this extract use? REPEAT … INPUT Value … UNTIL Total > 100. Select all · 所有 that apply. · 这段代码用了哪些构造?REPEAT … INPUT Value … UNTIL Total > 100。选出所有适用的。
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 是迭代,INPUT Value 存入一个值,算作赋值。没有 IF 或 CASE,所以没有选择——UNTIL 的条件控制循环,并不在分支之间做选择。
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
流程图
- 流程图(flowchart)用图画记录同一个算法。椭圆是
START和END,矩形是处理,平行四边形是INPUT/OUTPUT,菱形是判断。 - 菱形是选择发生的地方,一条向上折回的流程线就是一个循环。
- 考题两个方向都会问:从流程图写伪代码,以及从伪代码或结构化英语画流程图。你画的每个符号都应对应一行伪代码。
每种流程图符号对应一种伪代码语句
In a flowchart, what does a diamond represent? · 在流程图中,菱形代表什么?
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. · 菱形是选择发生的地方,流程线折回上方的菱形就是循环测试。矩形是处理,平行四边形是输入/输出,椭圆是 START 和 END。
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
例题:猜数游戏
- 程序从 1 到 100 中随机选一个整数,然后反复要求猜测,直到用户猜中。用户至少要猜一次,所以循环是
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"
- 对照流程图:一个菱形做循环测试,两个菱形给提示,每条流程线最后都回到
INPUT Guess或到达END。
猜数游戏的流程图:循环回到输入,直到猜测匹配
Why is REPEAT … UNTIL the right loop for the guessing game? · 为什么 REPEAT … UNTIL 是猜数游戏正确的循环?
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. · 后测循环总是先运行一次循环体再测试,正好匹配一个至少需要猜一次的游戏。WHILE 循环则需要在循环之前先猜一次,才有东西可测。
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
逐步求精
- 逐步求精(stepwise refinement)意味着从一个大纲开始,把每一步展开成更详细的步骤,一遍又一遍,直到每一步都能直接写成伪代码。
- "处理一个订单" → "获取商品"、"计算总额"、"收款" → "计算总额"变成"对每件商品,加上单价 × 数量;应用任何折扣"。
- 每一层都是上一层的细化,完成的各层合起来就是设计。"描述逐步求精"要写出大纲、展开和停止规则。
细化每一步,直到它能直接编码
Put the stages of stepwise refinement in order. · 把逐步求精的各阶段按顺序排列。
Outline first, then refine level by level; you stop when a step is one line of 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
逻辑语句
- 解决方案的各部分由逻辑语句定义:由比较(
=、<>、<、>、<=、>=)组成、用AND、OR和NOT连接的条件。 - 一个有效的分数:
Mark >= 0 AND Mark <= 100。顾客是会员或消费超过 50 就有折扣:IsMember OR Total > 50。 NOT (Mark < 40)和Mark >= 40说的是同一件事。写出语句,然后用边界两侧各一个值来测试它。
用 AND、OR 和 NOT 连接的比较构成算法需要的条件
NOT (Mark < 40) is true for exactly the same values of Mark as Mark >= 40. · NOT (Mark < 40) 为真的 Mark 值与 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. · 对"小于 40"取反得到"40 或更多"。测试边界:Mark = 40 时 Mark < 40 为假,所以它的 NOT 为真,而 40 >= 40 也为真。
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.
容易丢掉的分
←是赋值,=是比较。IF Total = 0是一个测试;单独一行的Total = 0不得分。- 每个构造都要关闭:
ENDIF、ENDWHILE、UNTIL、NEXT、ENDCASE。少一个结束符就丢掉结构分。 - 先声明再使用,累加总和要初始化为
0。 WHILE可能一次都不运行,REPEAT总是运行一次。选与任务匹配的循环,被问到时要说明理由。
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
你掌握了
- 算法的步骤无歧义、确定、有限、有效;在标识符表里规划数据
- 三种构造:顺序、选择(
IF/CASE)、迭代(FOR/WHILE/REPEAT);WHILE先测,REPEAT后测 - 流程图和伪代码描述同一个算法;逐步求精把大纲展开到可以编码
- 条件是逻辑语句:用
AND、OR、NOT连接的比较