第 2 章 · 选择与迭代

if、while 和 for

程序按顺序一条接一条地执行语句。有两件事会改变这个顺序：选择决定运行哪些语句，迭代让语句重复运行。

图中的程序从 n = 5 开始。只要 n 不是 1，如果它是偶数就把 n 减半，如果是奇数就乘以 3 再加 1，并计一步。顶部的菱形是循环的判断；它下面的菱形是 if 的判断。红色标记是执行点，旁边的代码会点亮正在运行的那一行。

int n = 5; int steps = 0; while (n != 1) { if (n % 2 == 0) { n = n / 2; } else { n = 3 * n + 1; } steps++; } System.out.println(steps);

n 依次为 5, 16, 8, 4, 2, 1。循环条件被检查 6 次：5 次为真，然后一次为假，程序输出 5。

本章是 AP 计算机科学 A 的第 2 单元，占选择题得分的 25–35%：布尔表达式和 if 语句（2.1–2.6），while 和 for 循环（2.7–2.8），由它们构成的标准算法（2.9–2.10），循环中的循环（2.11），以及统计语句运行的次数（2.12）。

2.1 · 含选择和重复的算法

三种基本构件

每个算法都由三样东西构成：顺序（步骤依次进行）、选择（一个判断）和重复（一个循环）。

当算法接下来怎么进行取决于一个真或假的判断时，就发生了选择。重复是一个过程不断重复，直到达到期望的结果。两者都出现在日常的指示中：“如果下雨，就带伞”是选择；“搅拌直到糖溶化”是重复。

算法可以用文字写出，也可以画成流程图：每个步骤一个方框，每个真假判断一个菱形，向上返回的箭头表示重复。图中现在用文字写出同一个算法：“n 是偶数吗？”“减半”“计一步”。代码用 Java 说的是完全相同的事。

步骤的顺序会改变结果。下面两段代码包含相同的语句：

int x = 3; x = x * 2; x = x + 1;

int x = 3; x = x + 1; x = x * 2;

第一段使 x 停在 7；第二段则停在 8。在图中，如果把计步放在循环之后而不是循环里面，无论循环运行多少次，都只会输出 1。

2.2 · 布尔表达式

关系运算符

布尔表达式的值是两个值之一，true 或 false。最简单的是用关系运算符比较两个值。

== 和 != 测试两个值是否相同或不同。<、>、<= 和 >= 比较数字。对于 int、double 和 boolean 这样的基本类型，== 比较的是实际的值。对于引用类型，它比较的是引用：两个变量是否引用同一个对象（2.6）。

图中 a 的值是 7，b 依次取值 4, 7, 9。每次比较产生一个方块，为真时是红色：

= 是赋值；== 是比较。布尔结果可以像其他值一样存储：boolean same = a == b;

2.3 · if 语句

单向选择和双向选择

选择语句改变语句的顺序执行。if 语句根据布尔表达式的值运行不同的代码段。

单向选择（if）有一个代码段，只在条件为真时运行：

if (temp >= 30) { System.out.println("hot"); } System.out.println("done");

temp 为 34 时它输出 hot then done；为 22 时只输出 done。最后一行在 if 之后，所以总会运行。

双向选择（if-else）有两个代码段：条件为真时运行 if 的语句体，条件为假时运行 else 的语句体。恰好运行其中一个。

if (temp >= 30) { System.out.println("hot"); } else { System.out.println("mild"); } System.out.println("done");

图中让两个温度依次通过。在 34 时，标记走真的通道，输出 hot；在 22 时走假的通道，输出 mild。之后两者都输出 done。

2.4 · 多路选择

if、else if、else

多路选择（if-else-if）依次测试一系列条件。第一个为真的条件运行它的代码段，并且最多只运行一个代码段。

if (score >= 90) { grade = "A"; } else if (score >= 80) { grade = "B"; } else if (score >= 70) { grade = "C"; } else { grade = "F"; }

图中让三个分数沿着这条链落下。83 没通过 score >= 90，通过了 score >= 80，被拦住：等级为 "B"。下面的条件根本不会被检查。95 被第一道关 "A" 拦住。64 三个条件都没通过，所以最后的 else 运行："F"。如果没有结尾的 else，一个不满足任何条件的值就不会运行任何代码段。

