無痛入手 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';

2. 由小到大印出所有小於 x 且為 2 的次方數的整數:

for (int i = 1; i < x; i *= 2)
	cout << i << '\n';

3. 由小到大印出所有平方數小於 x 的正整數:

for (int i = 1; i * i < x; ++i)
	cout << i << '\n';

4. 由大到小印出所有小於 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，從這邊就可以理解為何第一種寫法會快很多。

我們之後會談到更多關於程式效能的議題。

總結

1. 迴圈 (loop) 是用來重複執行相同或相似行為的語法。其中 for 迴圈是最常被使用的，包含了初始式、判斷式、運算式，以及想要重複執行的陳述。
2. 可以在陳述中使用 induction variable，使得陳述在每次的迴圈得到不一樣的結果。
3. 可以在 for 迴圈中使用更多的 for，也可以使用 if、else if、else 等陳述。
4. 可以利用 continue 直接進入下一個迴圈，或利用 break 跳出目前的 for。
5. 初始式、判斷式、運算式不一定要放在 for 的小括號內。

習題

1. 讓使用者輸入 N 個整數，印出這 N 個整數的和。
2. 讓使用者輸入 N 個整數，印出這 N 個數當中最大的數。
3. 讓使用者輸入 N 個整數，印出所有 3 和 5 的倍數。寫兩個版本: 一個使用 continue 一個不使用。
4. 持續讓使用者輸入兩個整數: x 和 y，分別代表二維空間中 x 座標和 y 座標的位置，當使用者輸入一個和 (-3, 8) 距離超過 5 的點 (x, y) 時，印出該點的座標並結束執行。
5. 讓使用者輸入兩個正整數 n 和 m，用 * 印出上底為 n 、下底為 m、高為 m - n + 1 的梯形。
6. 讓使用者輸入兩個偶數 n 和 m，分別代表兩個正方形的邊長，用 * 印出較大的那個正方形，但中間要留一個小正方形面積大小的空白。
7. 同 6. 且讓使用者額外輸入一個座標 (x, y)，以大正方形的左上角作為原點，小正方形的左上角要位於使用者輸入的座標 (x, y)。若小正方形的任何一邊會超出大正方形的話，請使用者重新輸入一組新的座標。