Selection and Iteration
AP Computer Science A Topic 2 7:59 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Here are three loops. They differ by one character each — a less-than instead of a less-than-or-equal, a greater-than instead of a less-than.
这里有三个循环，彼此只差一个字符——小于换成小于等于， 或者小于换成大于。
The first runs ten times. The second runs eleven. And the third never stops at all: it will sit there burning your processor until you kill it.
第一个循环运行十次，第二个运行十一次， 而第三个根本停不下来：它会一直耗着你的处理器，直到你强行结束它。
One character.
就差一个字符。
Getting loop conditions exactly right is most of what this unit is about.
把循环条件写得分毫不差，正是这一单元的核心。
Welcome to Unit Two.
欢迎来到第二单元。
Algorithms are built from three control structures: sequence, steps in order; selection, which lets a program choose; and iteration, which lets it repeat.
算法由三种控制结构构成：顺序，也就是按次序执行的步骤； 选择，让程序会"做决定"；以及迭代，让程序会"重复"。
Sequence you already write without thinking.
顺序你早已不假思索地在写。
The other two both rest on one thing: an expression that is either true or false.
另外两种都建立在同一样东西之上： 一个非真即假的表达式。
Let's begin there.
我们就从这里开始。
A boolean expression evaluates to exactly one of two values: true or false.
布尔表达式的取值只有两个：真或假。
Six relational operators produce them. Less than, greater than, less than or equal, greater than or equal, double-equals for "is equal to", and exclamation-equals for "is not equal to". Now the classic beginner error.
有六个关系运算符能产生它们： 小于、大于、小于等于、大于等于、双等号表示"等于"， 以及感叹号等号表示"不等于"。
One equals sign assigns a value. Two equals signs compare. They are completely different operators.
现在说那个初学者的经典错误： 一个等号是赋值，两个等号是比较，它们是完全不同的运算符。
And one more, which the exam tests every year: with Strings you must use dot-equals, not double-equals.
还有一点，考试每年都考：比较字符串必须用点 equals，而不是双等号。
Double-equals on objects compares references — whether they are the same object — not the text inside.
双等号作用在对象上比较的是引用——是不是同一个对象—— 而不是里面的文字内容。
The if statement runs a block only when its condition is true.
if 语句只在条件为真时执行代码块。
Add else, and you get the other path when it is false.
加上 else，条件为假时就走另一条路。
Chain them with else if, and Java tests each condition in turn and takes the first one that is true — then skips every remaining branch.
用 else if 把它们串起来，Java 会依次检查每个条件， 取第一个为真的分支——然后跳过后面所有分支。
Which means the order matters enormously. Put a wide condition first and the narrow ones below it can never run.
因此顺序极其重要：如果把范围宽的条件放在前面， 下面范围窄的条件就永远轮不到。
Test the most specific case first, and the most general case last.
要把最具体的情况放在最前，最一般的放在最后。
Three logical operators combine conditions.
有三个逻辑运算符可以组合条件。
Double-ampersand means AND: true only when both sides are true.
双与号表示"与"：两边都为真时才为真。
Double-pipe means OR: true when at least one side is true.
双竖线表示"或"：至少一边为真就为真。
And exclamation mark means NOT: it flips the value.
感叹号表示"非"：它把值取反。
Learn the truth table until it is automatic.
真值表要背到条件反射。
Then there is one rule that turns up constantly — De Morgan's laws. NOT of A and B is the same as NOT A or NOT B. NOT of A or B is the same as NOT A and NOT B.
还有一条经常出现的规则——德摩根定律： "A 且 B"的否定，等于"非 A 或非 B"；"A 或 B"的否定，等于"非 A 且非 B"。
Push the NOT inwards, and flip the operator as you go.
把否定往里推，同时把运算符翻过来。
Java also evaluates these lazily, and that is not just an optimisation — it changes what your code can safely do.
Java 还会"惰性"地求值，这不只是优化——它改变了你的代码能安全做什么。
With double-ampersand, if the left side is already false, the whole thing must be false, so Java never even looks at the right side.
对于双与号，如果左边已经为假，整体必然为假，所以 Java 根本不去看右边。
With double-pipe, if the left side is true, it skips the right side.
对于双竖线，如果左边为真，就跳过右边。
This is short-circuit evaluation, and you use it deliberately: test that a reference is not null on the left, and only then use it on the right.
这叫短路求值， 而你要有意识地利用它：先在左边判断引用不为空，然后才在右边使用它。
Now repetition.
现在讲重复。
Every loop needs three things: something to initialise the counter, a condition to keep going, and an update that moves the counter along.
每个循环都需要三样东西：初始化计数器、继续执行的条件， 以及让计数器前进的更新语句。
A while loop checks the condition before each pass, so if the condition is false at the very start, the body never runs even once.
while 循环在每一轮之前检查条件， 所以如果一开始条件就为假，循环体一次都不会执行。
And here is how you hang your program: forget the update.
而让程序卡死的方法就是：忘了写更新语句。
If nothing inside the loop can ever make the condition false, it is an infinite loop.
如果循环里没有任何东西能让条件变成假，那就是死循环。
The for loop puts all three parts into one header: initialise, condition, update, separated by semicolons.
for 循环把三个部分都放进一个头部：初始化、条件、更新，用分号分隔。
It is an equivalent loop to the while version — just written where you can see all three parts at once, which makes it much harder to forget the update.
它和 while 版本是完全相同的循环——只是写成一眼能看到三个部分的形式， 这样就很难忘掉更新语句。
Use a for loop when you know how many passes you need, and a while loop when you do not.
当你知道要循环多少次时用 for，不知道时用 while。
Two integer patterns the exam tests directly: to read the digits of an integer, take n modulo ten for the last digit and divide by ten to drop it; and for divisibility, n modulo d equals zero.
考试直接考查的两个整数套路：要取出整数的各位数字， 用 n 对十取模得到最后一位，再除以十把它去掉； 判断整除则看 n 对 d 取模是否等于零。
Add a counter and you find the frequency of anything you can test.
再加一个计数器，你就能统计任何可以判断的事情出现了多少次。
A flag — a boolean that records whether something happened — is the other pattern worth knowing.
另一个值得掌握的套路是标志位——一个布尔变量，用来记录某件事有没有发生过。
And to count the passes: starting at zero with a less-than condition runs exactly that many times.
至于次数：从零开始、用小于作条件，就正好循环那么多次。
Loops and Strings go together constantly.
循环和字符串总是配合出现。
Four String methods carry most of the work. Length gives the number of characters. Substring pulls out a piece.
四个 String 方法承担了大部分工作： length 给出字符个数；substring 取出一段；indexOf 找出某内容出现的位置， 找不到就返回负一；charAt 取出一个字符。
IndexOf finds where something appears, or returns minus one if it does not. And charAt gives you one character. All of them start counting at zero, and substring includes the start position but excludes the end position — that off-by-one is the most common String bug there is.
它们全都从零开始计数，而且 substring 包含起始位置、不包含结束位置—— 这个差一错误是最常见的字符串 bug。
To walk through every character, run a for loop from zero while the counter is less than the length.
要遍历每个字符， 就用 for 循环从零开始，条件是计数器小于长度。
Put a loop inside a loop and you get nested iteration.
把一个循环放进另一个循环里，就得到嵌套迭代。
For every single pass of the outer loop, the inner loop runs completely, from start to finish.
外层循环每走一轮，内层循环就完整地从头跑到尾。
So if the outer loop runs three times and the inner loop runs four, the inner body runs twelve times in total — three times four.
所以如果外层循环三次、内层循环四次，内层循环体总共执行十二次——三乘四。
The usual mental model is rows and columns: the outer loop picks the row, the inner loop walks across it.
通常的思维模型是行与列：外层循环选定行，内层循环沿着这一行走过去。
Which leads to informal run-time analysis.
这就引出了非正式的运行时间分析。
You are not asked for formal big-O notation here — you are asked to count how many times a statement executes.
这里不要求你写正式的大 O 记号—— 要求你数出某条语句执行了多少次。
A single loop over n items runs its body n times — that is linear.
对 n 个元素的单层循环，循环体执行 n 次。
A nested loop over the same n items runs its body n times n — quadratic — so doubling the data makes it four times slower.
对同样 n 个元素的嵌套循环，循环体执行 n 乘 n 次， 所以数据翻倍会让它慢四倍。
That is why nesting loops carelessly is expensive, and why noticing the nesting is worth marks.
这就是随意嵌套循环代价高昂的原因， 也是看出嵌套能拿分的原因。
But multiplying is only right when the inner bound is a fixed number.
但只有当内层的上界是一个固定的数时，相乘才是正确的。
Look at this loop: the inner condition is j less than i, so the inner bound is the OUTER variable, and the inner loop gets longer every pass.
看这个循环：内层条件是 j 小于 i， 所以内层的上界是外层变量，内层循环每一轮都变得更长。
So go row by row.
所以要一行一行地数。
When i is zero, j starts at zero and is already not less than zero, so the inner loop runs zero times and prints nothing.
当 i 等于零时， j 从零开始，已经不小于零了，所以内层循环运行零次，什么也不打印。
When i is one, it runs once.
当 i 等于一时，运行一次。
When i is two, twice.
i 等于二时，两次。
When i is three, three times.
i 等于三时，三次。
Add them: zero plus one plus two plus three, which is six stars.
把它们加起来：零加一加二加三，等于六个星号。
And here is the trap the exam sets: the outer loop runs four times and the inner bound reaches four, so the careless answer is four times four, sixteen.
考试设下 的陷阱就在这里：外层循环运行四次，内层上界也达到四，所以粗心的答案是四乘四，十六。
It is not sixteen.
它不是 十六。
Sixteen is the rectangular case, where the inner bound is fixed.
十六是矩形的情形，那是内层上界固定的时候。
This is the triangular sum: zero up to n minus one, which is n times n minus one, all over two.
这个是三角求和：从零加到 n 减一，等于 n 乘以 n 减一，再除以二。
Four times three over two is six.
四乘三除以二等于六。
So before you multiply, check what the inner loop is counting up to.
所以在相乘之前，先看清楚内层循环数到哪里。
Three marks students throw away.
三个学生常丢的分。
First, compare Strings with dot-equals, never with double-equals — double-equals asks whether they are the same object.
第一，比较字符串要用点 equals，绝不能用双等号—— 双等号问的是"是不是同一个对象"。
Second, check the loop bounds by hand: start at zero with a less-than condition, and trace the first and last pass before you trust it.
第二，循环边界要手算： 从零开始、用小于作条件，并在相信它之前先把第一轮和最后一轮走一遍。
Third, a nested loop multiplies the work — but only when the inner bound is fixed.
第三，嵌套循环是相乘——但只有当内层上界固定时才如此。
If the inner bound is the outer variable, add the rows up instead.
如果内层上界是外层变量，就要逐行相加。