因为第一个为真的条件胜出，所以顺序很重要。先测试 score >= 70，则 95 得到 "C"：所有 70 或更高的分数都会在第一道关就被拦住。要把要求最高的测试放在最前面。

2.4 · 嵌套 if 语句

if 里面的 if

嵌套 if 语句是指另一个 if、if-else 或 if-else-if 语句内部的 if、if-else 或 if-else-if 语句。

if (age >= 16) { if (hasPermit) { System.out.println("may drive"); } else { System.out.println("needs a permit"); } } System.out.println("done");

内层条件只在外层条件为真时才计算。图中让三个人通过。年龄 17 且有许可证的人两道关都通过，输出 may drive。年龄 17 且没有许可证的人通过外层测试而没通过内层：needs a permit。年龄 14 的人没通过外层测试，所以标记绕过整个方框：hasPermit 根本不会被看到，只输出 done。

花括号决定 else 属于哪个 if。这里 else 在外层花括号之内，所以它与 if (hasPermit) 配对：不满 16 的人根本看不到关于许可证的任何消息。

2.5 · 复合布尔表达式

!、&& 和 ||

逻辑运算符 !（非）、&&（与）和 ||（或）把布尔表达式组合成一个本身也为真或假的表达式。

!a 在 a 为假时为真，否则为假。a && b 只在两者都为真时为真。a || b 在 a 为真、b 为真或两者都为真时为真。图中逐行走过每一种组合：

优先级顺序是先 !，然后 &&，再 ||。所以当 a = false、b = true、c = false 时，表达式 !a || b && c 的意思是 (!a) || (b && c)：true。把它改成 (!a || b) && c 的组合方式则得到 false。括号可以让顺序一目了然。

关系运算符先于逻辑运算符，所以 x > 0 && x < 10 先比较、后组合：对严格介于 0 和 10 之间的每个 x，它都为真。

2.5 · 短路求值

右侧可能永远不会运行

当 && 或 || 的左操作数已经决定了结果时，Java 不会再计算右边的操作数。这就是短路求值。

false && anything 为假，true || anything 为真，无论右侧会是什么。所以右侧被跳过。图中计算两个表达式，先用 x = 4，再用 x = 0：

x != 0 && 10 / x > 2 x == 0 || 10 / x > 2

当 x = 4 时，两个表达式的两侧都会运行。10 / 4 是 2（整数除法），不大于 2，所以第一个是 false，第二个也是。

当 x = 0 时，x != 0 为假，所以第一个立刻为 false；x == 0 为真，所以第二个立刻为 true。两个表达式中 10 / x 都不会运行，这正好：用零去除 int 会抛出 ArithmeticException。

这使左操作数成为一道防护。反过来写，10 / x > 2 && x != 0 会先做除法，当 x 为 0 时就会崩溃。

2.6 · 等价的布尔表达式

真值表和德摩根定律

如果两个布尔表达式在所有情况下的值都相同，它们就是等价的。真值表（每种输入组合一行）可以证明这一点。

德摩根定律给出两个等价关系：

!(a && b) 等价于 !a || !b !(a || b) 等价于 !a && !b

要把 ! 推进括号内，需要对每个部分取反，并把 && 换成 ||，或把 || 换成 &&。图中第二个表达式的每一列滑到第一个表达式上：每一行的颜色都相同。

忘了交换运算符就不成立了：!(a && b) 和 !a && !b 在 4 行中有 2 行不同。对比较取反要翻转运算符：!(x > 5) 就是 x <= 5。所以 !(x >= 1 && x <= 10) 等价于 x < 1 || x > 10。

2.6 · 比较对象

== 与 equals 的对比

两个不同的变量可以保存对同一个对象的引用。对引用使用 == 和 !=，问的是它们是否引用同一个对象，而不是两个对象的内容是否相同。

String s1 = new String("atlas"); String s2 = s1; String s3 = new String("atlas"); String s4 = null;

