选择与迭代

算法由三种控制结构(control structures)构建:顺序(sequence)(按顺序的步骤)、选择(selection)(选择一条路径),和迭代(iteration)(重复步骤)。这个主题涵盖选择和迭代——让一个程序做决定和循环的工具。

一个布尔表达式(boolean expression)求值为 true 或 false,用关系运算符(relational operators):==(相等)、!=(不相等)、<、>、<=、>=。注意 == 比较基本值但对对象比较对象引用,所以对 String 用 .equals。

一个条件语句(if statement)只在它的条件为真时运行一个块;一个可选的 else 给出一个替代:

if (score >= 60) {
    System.out.println("Pass");
} else {
    System.out.println("Fail");
}

把一个 if 放进另一个里面,或用 else if 链接,按顺序测试几个情况。只有第一个匹配的分支运行:

if (g >= 90) grade = 'A';
else if (g >= 80) grade = 'B';
else grade = 'C';

逻辑运算符(logical operators)组合条件:&&(与——两者都真)、||(或——至少一个真)、!(非——反转)。Java 用短路求值(short-circuit evaluation):&& 若左侧为假则停止,而 || 若左侧为真则停止——对防止错误有用,例如 if (n != 0 && total / n > 5)。

德摩根定律(De Morgan's laws)重写否定:!(a && b) 等于 !a || !b,而 !(a || b) 等于 !a && !b。两个布尔表达式等价,若它们对每个输入给出相同的结果——一张真值表证明它。以这种方式化简条件是一个常见的考试任务。

一个循环(while loop)在它的条件保持为真时当……时重复,在每一趟之前测试。你必须在里面改变某样东西以便循环最终停止,否则它变成一个无限循环(infinite loop):

int i = 0;
while (i < 5) {
    System.out.println(i);
    i++;
}

一个 for 循环(for loop)把初始化、条件和更新打包进一行——当你知道次数时最好:

for (int i = 0; i < n; i++) {
    // runs n times, i = 0..n-1
}

一个 for 和一个等价的 while 做相同的工作;能够在它们之间转换。

组合循环和条件来解决真实的问题——计数、求和、找一个最大值,或测试一个性质:

int max = arr[0];
for (int k = 1; k < arr.length; k++) {
    if (arr[k] > max) max = arr[k];
}

有两个整数模式,考试会直接考,它们用 % 和 /。要一次一个地读出一个整数的各位数字,反复取 n % 10(最后一位)然后 n = n / 10(把它去掉)。要测试整除性,n % d == 0 表示 n 能被 d 整除。把它们和一个计数器结合起来,就能求出某个标准被满足的频率。

像一个连续总计、一个计数器,或一个标志(flag)(一个记录某事是否发生的布尔值)这样的标准模式贯穿整个课程重现。

按索引循环遍历一个字符串以处理每个字符:

for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // count vowels, reverse, check for a substring, ...
}

典型的任务:计数出现、构建一个反转或过滤的副本,或测试一个字符串是否包含另一个。

一个嵌套循环(nested loop)把一个循环放进另一个里面;内层循环对外层的每一趟完全完成。若外层运行 $n$ 次而内层 $m$ 次,主体运行 $n\times m$ 次——处理网格和比较所有对的基础。

运行时间分析(run-time analysis)数一个算法随着输入大小 $n$ 增长取多少基本步骤。数最内层语句的执行:一个遍历 $n$ 个项的单一循环是线性的($n$ 步);两个遍历 $n$ 的嵌套循环是二次的($n^2$)。这种非正式的计数让你能比较两个算法的效率。

考试技能: 对于一个嵌套循环,能够以循环边界陈述内层语句运行多少次——一个频繁的选择题。

Worked example. 这个打印多少个星?

for (int i = 0; i < 4; i++)
    for (int j = 0; j < i; j++)
        System.out.print("*");

内层循环对每个外层 i 运行 i 次:0 + 1 + 2 + 3 = 6 个星。当内层边界是外层变量时,总数是三角和 $0+1+\dots+(n-1)=\dfrac{n(n-1)}{2}$ ——这里 $\dfrac{4\times3}{2}=6$ ——不是一个矩形嵌套循环的完整 $n^2=16$。

• 把边界条件搞对:有意地用 < vs <=,并注意每个循环的第一次和最后一次迭代(差一是经典的 bug)。
• 用 &&、||、! 构建复合条件并记住短路求值(把 null 检查放在先)。
• 通过数内层主体总共运行多少次来跟踪嵌套循环。
• 选择正确的结构——if/else if 用于范围、一个循环用于重复——并通过更新循环变量避免一个无限循环。
• 当你化简或否定一个布尔条件时应用德摩根定律。