Algorithms and Programming
AP Computer Science Principles Topic 3 9:17 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Imagine a phone book with a million names, and you must find one.
想象一本有一百万个名字的电话簿，而你要从中找出一个。
Check them one at a time, and you could be there all day.
如果一个一个地查，你可能要花上一整天。
There is a way to find it in about twenty steps.
但有一种办法，大约二十步就能找到。
That way is an algorithm: a plan so exact that a machine can follow it.
这种办法就是算法：一份精确到机器都能照着做的计划。
This is Big Idea Three.
这是大概念三。
We start with the smallest pieces — variables, conditions and loops — then build up to lists, searching and procedures.
我们先从最小的部分开始——变量、条件和循环—— 再一步步搭到列表、搜索和过程。
Every line of code you see is AP CSP pseudocode, the exam's own language-neutral reference.
屏幕上的每一行代码都用 AP 伪代码，也就是考试自己的语言。
A variable is a named box that holds one value.
变量是一个有名字的盒子，里面只放一个值。
Here are two, a and b.
这里有两个：a 和 b。
The left arrow is assignment: it puts the value on the right into the box on the left.
左箭头表示赋值：它把右边的值放进左边的盒子。
So a now holds five.
所以 a 现在装着五。
The next line adds three to a and stores the sum in b, so b holds eight.
下一行把三加到 a 上，再把和存进 b，所以 b 装着八。
Now watch.
现在注意看。
We assign to a again, and the old five is replaced by twelve.
我们再一次给 a 赋值，原来的五就被十二替换掉了。
But b does not change.
但是 b 不会变。
Programs also calculate, and the mathematical expressions have one operator that is easy to forget: MOD.
程序也要做计算。 有一个运算符很容易忘：MOD。
Here are seventeen items, packed five to a box.
这里有十七个东西，每五个装一盒。
Three boxes fill up, and two are left over.
三盒装满了，还剩下两个。
That leftover is the remainder, and MOD hands it to you.
剩下的这部分就是余数，MOD 把它交给你。
So if a number MOD two is zero, the number is even. Programs handle text too.
所以，如果一个数 MOD 二等于零，这个数就是偶数。
A string is an ordered row of characters, and joining two strings is called concatenation.
程序也要处理文本。 字符串是一串有顺序的字符，把两个字符串接起来叫做拼接。
Every decision a program makes starts with a Boolean expression: something that is either true or false.
程序做的每一个判断，都从布尔表达式开始：它的结果不是真就是假。
Operators come in three families.
运算符分成三类。
Arithmetic operators give you a number.
算术运算符给你一个数。
Relational operators compare two values and give back true or false.
关系运算符比较两个值，返回真或假。
And logical operators join conditions: NOT reverses a value, AND needs both sides true, OR needs at least one.
逻辑运算符把条件连起来：NOT 取反，AND 要两边都为真，OR 只要有一边为真。
A conditional chooses which code to run.
条件语句决定运行哪一段代码。
The condition here asks whether the score is sixty or more.
这里的条件问：分数是不是六十或以上。
Give it seventy-two: the condition is true, so the first block runs and the program shows Pass.
给它七十二：条件为真，于是第一个代码块运行，程序显示 Pass。
Give it forty-five: now it is false, so the ELSE block runs and it shows Fail.
给它四十五：这时条件为假，于是 ELSE 里的代码块运行，显示 Fail。
Never both.
绝不会两个都运行。
To choose between more than two paths, use a nested conditional: an IF inside another IF, or a chain of ELSE IF.
要在两条以上的路里选，就用 ELSE IF 串起来。
Only the first true branch runs, and the rest are skipped.
只有第一个为真的分支会运行，其余的都跳过。
Conditionals are the name the exam uses for selection.
条件语句是考试给选择结构起的名字。
An IF block runs only when its condition is true.
IF 代码块只在条件为真时运行。
ELSE is the other path.
ELSE 是另一条路。
Nested conditionals put one IF inside another, or chain ELSE IF, so you can choose among more than two paths.
嵌套条件把一个 IF 放进另一个里，或者用 ELSE IF 串起来，这样就能在两条以上的路里选。
Only the first matching branch runs.
只有第一个匹配的分支会运行。
Write both paths, not just the true one.
两条路都要写，不要只写为真的那条。
Iteration repeats instructions, so you only write them once.
迭代就是重复执行指令，这样你只需要写一次。
AP pseudocode has two loops.
AP 伪代码有两种循环。
This one repeats a fixed number of times: four times, so the body runs four times — watch.
这一种重复固定的次数：四次，所以循环体就运行四次——看。
The other repeats until a condition becomes true, and it may run many times first.
另一种一直重复，直到条件变成真为止，中间可能会先跑很多次。
Careful: if that condition never becomes true, the loop runs forever.
小心：如果那个条件永远不会变成真，循环就会一直跑下去。
That is an infinite loop.
这就是无限循环。
An algorithm is a finite list of steps that solves a problem, and every algorithm is built from three structures.
算法是解决某个问题的有限步骤，而任何算法都只由三种结构搭成。
Sequencing: do the steps in order, one after another.
顺序：按次序一步接一步地做。
Selection: test something, then take one path or the other.
选择：先做判断，再走这条路或那条路。
Iteration: repeat a block while a test stays true.
迭代：只要判断仍然为真，就重复这一块。
That is all a program is.
程序就只有这些。
A flowchart draws an algorithm with standard symbols: an oval starts and ends it, a parallelogram is input or output, a rectangle is a step, a diamond is a decision.
流程图用标准符号画出算法：椭圆表示开始和结束，平行四边形表示输入或输出， 矩形表示一个步骤，菱形表示一个判断。
Now read this one.
现在来读这一张。
It sets the total to zero and the counter to one.
它先把 total 设为零，把计数器设为一。
Then, while the counter has not passed n, it adds the counter to the total and moves the counter on.
接着，只要计数器还没超过 n，就把计数器加到 total 上，再把计数器加一。
When the test fails, it outputs the total.
当判断不再成立时，它就输出 total。
One variable holds one value.
一个变量只装一个值。
A list holds many, all under one name — that is data abstraction, this course's main tool for managing complexity.
列表把很多值装在同一个名字下——这就是数据抽象， 也是本课程管理复杂度的主要工具。
Each value has a position called its index.
每个值都有一个位置，叫做索引。
AP pseudocode is 1-indexed — the first index is one, not zero — so scores index two is seventy-five.
在 AP 伪代码里，第一个索引是一，不是零， 所以 scores 的索引二是七十五。
You can replace a value, append one to the end, insert one, remove one, or ask for the length.
你可以替换某个值、在末尾追加、插入、删除，也可以问它有多长。
Now trace a real code segment.
现在来追踪一段真实的代码。
The list holds eighty-eight, seventy-four, ninety-five and sixty.
列表里是八十八、七十四、九十五和六十。
How many are eighty or more?
有多少个在八十或以上？
Start with count at zero, and take one value at a time.
先让 count 等于零，然后一次取一个值。
First, eighty-eight: eighty or more is true, so count becomes one.
第一个，八十八：八十或以上为真，所以 count 变成一。
Second, seventy-four: false, so count stays.
第二个，七十四：为假，count 保持不变。
Third, ninety-five: true, so count becomes two.
第三个，九十五：为真，所以 count 变成二。
Fourth, sixty: false.
第四个，六十：为假。
The loop ends, and the answer displayed is two.
循环结束，显示出来的答案是二。
Two of the four scores were eighty or more.
四个分数里有两个在八十或以上。
Binary search finds a value fast, but it requires the data to be sorted first.
二分搜索能很快找到一个值，但前提是列表已经排好序。
We want seventy-nine.
我们要找七十九。
Check the middle box, number four: it holds forty-one.
先看中间那个盒子，第四号：里面是四十一。
Too small, so the value cannot be in the left half — throw that half away.
它比目标小，所以要找的值不可能在左半边——把那一半扔掉。
Repeat on what is left.
对剩下的部分再来一次。
The new middle is sixty-three, still too small, so drop that half too.
新的中间是六十三，还是太小，那一半也扔掉。
Two boxes remain, and the next middle is seventy-nine.
只剩两个盒子，下一个中间就是七十九。
Found, in three comparisons instead of eight. Each step halves what is left.
找到了，只比较了三次，而不是八次。
A thousand items need about ten steps, a million about twenty.
一千个数据大约十步，一百万个大约二十步。
A procedure — a function — is a named, reusable block of code.
过程是一段有名字的代码，你可以反复调用它。
Calling it runs its code: call it by name, and pass in arguments.
按名字调用它，并传入实参。
Those values land in its parameters; it does its work, and it may return a value.
这些值就落到它的形参里；它做完事，可能返回一个值。
A library is a bundle of ready-made, tested procedures, and its API tells you what each one does — so you can use it without ever seeing inside.
库是一捆做好并测试过的过程，它的 API 会告诉你每一个能做什么—— 这样你不用看它的内部就能用它。
That is procedural abstraction.
这就是过程抽象。
Libraries save time.
库能省时间。
They are collections of ready-made procedures that others can reuse.
它们是别人做好、可以复用的过程的集合。
An API documents what each procedure does, its parameters, and its result, so you can use it without seeing its code.
API 会写明每个过程做什么、 要哪些参数、返回什么，这样你不用看代码就能用。
Build on tested work.
建立在已经测过的工作上。
Name libraries when the question asks how you reuse other people's code.
题目问你怎么复用别人的代码时，要写出库这个词。
Developing your own procedures — deciding what to define — is how you break a big problem into small ones.
自己写过程，就是把一个大问题拆成许多小问题。
Start at the top: manage stock.
从最上面开始：管理库存。
Split it into jobs — record sales, record deliveries, produce reports.
把它拆成几件事——记录销售、记录进货、生成报表。
Then split each job again, into steps small enough to write and test on their own.
再把每件事继续拆下去，拆到每一步都小到可以单独写、单独测试。
Two more ideas.
还有两个概念。
RANDOM returns a random integer, so a program can produce unpredictable results — useful for games, and for sampling.
随机值让程序每次运行的结果都不一样，这在游戏和抽样里很有用。
A simulation models something real, so you can test it cheaply and safely; it often uses randomness to imitate chance events, and it simplifies, so it is only as good as its assumptions.
模拟程序用来模仿真实的事物，让你能便宜又安全地做实验； 但它总要做简化，所以结论好不好，取决于假设好不好。
Most questions are decidable: an algorithm always answers.
大多数问题是可判定的：总有算法能给出答案。
A few are undecidable — no algorithm works for every case.
少数问题是不可判定的——没有任何算法能对每一种情况都有效。
That means impossible, not merely slow.
那是不可能，而不只是慢。
Simulations let you study a real-world process without running it in real life.
模拟让你研究真实世界的过程，却不必真的去做一遍。
They simplify reality — they leave out detail — and they often use randomness to imitate chance events.
它们简化现实——省掉细节—— 并且常常用随机性来模仿偶然事件。
Test what would be too costly, too slow, or too dangerous.
太贵、太慢、或太危险时，就用模拟来试。
The results are only as good as the assumptions.
结果好不好，只取决于假设好不好。
So how good is an algorithm?
那么一个算法到底好不好呢？
Efficiency is how much time it needs as the input grows, so count the steps.
看输入变大时它要走多少步。
Watch what happens when the input doubles.
看看输入翻倍会发生什么。
A constant-time algorithm does the same work.
常数时间的算法工作量不变。
A halving algorithm needs one more step.
每次减半的算法只多走一步。
A linear one does twice as much.
线性的算法工作量翻一倍。
A quadratic one does four times as much.
平方级的算法变成四倍。
Algorithmic efficiency splits in two.
考试把这件事分成两类。
If the work grows like a power of the input size, the algorithm runs in reasonable time.
如果工作量随输入规模按幂次增长，这个算法就是合理时间的。
If it doubles every time you add one more item, it runs in unreasonable time, and it is useless long before the input gets big.
如果每多加一个数据它就翻一倍，那就是不合理时间的， 输入还没变大，它就已经没法用了。
When an exact answer would take too long, use a heuristic instead: a rule of thumb that finds a good-enough answer quickly.
当精确答案要花太久时，就改用启发式方法：一种能快速找到够好答案的经验规则。
Three things that win marks.
三件能拿分的事。
First, read the pseudocode carefully: the left arrow means assignment, and AP lists start at index one, not zero.
第一，仔细读伪代码：左箭头表示赋值，AP 的列表从索引一开始，不是零。
Second, trace code with a table — write every variable down after every line, instead of doing it in your head.
第二，用表格追踪代码——每读完一行，就把每个变量的值写下来，别在脑子里算。
Third, binary search only works on a sorted list, and halving is what makes it fast.
第三，二分搜索只对排好序的列表有效，而每次减半正是它快的原因。