s2 = s1 复制了引用，所以 s1 和 s2 指向同一个对象：s1 == s2 为 true。s3 引用第二个对象，字母相同：s1 == s3 为 false。

类通常定义一个 equals 方法，说明什么时候两个对象算相等，通常通过比较它们的属性。细绳 的版本比较各个字符，所以 s1.equals(s3) 是 true。比较字符串要用 equals，永远不要用 ==。

引用可以用 == 或 != 与 null 比较，以判断它是否引用了某个对象：s4 == null 为 true。（重写 equals 方法不在课程范围内。）

2.7 · while 循环

检查、运行、再检查

迭代是重复的一种形式：迭代语句在布尔表达式为真期间，把一个代码段重复运行零次或多次。

在 while 循环中，布尔表达式在每次执行循环体之前计算，包括第一次。为真时循环体运行；为假时循环结束，程序继续执行循环之后的内容。

int sum = 0; int k = 1; while (k <= 4) { sum += k; k++; } System.out.println(sum);

追踪表在每次检查条件时记录各个变量。图中逐行填写它：

条件被检查 5 次，循环体运行 4 次：最后一次检查是为假的那一次。循环以 k = 5 结束，输出 10。

2.7 · 出错的循环

从不运行、永不停止、少一次

大多数循环错误是这三种之一：循环从不运行，永不停止，或者多运行一次或少运行一次。

如果布尔表达式第一次就为假，循环体永远不会执行。k 为 10 时的 while (k < 5) 只检查一次就继续往下走（顶行）。

当布尔表达式始终为真时，就发生无限循环。在中间一行，k 依次为 1, 3, 5, 7, 9、……，永远不会是 6，所以 while (k != 6) 永远不会变为假。循环体从不改变其条件中的变量的循环，也是如此。

差一错误是指循环多运行一次或少运行一次。本应输出 1 到 5，最下面的循环却输出了 1234：while (k < 5) 在 5 之前就停了。k <= 5 可以修正它。

int k = 1; while (k < 5) { System.out.print(k); k++; }

检查循环的边界：第一遍、最后一遍，以及使它结束的那次检查。

2.8 · for 循环

初始化、布尔表达式、更新

for 循环把计数循环的三个部分放在头部：初始化、布尔表达式和更新。

for (int i = 0; i < 3; i++) { System.out.println(i); }

初始化只运行一次，在第一次检查之前。它设置的变量就是循环控制变量。布尔表达式在初始化之后立刻计算，之后每次更新后再计算，直到它为假。每一遍中，更新在整个循环体之后、下一次检查之前运行。

图中的标记依次经过 初始化 → 检查 → 循环体 → 更新 → 检查 ……。每个站点下的计数：初始化 1，检查 4，循环体 3，更新 3。它输出 0, 1, 2，每个独占一行。

for 循环可以改写成等价的 while 循环，反之亦然：

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

有一点不同：在 for 头部声明的 i 只存在于循环内部；在 while 循环之前声明的，之后仍然存在。

2.9 · 数位与整除

% 10、/ 10 和 % k

有两种标准算法用到取余运算符：逐位拆分一个整数，以及测试一个整数能否被另一个整数整除。

对于正的 int n，n % 10 是它的最后一位数字，n / 10（整数除法）是去掉那一位数字后的 n。重复，直到 n 为 0：

int n = 3725; int sum = 0; int max = 0; int odd = 0; while (n > 0) { int d = n % 10; sum += d; if (d > max) { max = d; } if (d % 2 == 1) { odd++; } n /= 10; }

图中把 3725 的各位数字从右边一个个剥下来，5, 2, 7, 3，每一位都经过 d。

a % b == 0 为真，恰好当 a 能被 b 整除。3725 % 5 是 0，所以 3725 能被 5 整除；3725 % 3 是 2，所以它不能被 3 整除。用 2 做同样的测试可以区分偶数和奇数，就像循环中的 d % 2 == 1 那样。

2.9 · 求和、平均值、极值和计数

随循环运行不断累积

另外三种标准算法，会在循环之前声明一个变量来保存运行中的值，并在循环内部更新它：求和、求最小值或最大值，以及计数。

求和从 0 开始，逐个加上每个值：sum += d。对于 3725，sum 最终为 17。

