無痛入手 C++：基礎教學6 - 迴圈
迴圈 (loop) 是用來重複執行相同或相似行為的語法。
for 迴圈
基本架構
for 是最常被使用的迴圈語法，基本的架構如下:
// single statement
for (初始式; 判斷式; 運算式)
陳述;
// multiple statements
for (初始式; 判斷式; 運算式) {
陳述1;
陳述2;
陳述3;
...
}
電腦遇到 for 的時候，會執行下列的流程:
1. 執行一次初始式 (通常包含變數的宣告與初始化)。
2. 如果判斷式的結果為真就執行陳述，為假的話則跳出 for 迴圈並繼續向下執行。
3. 若判斷式的結果為真，在執行完所有陳述以後，執行一次運算式，然後回到 2.。
下面的程式會讀入一個整數 x，並重複列印相同的文字 x 次:
int x = 0;
cin >> x;
for (int i = 0; i < x; ++i)
cout << "This is a statement in for loop\n";
我們用這個例子說明剛剛提到的流程。假設使用者輸入 2，當電腦遇到上面的 for 時:
1. 執行 int i = 0; 。注意: 因為 int i 式宣告在 for 迴圈的小括號內，因此只有在這個 for 迴圈內可以使用，在這個 for 以外使用該變數 i 是不合法的行為。
2. 檢查判斷式 i < x; 是否為真。因為 0 < 2，判斷式為真，所以電腦會執行 for 中的陳述: cout << "This is a statement in for loop\n";。
3. 執行完陳述以後，電腦會執行一次 ++i，所以變數 i 的值會從 0 變成 1，接著電腦便會回到 2. 重新進行判斷。
按照上述的邏輯，電腦會在第三次檢查 i < x; 的時候發現結果為假: 2 < 2，於是跳出 for 迴圈。因此在這個例子中，cout << "This is a statement in for loop\n"; 會被執行兩次。
注意1: 將 int i 初始化為 1 並調整一下判斷式，如: for (int i = 1; i <= x; ++i)，也可以得到相同的結果 (why?)。不過在程式的世界裡，我們習慣用 0 當作開始，而不是 1，原因之後有機會再分享。
注意2: 在這個例子中，++i 跟 i++ 會得到相同的結果，事實上也可以寫成 i = i + 1。重點在於將 i 的值增加 1，只要能做到這點就可以。
注意3: 假如使用者輸入負數或 0 的話，判斷式在一開始就為假，所以電腦連一次陳述都不會執行。
在陳述中使用 induction variable
在上述的例子當中 int i 稱為 induction variable (我不知道中文怎麼翻QQ)。可以在 for 的陳述中使用 induction variable 來做到更複雜的事情。
下面的程式會讀入一個整數，並印出所有小於或等於該數的正整數:
int x = 0;
cin >> x;
for (int i = 1; i <= x; ++i)
cout << i << '\n';
因為我們要印出正整數，所以將 int i 初始化為 1，其他的部分就跟上個例子是相同的概念。
也就是說，for 不僅能重複執行相同的陳述，我們還能使用 induction variable 在每次的迴圈 (iteration) 中給予陳述不同的數值。事實上，大部分的問題都需要在陳述中使用 induction variable。
int i 就跟宣告一般的變數一樣，只要符合命名規範，變數名稱可以隨便取。i 只是一個簡單的代稱用來表示 induction variable (應該啦，我猜的)。懶惰的程式設計師們也經常使用: j, k, n, m 來命名。
更多範例
為了幫助大家熟悉 for 的使用方式，以下是更多的範例。
1. 由小到大印出所有大於等於 0 且小於等於 x 的偶數:
for (int i = 0; i <= x; i += 2)
cout << i << '\n';
- 由小到大印出所有小於 x 且為 2 的次方數的整數:
for (int i = 1; i < x; i *= 2)
cout << i << '\n';
- 由小到大印出所有平方數小於 x 的正整數:
for (int i = 1; i * i < x; ++i)
cout << i << '\n';
- 由大到小印出所有小於 x 的正整數 i，且 x + i 為 3 的倍數:
for (int i = x - 1; i > 0; --i) {
// if statement
if ((x + i) % 3 == 0)
cout << i << '\n';
}
巢狀迴圈
for 本身也是陳述的一種，所以 for 的陳述也可以包含另一個 for，這個結構稱為巢狀 (跟巢狀條件判斷的概念是一樣的)。以下的程式會依序把兩個 for 迴圈的 induction variable 印出來，猜猜看會印出什麼樣的結果:
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 5; ++j)
cout << i << " " << j << '\n';
}
在外層 for 的每次迴圈 (iteration) 中，內層 for 的 j 都會從 0 加到 4，接著就會回到外層 for 進行運算式 ++i 和條件判斷 i < 3，若結果為真的話就再執行一次內層的 for。依此類推，會印出 0~2 和 0~4 的所有排列組合:
0 0
0 1
0 2
0 3
0 4
1 0
1 1
1 2
1 3
1 4
2 0
2 1
2 2
2 3
2 4
注意: induction variable 就跟一般的變數一樣，差別在於宣告在 for 的小括號內的時候，只有這個 for 裡面的陳述能使用 (所以上述程式的內層 for 能夠使用上層 for 的 i)。如果不小心把內層 for 的 induction variable 也取名叫 i，就會把外層 for 的 i 覆蓋掉 (詳細說明請看下一篇文章)。
我們也可以利用外層 for 的 induction variable 來設定內層 for 的判斷式，舉例來說，以下的程式會用 * 印出邊長為 n 的直角三角形:
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j)
cout << '*';
cout << '\n';
}
上述程式的邏輯是這樣的:
1. 外層 for 的每次迴圈都會印出一列 *，所以在迴圈結束的時候 (第 4 行) 要換行。
2. 內層 for 會決定每一列要印幾個 *。因為第 i 列需要印出 i + 1 個 *，而且 i 介於 0~(n - 1)，因此我們將 j 設定為 0~i，因為 i - 0 + 1 = i + 1。
以下的程式會用類似的邏輯，印出倒過來的直角三角形:
for (int i = 0; i < n; ++i) {
for (int j = n - 1; j >= i; --j)
cout << '*';
cout << '\n';
}
我們只修改了內層迴圈: 在這個例子中，第 i 列需要印出 n - i 個 *，而且 i 介於 0~(n-1)，因此我們將 j 設定為 (n - 1)~i 的遞減形式，因為 (n - 1) - i + 1 = n - i。
觀察上面兩個直角三角形的例子，可以發現設計 for 迴圈的步驟大致是:
1. 依照問題設計每層 for 要做到的事情。
2. 將要做的事情定義成公式 (有必要的話可以使用 induction variable 和其他變數)。
3. 設計 for 的初始式、判斷式、運算式來滿足 2. 定義的公式。
continue 和 break
for 中可以使用 continue 和 break 這兩個特殊的陳述。
continue:
電腦執行到 continue 後會忽略後面尚未執行的陳述，直接跳至下一個迴圈，重新進行條件判斷。下面的程式會印出所有介於 0 ~ n 之間的偶數，提供了兩種寫法做比較: 1. 利用條件判斷印出偶數和 2. 利用 continue 跳過奇數不印。
// method 1
for (int i = 0; i <= n; ++i) {
if (i % 2 == 0)
cout << i << '\n';
}
// method 2
for (int i = 0; i <= n; ++i) {
if (i % 2 == 1)
continue;
cout << i << '\n';
}
break:
電腦執行到 break 後會立即跳出目前所在的 for。下面的程式讓使用者輸入 N 個數字，如果使用者輸入偶數，它會印出該數字然後停止執行:
// input 10 numbers
for (int i = 0; i < 10; ++i) {
int num;
cin >> num;
if (num % 2 == 0) {
cout << num << " is even!";
break;
}
}
假如沒有 break 的話，電腦會把後續使用者輸入的偶數全部印出來。
注意: 上述的 if 有超過一個陳述，所以要用大括號包起來，否則電腦會認為 break 在 if 外面，導致 for 在第一個迴圈就會因為 break 的關係跳出去。
如果使用在巢狀迴圈中的話，break 只會跳出目前所屬的 for。以下面的程式為例:
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 10; ++j) {
cout << i << ' ' << j << '\n';
if (j == 3)
break;
}
}
內層 for 的 j 一旦加到 3 就會跳出去，因此會得到以下輸出:
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
左邊的數字是 i 的值 (0 ~ 2)，右邊的則是 j 的值 (0 ~ 3)。
for 的變形
for 的初始式、判斷式、運算式其實可以是空的，如:
for (;;) {
cout << "infinite loop...\n";
}
這是一個合法的 for 迴圈 (只是沒什麼用)。 判斷式是空的話，電腦會當成是真，所以上述的 for 會無止盡的執行 cout << "infinite loop...\n";。
下面的程式會請使用者持續輸入整數，直到使用者輸入奇數，程式會印出該數以及它是第幾個被輸入的數字，然後停止執行:
int number;
for (int i = 0;; ++i) {
cin >> number;
if (number % 2 == 0) {
cout << "Get an even number " << number << " at " << i + 1 << "th input.";
break;
}
}
有時候我們會故意把 for 的初始式和運算式放在小括號外。這可以用於當 induction variable 會在 for 外面被使用的時候，或是運算式很複雜，很難全部塞在小括號內的時候。
下面的程式會印出小於 x 且為 2 的次方數的整數中最大的數 (其實就是要找前面更多範例第 2 題中最後一個被印出來的數):
int i = 1;
// for with empty body
for (; i < x; i *= 2) {}
cout << i / 2 << '\n';
注意: 最後要把 i 除以 2，因為這時候的 i 剛因為條件判斷為假所以跳出迴圈，表示此時它是大於等於 x 的最小的 2 的次方數。也就是 i 比我們預期的還多乘了一次 2，所以要除以 2 把它的值修正回來。
以下的寫法也可以得到一樣的結果:
int number = 1;
for (int i = 1;; ++i) {
if (number * 2 > x)
break;
number *= 2;
}
cout << number << '\n';
它們的差異在於第一種寫法直接用 induction varibale 來計算答案，而第二種寫法則是單純拿 induction variable 來計數，另外又宣告了 number 來計算答案。
第一種寫法不只是比較簡潔而已，當 x 的值很大的時候，第一種寫法的效能 (電腦執行程式所需要花費的時間) 會遠遠好於第二種寫法。
可以透過觀察發現，兩種寫法都會在所求的值達到一個上限後跳出迴圈，但第一種寫法的 induction variable 一次會乘以 2，而第二種則是一次加 1，從這邊就可以理解為何第一種寫法會快很多。
我們之後會談到更多關於程式效能的議題。
總結
- 迴圈 (loop) 是用來重複執行相同或相似行為的語法。其中 for 迴圈是最常被使用的，包含了初始式、判斷式、運算式，以及想要重複執行的陳述。
- 可以在陳述中使用 induction variable，使得陳述在每次的迴圈得到不一樣的結果。
- 可以在 for 迴圈中使用更多的 for，也可以使用 if、else if、else 等陳述。
- 可以利用 continue 直接進入下一個迴圈，或利用 break 跳出目前的 for。
- 初始式、判斷式、運算式不一定要放在 for 的小括號內。
習題
- 讓使用者輸入 N 個整數，印出這 N 個整數的和。
- 讓使用者輸入 N 個整數，印出這 N 個數當中最大的數。
- 讓使用者輸入 N 個整數，印出所有 3 和 5 的倍數。寫兩個版本: 一個使用 continue 一個不使用。
- 持續讓使用者輸入兩個整數: x 和 y，分別代表二維空間中 x 座標和 y 座標的位置，當使用者輸入一個和 (-3, 8) 距離超過 5 的點 (x, y) 時，印出該點的座標並結束執行。
- 讓使用者輸入兩個正整數 n 和 m，用 * 印出上底為 n 、下底為 m、高為 m - n + 1 的梯形。
- 讓使用者輸入兩個偶數 n 和 m，分別代表兩個正方形的邊長，用 * 印出較大的那個正方形，但中間要留一個小正方形面積大小的空白。
- 同 6. 且讓使用者額外輸入一個座標 (x, y)，以大正方形的左上角作為原點，小正方形的左上角要位於使用者輸入的座標 (x, y)。若小正方形的任何一邊會超出大正方形的話，請使用者重新輸入一組新的座標。
