第2章 · 選擇與迭代

if、while 和 for

程式會依序一個接一個執行它的敘述。有兩件事會改變這個順序：選擇決定哪些敘述執行，迭代讓敘述再執行一次。

圖中的程式從 n = 5 開始。只要 n 不是 1，若它是偶數就把 n 減半，若是奇數就乘以三再加 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 次為 true，最後一次為 false，程式印出 5。

本章是 AP Computer Science 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。每個比較產生一個方塊，true 為紅色：

= 是指派；== 是比較。布林結果可以像其他值一樣儲存：boolean same = a == b;

2.3 · if 敘述

單向與雙向選擇

選擇敘述會改變敘述的循序執行。if 敘述依布林運算式的值，執行不同的程式碼片段。

單向選擇（if）只有一個片段，只在條件為 true 時執行：

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

當 temp 為 34 時印出 hot then done；為 22 時，只印出 done。最後一行在 if 之後，所以一定會執行。

雙向選擇（if-else）有兩個片段：條件為 true 時執行 if 的主體，為 false 時執行 else 的主體。兩者恰好執行其一。

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

圖中讓兩個溫度走過它。在 34 時，代幣走 true 的車道並印出 hot；在 22 時走 false 的車道，印出 mild。之後兩者都印出 done。

2.4 · 多向選擇

if、else if、else

多向選擇（if-else-if）依序測試一連串條件。第一個為 true 的條件執行它的片段，而且最多只有一個片段會執行。

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，沒通過任何條件的值就一個片段也不執行。

因為第一個為 true 的條件勝出，所以順序很重要。先測試 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");

內層條件只有在外層為 true 時才會求值。圖中讓三個人走過。年齡 17 且有許可證的人兩關都通過，印出 may drive。年齡 17 但沒有許可證的人通過外層測試、卻沒通過內層：needs a permit。年齡 14 的人沒通過外層測試，所以代幣繞過整個方框：hasPermit 根本不會被看到，只印出 done。

大括號決定 else 屬於哪個 if。這裡 else 在外層大括號裡，所以它與 if (hasPermit) 配對：未滿 16 的人完全不會得到關於許可證的訊息。

2.5 · 複合布林運算式

!、&& 與 ||

邏輯運算子 !（非）、&&（且）和 ||（或）把布林運算式組合成另一個本身也是 true 或 false 的運算式。

!a 在 a 為 false 時為 true，否則為 false。a && b 只有在兩者都為 true 時才為 true。a || b 在 a 為 true、b 為 true，或兩者皆為 true 時為 true。圖中一列一列地走過每一種組合：

優先順序是先 !，再 &&，最後 ||。所以當 a = false、b = true、c = false 時，運算式 !a || b && c 的意思是 (!a) || (b && c)：true。如果改成 (!a || b) && c 的分組，則得到 false。括號能讓順序清楚明白。

關係運算子先於邏輯運算子，所以 x > 0 && x < 10 先比較再組合：對嚴格介於 0 和 10 之間的每個 x 都為 true。

2.5 · 短路求值

右側可能根本不會執行

當 && 或 || 的左運算元已經決定了結果，Java 就不會對右邊求值。這就是短路求值。

false && anything 是 false，true || anything 是 true，不論右側會說什麼。所以右側被略過。圖中對兩個運算式求值，先用 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，所以第一個立刻就是 false；而 x == 0 是 true，所以第二個立刻就是 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 迴圈

檢查、執行、再檢查

迭代是一種重複：迭代敘述只要它的布林運算式為 true，就把一段程式碼重複零次或多次。

在 while 迴圈中，布林運算式在每次進入主體之前求值，包括第一次。為 true 時主體執行；為 false 時迴圈結束，程式接著執行迴圈之後的內容。

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

追蹤表在每次檢查條件時記錄各變數。圖中一列一列地把它填起來：

條件被檢查了 5 次，主體執行了 4 次：最後一次檢查是結果為 false 的那次。迴圈結束時是 k = 5，並印出 10。

2.7 · 出問題的迴圈

從不執行、永遠不停、差一次

多數迴圈的程式錯誤屬於三種之一：迴圈從不執行、永遠不停，或多執行或少執行一次。

如果布林運算式第一次就是 false，主體就永遠不會執行。while (k < 5) 且 k 為 10 時，只檢查一次就往下繼續（最上面一列）。

無窮迴圈發生在布林運算式永遠求值為 true 的時候。在中間那一列，k 依序為 1, 3, 5, 7, 9、…，永遠不會是 6，所以 while (k != 6) 永遠不會變成 false。迴圈主體從不改變條件中的變數，也會造成同樣的結果。

差一錯誤是迴圈多執行一次或少執行一次。本來要印出 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); }

初始化在第一次檢查之前只執行一次。它設定的變數是迴圈控制變數。布林運算式在初始化之後立刻求值，之後每次更新後再求值，直到為 false。每一輪中，更新在整個主體之後、下一次檢查之前執行。

圖中的代幣依序經過 初始化 → 檢查 → 主體 → 更新 → 檢查……。每個站下面的計數：初始化 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 整除時為 true。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 次。比較這類次數，就是不用碼表也能說出一個迴圈比另一個快的方法。