Computational Thinking
A-Level Computer Science Topic 9 14:43 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Here is a task: build a system to run a whole shop's stock — every product, every sale, every delivery, every report.
有这样一个任务：做一个系统来管理一整家商店的库存——每一件商品、每一笔销售、 每一次进货、每一份报表。
As one giant problem, it is too big to hold in your head.
作为一个庞大的整体问题，它大到你脑子里根本装不下。
But a way of thinking tames it: computational thinking.
但有一种思维方式能把它驯服：计算思维。
You break the giant into small pieces, keep only what matters, and describe each piece as clear steps.
你把这个庞然大物拆成小块，只保留重要的部分， 再把每一块描述成清晰的步骤。
The impossible becomes a simple to-do list.
不可能的任务，就变成了一张简单的待办清单。
Computational thinking is the set of mental tools for analysing a problem and designing a solution a computer can run.
计算思维，是一套用来分析问题并设计计算机能运行的解决方案的思维工具。
Today: abstraction and decomposition, algorithms and their building blocks, and the ways we write them down.
今天我们讲：抽象与分解、算法及其构建模块，以及我们把它们写下来的各种方式。
Let's begin.
让我们开始吧。
The first tool is abstraction.
第一个工具是抽象。
It means keeping the details that matter, and throwing away the rest.
它的意思是保留重要的细节，把其余的都扔掉。
Think of a train-network map.
想想一张轨道交通网地图。
The real city is a tangle of curved streets and exact distances.
真实的城市是一团弯曲的街道和精确的距离。
The map throws all of that away, keeping only what a traveller needs — the stations, and which line joins them.
地图把这些全都扔掉，只保留旅客需要的东西—— 车站，以及哪条线把它们连起来。
It even straightens the lines.
它甚至把线路都拉直了。
It is wrong about geography, but perfect for finding your route.
它在地理上是错的， 但对于找路来说却是完美的。
That is abstraction: a simpler model of a complex thing.
这就是抽象：一个复杂事物的简化模型。
The examiner asks two separate things about abstraction, so answer them separately.
考官关于抽象会问两件不同的事，所以要分开回答。
Its purpose: to produce a simpler model of a problem that contains only the details needed to solve it.
它的目的：产生一个更简单的问题模型，只保留解决问题所需要的细节。
Its benefits: the problem becomes easier to understand and to solve, the solution is quicker to write and to test, it needs less memory and less processing, and the same model can be reused for similar problems.
它的好处：问题更容易理解、更容易求解， 方案写起来和测试起来更快，占用更少的内存和处理能力， 而且同一个模型可以用在类似的问题上。
Abstraction means keeping the essential features of a problem and ignoring the irrelevant detail, which leaves you a simpler model to reason about.
抽象的意思是保留问题的本质特征，忽略无关的细节，从而留下一个更简单、便于思考的模型。
The train-network map is the classic example: it keeps the stations and the lines, and throws away the geography — the real track curves, the real distances, everything except what a passenger needs.
轨道交通网地图是最经典的例子：它保留了车站和线路，扔掉了地理——真实轨道的弯曲、 真实的距离，除了乘客需要的以外，其余全都不要。
Two more the syllabus names.
考纲还点名了两个。
A class in object-oriented programming keeps only the attributes and methods the system actually needs, not everything true about the real thing.
面向对象程序设计里的类，只保留系统真正需要的属性和方法， 而不是关于那个真实事物的一切。
And a function hides a piece of work behind a name, so you can use it without knowing how it works.
而函数把一段工作藏在一个名字后面， 让你不必知道它怎么做就能用它。
Why bother?
为什么要这样做？
Because a full model of any real problem would simply be too big to reason about.
因为任何真实问题的完整模型，都会大得根本没法思考。
Put it in the examiner's own phrase: the purpose of abstraction is to produce an abstract model of the problem — a simpler one that keeps only what is needed to solve it.
用考官自己的说法：抽象的目的，是产生问题的一个抽象模型—— 一个更简单的模型，只保留解决问题所需要的东西。
Decomposition means breaking a large problem into smaller sub-problems, and there are four steps.
分解的意思是把一个大问题拆成若干更小的子问题，一共有四步。
Find the main parts of the task.
找出任务的主要组成部分。
Break each into smaller sub-tasks.
把每一部分拆成更小的子任务。
Continue until each is small enough to design directly.
一直拆下去，直到每一个都小到可以直接设计为止。
Then solve the small tasks and combine them.
然后解决这些小任务，再把它们组合起来。
Follow the example: manage stock splits into record sales, record deliveries, produce reports.
跟着例子看：管理库存分成记录销售、记录进货、生成报表。
Then record sales splits again into look up product, decrease stock count, save the transaction.
然后记录销售又继续分成查找商品、减少库存数量、保存这笔交易。
Three payoffs, and a question may ask for them.
有三个好处，题目可能会问到。
Big problems become manageable.
大问题变得可管理。
A team can divide the work.
团队可以分工。
And the code comes out modular, because each of those leaves becomes a procedure or a function.
而且代码天然是模块化的，因为每一片叶子都会变成一个过程或者一个函数。
The second tool is decomposition: breaking a big problem into smaller sub-problems, each easy to solve on its own.
第二个工具是分解：把一个大问题拆成更小的子问题，每一个都容易单独解决。
Take manage stock. Break it into record sales, record deliveries, and produce reports.
拿"管理库存"来说，把它拆成记录销售、记录进货和生成报表。
Then break record sales again — look up the product, lower its count, save the sale.
然后再拆"记录销售"—— 查找商品、减少它的数量、保存这笔销售。
Keep going until each piece is small enough to code.
一直拆下去，直到每一块都小到可以直接编码。
Now a team can share the work, and each piece becomes its own tidy module.
这样一个团队就能分工，而每一块也成了它自己整洁的模块。
With a small piece in hand, you write an algorithm — a solution written as a sequence of clear steps.
手里有了一小块问题，你就写一个算法——一个用一连串清晰步骤写出来的解法。
A good algorithm has four qualities: each step is unambiguous, the same input always gives the same output, the steps end, and each one can actually be done.
一个好的算法有四个特点：每一步都没有歧义，相同的输入总是给出相同的输出， 步骤会结束，而且每一步都确实能做到。
Every algorithm follows one shape: take input, process it, produce output.
每个算法都遵循同一个形状：接收输入、处理、产生输出。
And before your first step, name your data in an identifier table — each variable, its type, and what it holds.
而在写第一步之前，先在标识符表里给你的数据命名——每个变量、它的类型，以及它保存的内容。
An algorithm is a solution expressed as a sequence of defined steps, and four properties are what make it one.
算法是用一串有定义的步骤表达出来的解法，而它之所以是算法，靠的是四条性质。
Unambiguous: each step has exactly one meaning, so two people reading it do the same thing.
无歧义：每一步恰好只有一种含义，两个人读了会做同一件事。
Deterministic: the same input always gives the same output.
确定性：同样的输入永远给出同样的输出。
Finite: the steps end — it must terminate.
有限性：步骤会结束——它必须能终止。
And effective: each step can actually be carried out.
以及可行性：每一步都确实能被执行。
Then the point that carries a mark on its own: an algorithm says WHAT to do, and is independent of the language you eventually implement it in.
然后是那个本身就值一分的要点： 算法说的是做什么，而与你最终用哪种语言实现无关。
The same algorithm can be written in Python, in Java, or on paper.
同一个算法可以用 Python 写，可以用 Java 写，也可以写在纸上。
Before writing any algorithm, list every piece of data in an identifier table: the variable name, its data type, and a description.
在写任何算法之前，先把每一项数据列进一张标识符表：变量名、数据类型，以及说明。
Here Category is a STRING, SaleDate is a DATE, ItemCost is a REAL, InStock is a BOOLEAN.
这里 Category 是字符串，SaleDate 是日期，ItemCost 是实数，InStock 是布尔值。
Two rules.
有两条规则。
Use descriptive names — ItemCost, not x — because the table is also documentation.
用有描述性的名字——写 ItemCost，不要写 x——因为这张表同时也是文档。
And know the common types: INTEGER, REAL, STRING, CHAR, BOOLEAN, DATE, plus arrays.
还要记住常见的类型：整数、实数、字符串、字符、布尔、日期，再加上数组。
The real value of the table is that it forces you to name and type every piece of data BEFORE you write code, which is when the mistakes are cheap.
这张表真正的价值在于，它逼着你在写代码之前就把每一项数据命名并定好类型， 而那正是犯错代价最低的时候。
Two habits earn marks on every question of this kind: declare every variable you use, with the type from your identifier table, and initialise every counter and total before the loop that uses it.
这类题目里有两个习惯每次都能拿分： 你用到的每一个变量都要声明，类型取自你的标识符表； 每一个计数器和总和，都要在用到它的循环之前初始化。
Every algorithm, however complex, is built from just three constructs.
每个算法，无论多复杂，都只由三种结构构建而成。
Sequence: steps run one after another, top to bottom.
顺序：步骤一个接一个地运行，从上到下。
Selection: the program chooses a path, with if-then-else, based on a condition.
选择：程序根据一个条件，用"如果-那么-否则"来选一条路。
And iteration: a block repeats — a WHILE loop tests the condition before each pass, so it may run zero times.
还有迭代：一个代码块不断重复—— WHILE 循环在每次进入前测试条件，所以可能一次都不运行。
Sequence, selection, iteration — master these three, and you can build any algorithm at all.
顺序、选择、迭代——掌握这三种，你就能构建出任何算法。
Selection and iteration each come in more than one shape, and the exam expects all of them.
选择和迭代各自都不止一种形式，而考试要求你全部掌握。
Selection first.
先看选择。
IF-THEN-ELSE chooses between two paths.
IF-THEN-ELSE 在两条路径之间做选择。
But when one variable has many possible values, use CASE OF, which lists each value with its own action and closes with ENDCASE — far cleaner than a tower of nested IFs.
但当一个变量有很多种可能取值时，就用 CASE OF—— 它把每个取值和对应的动作一一列出，最后以 ENDCASE 结束，比一层层嵌套的 IF 清爽得多。
Iteration comes in three.
迭代有三种。
A FOR loop runs a fixed number of times, counting from a start value to an end value, so reach for it when you know the count in advance.
FOR 循环运行固定的次数，从起始值数到终止值，所以在你事先知道次数时用它。
A WHILE loop tests its condition before each pass, so if the condition is false at the very start, the body runs zero times.
WHILE 循环在每一轮之前测试条件，所以如果一开始条件就为假，循环体一次都不会运行。
A REPEAT-UNTIL loop tests after each pass, so the body always runs at least once.
REPEAT-UNTIL 循环在每一轮之后测试条件，所以循环体至少运行一次。
That difference is a favourite question.
这个区别是常考题。
Ask for a password with REPEAT and the user is always asked once.
用 REPEAT 要求输入密码，用户总会被问一次。
Walk an empty list with WHILE and nothing happens — which is exactly what you want.
用 WHILE 遍历一个空列表，什么都不会发生—— 而这正是你想要的结果。
Name the three loops by their syllabus names, because a question will ask which one and why.
三种循环要用考纲的名字点名，因为题目会问「用哪一种、为什么」。
A count-controlled loop repeats a fixed number of times.
计数控制循环重复固定的次数。
A pre-condition loop tests before the body, so the body may never run.
前置条件循环在循环体之前判断，所以循环体可能一次都不执行。
A post-condition loop tests after the body, so the body always runs at least once.
后置条件循环在循环体之后判断，所以循环体至少执行一次。
The operations you will actually write.
下面是你真正会写的那些操作。
Assignment uses an arrow, not an equals sign — x arrow five.
赋值用一个箭头，不是等号——x 箭头 五。
The equals sign is reserved for comparison, and mixing them up is a classic slip.
等号是留给比较用的，把两者搞混是典型的失误。
The comparison operators are equals, less-than-greater-than for not-equal, and the four inequalities; the logical connectives are AND, OR and NOT.
比较运算符有等于、用小于号加大于号表示的不等于，以及四个不等式； 逻辑连接词是 AND、OR 和 NOT。
For arithmetic you have plus, minus, times and divide, plus DIV for integer division and MOD for the remainder — those two are worth memorising.
算术运算有加减乘除， 再加上表示整数除法的 DIV 和表示余数的 MOD——这两个值得背下来。
The string operations are LENGTH, LEFT, RIGHT, MID, and the ampersand for concatenation, meaning joining.
字符串操作有 LENGTH、LEFT、RIGHT、MID，以及表示拼接、也就是连接的与号。
And every program follows one shape: input, process, output.
而每一个程序都遵循同一个形状：输入、处理、输出。
Listing the inputs and outputs first makes the algorithm cleaner before you write a line.
先把输入和输出列出来，能让算法在你动笔之前就更清爽。
A flowchart uses five standard shapes, and you must know which is which.
流程图用五种标准图形，你必须分清哪个是哪个。
A rounded rectangle is Start or Stop.
圆角矩形表示开始或结束。
A parallelogram is input or output.
平行四边形表示输入或输出。
A plain rectangle is a process.
普通矩形表示处理。
A diamond is a decision.
菱形表示判断。
And arrows show the flow of control.
而箭头表示控制的流向。
Here is the conversion rule that makes questions easy: each IF becomes a decision diamond, each loop becomes a back-arrow returning to an earlier point, and a plain sequence becomes stacked rectangles.
下面这条转换规则能让题目变简单： 每一个 IF 变成一个判断菱形，每一个循环变成一条回到前面某处的回退箭头， 而顺序结构就变成一摞叠起来的矩形。
In this example the decision "count less than n" has a Yes branch that loops back to read the next value — that back-arrow IS the loop.
在这个例子里， "计数小于 n"这个判断的"是"分支会绕回去读下一个数值——那条回退箭头就是循环。
Stepwise refinement starts with a high-level outline and expands each step until it is small enough to code.
逐步求精从一个高层的提纲出发，把每一步不断展开，直到小到可以直接编码为止。
Level one for averaging n numbers is just three lines in plain English: read in the numbers, compute the average, output the average.
对求 n 个数的平均值来说，第一层不过是三行大白话：读入这些数、计算平均值、输出平均值。
Level two expands those into real pseudocode: input n, set total to zero, loop from one to n reading a value and adding it to the total, then divide and output.
第二层把它们展开成真正的伪代码：输入 n，把总和置零，从一循环到 n 读入一个数值并加到总和上，然后相除并输出。
The property that makes it refinement rather than rewriting is this: each level keeps the previous structure and only adds detail.
让它成为"求精"而不是"重写"的性质在于：每一层都保留上一层的结构，只增加细节。
Those three level-one steps are still visible inside level two, in the same order.
第一层的那三步，在第二层里依然看得见，而且顺序一样。
A logic statement is a Boolean condition that controls branching, built from comparisons, the connectives AND, OR and NOT, and brackets.
逻辑语句是控制分支的布尔条件，由比较式、连接词 AND、OR、NOT 以及括号构成。
Precedence runs highest to lowest: NOT, then AND, then OR — and use brackets whenever you are unsure.
优先级从高到低是：NOT，然后 AND，然后 OR——只要拿不准就加括号。
Three mistakes to avoid.
有三个要避免的错误。
Writing a equals one OR two is simply wrong; you must write a equals one OR a equals two, because OR joins two complete conditions.
写成 a 等于 一 OR 二 完全是错的； 你必须写 a 等于一 OR a 等于二，因为 OR 连接的是两个完整的条件。
Writing NOT a greater than five means NOT of the whole comparison, which is a less than or equal to five — not what most people intend.
写 NOT a 大于五，意思是对整个比较取非，也就是 a 小于或等于五—— 这多半不是人们想表达的意思。
And De Morgan's law: NOT of A AND B is the same as NOT A OR NOT B.
还有德摩根定律： A 且 B 的非，等于 A 的非 或 B 的非。
That one is genuinely useful for simplifying an ugly condition.
这一条在化简一个难看的条件时是真的好用。
Let us do the classic one: write an identifier table and pseudocode to read ten numbers and output the largest.
我们来做那道最经典的题：写出标识符表和伪代码，读入十个数并输出最大的那个。
Start with the identifier table, because the marks begin there: Count is an INTEGER, the loop counter; Num is a REAL, the number just read; Max is a REAL, the largest so far.
从标识符表开始，因为分数就是从这里开始给的：Count 是整数，循环计数器； Num 是实数，刚读进来的那个数；Max 是实数，到目前为止的最大值。
Now the pseudocode: set Max low, loop ten times reading Num, and if Num is greater than Max then Max becomes Num.
然后是伪代码：把 Max 置得很低，循环十次读入 Num， 如果 Num 大于 Max，就让 Max 变成 Num。
Output Max at the end.
最后输出 Max。
And here is the design decision that actually carries the marks: initialising Max.
而下面这个设计决定才是真正拿分的地方：Max 的初始化。
It must start lower than any possible input — or better still, set it to the FIRST number read.
它必须从一个比任何可能的输入都低的值开始——或者更稳妥的做法， 直接把它设成读到的第一个数。
Initialise it to zero and the algorithm wrongly returns zero for a list of negative numbers, and your trace only exposes that bug if your test data include a negative.
要是把它初始化为零， 那么对一串负数，这个算法会错误地返回零， 而只有当你的测试数据里包含负数时，你的手工跟踪才会暴露这个错误。
The same algorithm can be written three ways.
同一个算法可以用三种方式写出来。
Structured English: plain sentences with indentation.
结构化英语：带缩进的普通句子。
A flowchart: boxes and arrows — a diamond for each decision, an arrow looping back for each repeat.
流程图：方框和箭头——每个判断画一个菱形，每次重复画一条回绕的箭头。
And pseudocode: keyword steps, closest to real code.
还有伪代码：关键字步骤，最接近真正的代码。
Start high-level, then expand each step with more detail until it is ready to code.
先写高层次的，再把每一步展开、加上更多细节， 直到它可以编码为止。
That last skill — stepwise refinement — is how big designs get built.
最后这项技能——逐步求精——正是大型设计得以建成的方式。
Three marks to lock in.
三个要拿稳的分。
First, define an algorithm precisely: an unambiguous, finite sequence of steps, independent of any language.
第一，准确地定义算法：一连串没有歧义的、有限的步骤，且与任何语言无关。
Second, use the three constructs correctly, and keep an identifier table with data types.
第二，正确地使用三种结构，并保留一张带数据类型的标识符表。
Third, break problems down — decomposition and abstraction first, then stepwise refinement.
第三，把问题拆解开——先分解和抽象，再逐步求精。
Get these, and this topic is yours.
掌握这些，这个专题就是你的了。
These definitions are marked against fixed wording, and the question wants one answer only.
这些定义是按固定措辞给分的，而且题目只要一个答案。
Abstraction is keeping the essential details of a problem and leaving out those that are not needed.
抽象，是保留问题的关键细节，略去不需要的细节。
Decomposition is breaking a problem into smaller sub-problems, each of which can be solved separately.
分解，是把一个问题拆成更小的子问题，每个都可以单独解决。
An algorithm is a solution to a problem expressed as a sequence of defined steps.
算法，是把问题的解法表示成一串有明确定义的步骤。
An identifier table lists each identifier used in an algorithm with its data type and a description of its purpose.
标识符表，列出算法中用到的每一个标识符，连同它的数据类型和用途说明。
Pseudocode is a structured, language-independent way of writing the steps of an algorithm; a flowchart shows those steps and decisions using standard symbols joined by arrows.
伪代码，是一种结构化、与具体语言无关的写算法步骤的方式； 流程图，用标准符号加箭头把这些步骤和判断画出来。
Sequence is statements executed one after another in the order written; selection is choosing which statements to execute according to a condition; and iteration is repeating a group of statements while, or until, a condition holds.
顺序，是语句按写下来的次序一条接一条执行； 选择，是根据条件决定执行哪些语句； 迭代，是在某个条件成立期间、或者直到某个条件成立为止，重复一组语句。
And the mistakes that lose marks every year.
再说每年都在丢分的那些错误。
Use the arrow to assign; the equals sign is a comparison.
赋值要用箭头；等号是比较。
Close every construct — ENDIF, ENDWHILE, ENDCASE, NEXT — because the closing word is where the mark for that construct is checked.
每个构造都要闭合——ENDIF、ENDWHILE、ENDCASE、NEXT—— 因为这个构造的分正是在闭合的那个词上核对的。
Initialise a total or counter before the loop, or the algorithm adds to a value that never existed.
总和或者计数器要在循环之前初始化，否则算法是在往一个从来不存在的值上加。
Do not use a FOR loop when the number of repetitions is unknown: reading until a sentinel value or a correct guess needs WHILE or REPEAT UNTIL.
重复次数未知时不要用 FOR 循环： 读到哨兵值为止、或者猜对为止，需要用 WHILE 或者 REPEAT UNTIL。
Each side of OR and AND must be a complete comparison — Age greater than 65 OR less than 5 is not one.
OR 和 AND 的每一边都必须是一个完整的比较—— 「年龄大于 65 或者 小于 5」不算。
And a three-mark "explain why decomposition is used" needs three DIFFERENT benefits, not one benefit written three ways.
另外三分的「解释为什么使用分解」要三个不同的好处， 不是把同一个好处换三种说法。