The Program Development Life Cycle
IGCSE Computer Science Topic 7 9:17 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Every app on your phone was written by someone like this.
你手机上的每一个应用，都是由这样的人写出来的。
But they did not start by typing code.
但他们并不是一上来就敲代码。
Before the first line, the problem was studied, the solution was drawn, and the tests were planned.
在写下第一行之前，问题已经被研究过，方案已经被画出来，测试也已经计划好了。
Here is what happens when you skip that.
如果跳过这些步骤，就会发生这样的事。
A school types in a new student.
学校要录入一名新学生。
Age, minus four.
年龄，负四。
The program saves it.
程序把它保存了。
Age, two hundred and six.
年龄，二百零六。
Saved again.
又保存了。
Now the class report says the average age is forty-one, and the printout crashes.
现在班级报表显示平均年龄是四十一岁， 打印的时候程序崩溃了。
None of this is a hard problem.
这里没有一个是难题。
The program was simply never planned, never checked, and never tested.
这个程序只是从来没有被规划过、 没有被检查过，也没有被测试过。
Topic seven: algorithm design and problem solving.
第七章：算法设计与问题求解。
Today we go from a problem all the way to a working program: the four stages, the design tools, checking data, trace tables, test data, and the standard algorithms.
今天我们要从一个问题一路走到一个能运行的程序： 四个阶段、设计工具、数据检查、追踪表、测试数据，以及那些标准算法。
Here is the plan.
本节的安排是这样的。
First the development life cycle, the four stages every program goes through.
首先是开发生命周期，每个程序都要经过的四个阶段。
Then the three design tools.
然后是三种设计工具。
Then algorithms, and how every one splits into input, process and output.
接着是算法，以及每个算法如何拆成输入、处理和输出。
Then validation and verification.
然后是验证与核实。
Then trace tables.
再然后是追踪表。
And last, searching and sorting.
最后是查找与排序。
The program development life cycle has four stages.
程序开发生命周期有四个阶段。
Analysis: study the problem and work out what is needed.
分析：研究问题，弄清楚到底需要什么。
Design: plan how the program will work, before any code.
设计：在写任何代码之前，先规划程序如何运作。
Coding: write the code, using iterative testing — test small parts again and again as you build them.
编码：写出代码，并且边写边测试小的部分。
Testing: run the finished program with test data to find errors.
测试：用测试数据运行完成的程序，找出错误。
And look at the orange arrow: testing sends you back to design, to fix and refine.
再看那条橙色的箭头： 测试会把你送回设计阶段，去修正和改进。
Analysis needs two skills.
分析阶段需要两项技能。
The first is abstraction: keep only the details that matter and throw the rest away.
第一是抽象：只保留重要的细节，把其余的丢掉。
A metro map is not a real map.
地铁图并不是真正的地图。
It drops the streets and keeps only the stops and the lines.
它去掉了街道，只留下站点和线路。
That is all a traveller needs.
旅客需要的就只有这些。
The second is decomposition: break one big problem into smaller parts, or sub-systems, again and again, until every piece is small enough to write.
第二是分解：把一个大问题拆成更小的部分，也就是子系统，一层一层拆下去， 直到每一块都小到可以直接写出来。
In the design stage you plan the solution with three tools.
在设计阶段，你用三种工具来规划方案。
A structure diagram shows the parts of a system and how they fit together.
结构图展示一个系统由哪些部分组成， 以及它们如何拼在一起。
A flowchart uses boxes and arrows to show the steps in order.
流程图用方框和箭头按顺序展示步骤。
Pseudocode writes the steps in simple, code-like English.
伪代码用简单的、像代码的英文写出步骤。
None of the three is a real language: they plan the solution before any code is written.
这三种都不是真正的编程语言： 它们是在写任何代码之前先把方案规划好。
A flowchart uses four standard shapes.
流程图用四种标准形状。
A rounded box means start or end.
圆角框表示开始或结束。
A slanted box means input or output.
斜的平行四边形表示输入或输出。
A rectangle is a process, a step that changes a value.
矩形是处理，也就是改变某个值的一步。
A diamond is a decision, with two ways out: yes and no.
菱形是判断，它有两条出路：是和否。
Now read the chart.
现在来读这张图。
It reads a number, sets the total to zero, then adds one, two, three, and so on, until the counter passes that number, and outputs the total.
它读入一个数，把总和设为零，然后加一、加二、加三， 一直加下去，直到计数器超过那个数，最后输出总和。
An algorithm is a set of steps, in the right order, that solves a problem.
算法是一组按正确顺序排列的步骤，用来解决问题。
The order matters.
顺序很重要。
Swap two steps and you get a different answer, or the program fails.
把两步对调， 答案就会变，或者程序会失败。
During design you often draw those steps as a program flowchart: boxes for the work, diamonds for the decisions, and arrows for the path.
在设计阶段，你常常把这些步骤画成程序流程图： 方框表示处理，菱形表示判断，箭头表示路径。
That picture is not the code.
那张图不是代码。
It is the plan the coder will follow, so the steps stay in the right order when they are written.
它是编码的人 要跟着走的计划，好让步骤在写成代码时仍然保持正确的顺序。
Every algorithm, however big, breaks into three parts.
每一个算法，不管多大，都能拆成三个部分。
Input: the data that goes in.
输入：进去的数据。
Process: the work done on that data.
处理：对这些数据做的工作。
Output: the result that comes out.
输出：出来的结果。
Take the average of three marks.
以三个分数的平均值为例。
The input is the three marks.
输入是那三个分数。
The process is adding them and dividing by three.
处理是把它们相加再除以三。
The output is the average.
输出就是平均值。
Name those three parts, plus any storage the system needs, and you have decomposed the problem.
能说出这三个部分，再加上系统需要的存储，你就已经把问题分解好了。
Validation asks one question: is this data sensible?
验证只问一个问题：这个数据合不合理？
A range check says the value must sit between a lowest and a highest value.
范围检查要求数值落在最小值和最大值之间。
A length check counts the characters.
长度检查数字符的个数。
A type check makes sure a number is a number, not letters.
类型检查确保数字就是数字，而不是字母。
A presence check makes sure something was entered.
存在性检查确保确实输入了内容。
A format check makes sure the pattern is right, like a date.
格式检查确保样式正确，比如日期。
A check digit is an extra digit on the end of a long number, recalculated to catch typing mistakes.
校验码是长数字末尾多加的一位，重新算一遍就能发现输入时的打字错误。
Validation cannot check that the data is true.
验证不能检查数据是不是真的。
It only checks that the data is allowed.
它只检查数据是不是被允许的。
A birthday of the first of January nineteen ninety is sensible, so every check will pass, even if the real birthday is different.
一九九零年一月一日这个生日是合理的，所以每一项检查都会通过，哪怕真正的生日 并不是这一天。
A length check on a password might demand eight characters or more.
密码的长度检查可能要求至少八个字符。
A format check on a date might demand day, then month, then year, with slashes.
日期的格式检查可能要求 日、月、年，中间用斜杠。
Both still let a wrong but allowed value through.
这两种检查仍然会放过一个错误但被允许的值。
That is why verification exists.
这就是为什么还需要核实。
Validation and verification are not the same thing, and swapping them costs marks every year.
验证和核实不是一回事，把它们弄反每年都会失分。
Validation asks whether the data is sensible.
验证问的是数据合不合理。
Verification asks whether it was copied correctly.
核实问的是数据有没有被正确地抄录进来。
There are two verification methods.
核实有两种方法。
A visual check: a person compares the typed data with the original.
目视检查：由人把输入的数据和原件对照一遍。
Double entry: the data is typed twice and the computer compares the copies.
双重输入：同一份数据输入两次， 由计算机比较这两份。
A birthday can pass every validation check and still be wrong.
一个生日可以通过所有的验证检查，却仍然是错的。
Now choose the right test data.
现在来选对测试数据。
Say an age from zero to one hundred and twenty is allowed.
假设允许的年龄是从零到一百二十。
Normal data should be accepted, like twenty-five.
正常数据是应当被接受的，比如二十五。
Abnormal data should be rejected, like minus four, or the word cat.
异常数据是应当被拒绝的，比如负四， 或者"猫"这个词。
Extreme data is the largest and smallest values still accepted: zero, and one hundred and twenty.
极端数据是仍然会被接受的最大值和最小值：零，和一百二十。
Boundary data is a pair either side of a limit: one hundred and twenty is accepted, one hundred and twenty-one is not.
边界数据是限值两侧成对的两个值：一百二十被接受，一百二十一不被接受。
A trace table lets you follow an algorithm by hand.
追踪表让你用手跟着算法走一遍。
Write one column for every variable, one for the output, and one row for every pass through the loop.
每个变量写一列，输出写一列， 循环每走一趟就写一行。
Here the total starts at zero.
这里总和从零开始。
The counter runs from one to five and is added to the total each time: one, three, six, ten, fifteen.
计数器从一走到五，每一次都把它加到总和上： 一、三、六、十、十五。
The loop stops and fifteen is printed.
然后循环停止，十五被打印出来。
So the algorithm adds up the numbers up to the number you typed in.
所以这个算法就是把一直到你输入的那个数全部加起来。
Now you try one.
现在换你来做一个。
The variable starts at twenty.
变量从二十开始。
While it is greater than one, halve it, keeping only the whole number, and add one to the counter.
只要它大于一，就把它减半，只保留整数部分， 并把计数器加一。
What does it output?
它会输出什么？
Pause the video and fill the table yourself.
先暂停视频，自己把表填一遍。
Ready?
好了吗？
Twenty halves to ten, counter one.
二十减半得十，计数器一。
Ten halves to five, counter two.
十减半得五，计数器二。
Five halves to two, counter three.
五减半得二，计数器三。
Two halves to one, counter four.
二减半得一，计数器四。
One is not greater than one, so the loop stops.
一不再大于一，循环停止。
The output is four: the number of times you can halve twenty before you reach one.
输出是四： 也就是二十可以减半多少次才降到一。
Two habits protect the marks on a trace table.
两个习惯能保住追踪表上的分数。
First, test the condition before each pass, not after.
第一，在每一趟之前检查条件，而不是之后。
If the loop says while the value is greater than one, you check that before you halve.
如果循环说只要那个值大于一，你就要在减半之前先检查。
Second, write a new row for every pass.
第二，每一趟都新写一行。
Trying to hold the values in your head is what makes traces go wrong.
把数值记在脑子里，正是追踪表做错的原因。
And remember: D I V keeps only the whole-number part.
还要记住：整除，也就是 D I V， 只保留整数部分。
Twenty divided by two is ten.
二十除以二是十。
Five divided by two is two, not two point five.
五除以二是二，不是二点五。
First, the linear search.
首先是线性查找。
You start at the first item and compare it with the value you want.
你从第一个元素开始，把它和你要找的值比较。
Not it, move on.
不是它，往下走。
Not it, move on.
不是它，往下走。
You stop as soon as you find a match, or when you reach the end and report that it is not there.
一旦找到匹配就停下来；或者走到末尾，报告没有找到。
It works on any list, sorted or not, but in the worst case you check every single item.
它对任何列表都能用，排没排序都行；但在最坏的情况下，你要把每一个元素都检查一遍。
Second, the bubble sort, which puts a list in order.
第二个是冒泡排序，它把列表排好序。
Compare the first two items.
比较前两个元素。
If they are in the wrong order, swap them.
如果顺序不对，就交换它们。
Then compare the next pair, and the next, all the way to the end.
然后比较下一对，再下一对，一直比到末尾。
That is one pass, and it pushes the largest value to the end.
这就是一趟，它会把最大的值推到最后。
Then you go again.
然后再来一趟。
You stop when a whole pass makes no swaps at all, because the list is now sorted.
当某一趟一次交换都没有发生时就停下来，因为列表已经排好序了。
Four more standard methods, each one line inside a loop.
还有四种标准方法，每一种都是循环里的一行。
Watch the trackers as the values arrive.
看着数值进来时这些计数器的变化。
Totalling: keep adding each value to a running total.
求和：把每个数值不断加到一个累计的总和上。
Counting: add one to a counter each time something happens.
计数：每发生一次，就把计数器加一。
Maximum: keep the largest value seen so far.
最大值：记住到目前为止见过的最大值。
Minimum works the same way, downwards.
最小值的做法一样，只是方向相反。
The average is the total divided by how many values there are.
平均值就是总和除以数值的个数。
Four marks students throw away.
四个学生白白丢掉的分。
First, validation checks that the data is sensible; verification checks that it was copied correctly.
第一，验证检查数据是否合理；核实检查数据是否被正确抄录。
Second, extreme data is the largest and smallest values still accepted, while boundary data is the pair either side of a limit.
第二，极端数据是仍然会被接受的最大值和最小值，而边界数据是限值两侧成对的两个值。
Third, in a trace table write one row for every pass.
第三，在追踪表里，循环每走一趟就写一行。
Fourth, if you are asked what an algorithm does, give its purpose, not a line-by-line description.
第四，如果问你某个算法做什么，要说出它的用途，而不是一行一行地复述。