平均值是总和除以值的个数。注意整数除法：

double avg = (double) sum / 4; int avgInt = sum / 4;

avg 是 4.25；avgInt 是 4，小数部分被丢掉了。要先类型转换再除，不要先除再转换。

最大值保存到目前为止最大的值，每当遇到更大的值就替换它：if (d > max)。这里 max 最终为 7。可以让它从第一个值开始，或者从一个真实值不可能小于的值开始：0 之所以可行，只是因为数位永远不是负数；一般情况下请使用 Integer.MIN_VALUE。最小值则是镜像：从 Integer.MAX_VALUE 开始，测试 <；最小的数位是 2。

统计满足某条件的次数的计数从 0 开始，在 if 内部加 1：if (d % 2 == 1) 统计奇数数位，共 3 个。

2.10 · 字符串算法

反转并统计子字符串

字符串算法沿着字符串移动一个索引，在每个位置取一个子字符串：用来构建新字符串，或测试、统计具有某种性质的子字符串。

要反转字符串，把每个字符放到目前已构建内容的前面。substring(i, i + 1) 是索引 i 处的那个字符：

String word = "drawer"; String rev = ""; for (int i = 0; i < word.length(); i++) { rev = word.substring(i, i + 1) + rev; }

rev 逐步增长："d", "rd", "ard", "ward", "eward", "reward"。（rev = rev + word.substring(i, i + 1) 会原样复制该单词。）

要统计满足某条件的子字符串个数，让窗口沿字符串滑动并逐个测试：

String s = "banana"; int count = 0; for (int i = 0; i < s.length() - 1; i++) { if (s.substring(i, i + 2).equals("an")) { count++; } }

窗口 substring(i, i + 2) 查看 "ba", "an", "na", "an", "na"，匹配的是：2，所以 count 是 2。最后一个窗口从索引 4 开始，所以 i 必须在 s.length() - 1 之前停止；再多走一步，substring(5, 7) 就会越过末尾并抛出 StringIndexOutOfBoundsException。

用 equals 比较子字符串。要判断是否存在具有该性质的子字符串，同样的循环可以在找到第一个时就停止，或者用 indexOf 返回给定子字符串第一次出现的位置，若没有则返回 −1。

2.11 · 嵌套迭代

循环中的循环

嵌套迭代是指一个循环位于另一个循环的循环体中。内层循环会先执行完它的全部迭代，外层循环才进入下一次。

for (int r = 0; r < 3; r++) { for (int c = 0; c < 4; c++) { System.out.print(r * c + " "); } System.out.println(); }

对于 r = 0，内层循环让 c 从 0 取到 3；然后 println 结束这一行，之后 r 才变为 1。图中逐格、逐行点亮网格：内层循环体运行 3 × 4 = 12 次，并输出

0 0 0 0 0 1 2 3 0 2 4 6

内层循环的边界可以依赖外层变量。这里内层循环运行 r + 1 次，所以各趟分别是 1, 2, 3, 4：

int count = 0; for (int r = 0; r < 4; r++) { for (int c = 0; c <= r; c++) { count++; } }

count 最终为 10，得到的是三角形而不是矩形。

2.12 · 非正式运行时分析

数一条语句运行了多少次

语句执行次数是一条语句运行的次数。通常通过追踪几趟并分析循环，非正式地求出。

for (int i = 0; i < n; i++) { count++; }

i 从 0 取到 n − 1 时，count++ 运行 n 次。检查 i < n 运行 n + 1 次：多一次，用来结束循环。

for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { count++; } }

嵌套时，n 趟外层循环各自运行内层循环 n 次：count++ 运行 n × n 次。对于 n = 6，是 6 对比 36；对于 n = 8，是 8 对比 64。随着 n 增大，图中两者都在增长：n 加倍时，一个加倍，另一个变为四倍。

根据循环边界来数。for (int i = 1; i <= n; i++) 也运行 n 次；i < n 从 1 开始则运行 n − 1 次；像上一页那样的三角形运行 1 + 2 + … + n 次。比较这类次数，就是不用秒表也能说明一个循环比另一个快的方法。