## 迴圈講義(Loop) by 葉宥辰 --- ## 甚麼是迴圈？ ## 為甚麼要學迴圈呢? ---- ## 思考 現在我們可以很輕鬆的寫出兩個數字相加的程式 但如果增加到10個或是更多呢? ---- ## 錯誤示範 ```cpp= int main() { int a, b, c, d, e, f, g, h, i, j; cin >> a >> b >> c >> d >> e >> f >> g >> h >> i >> j; cout << a + b + c + d + e + f + g + h + i + j << '\n'; } ``` ---- ## 思考 這種寫法不只麻煩 而且泛用性非常低 如果改成 n 個數字相加 也能輕鬆搞定 我們希望只寫一份程式 就可以做到所有情況 所以我們需要使用... ---- ## 迴圈 利用電腦能快速進行大量計算的優勢 我們可以做到很多靠人腦很難做到的事情 所以現在就要來教大家如何使用迴圈 以及迴圈的種類 --- ## While ---- ### 用法 這是一種比較直觀的迴圈寫法 用法如下 ```cpp= while (限制條件) { 要執行的操作 } ``` ---- 當 **`限制條件`** 為 **`True`** 時 迴圈將不斷被執行 下面給出一個範例 ---- ```cpp= while (詹挹辰是ㄌㄌ控) { 向著小學全速的前進; } ``` 執行這段程式碼時電腦會先判斷 **`詹挹辰是ㄌㄌ控`** 這個條件 我們都知道 **`詹挹辰是ㄌㄌ控`** 結果會是 **`True`** 所以會開始執行 **`向著小學全速的前進`** ---- ```cpp= while (詹挹辰是ㄌㄌ控) { 向著小學全速的前進; } ``` 執行完後 並不會跳出迴圈 而是再次進行條件判斷 如果條件為 **`True`** 又會繼續執行 ---- ```cpp= while (詹挹辰是ㄌㄌ控) { // -> 1 向著小學全速的前進; // -> 2 } ``` 所以被執行的順序就是 1 -> 2 -> 1 -> 2 ... 你會發現 上面這段程式根本不會停止 因為 **`詹挹辰是ㄌㄌ控`** 這個條件永遠都會是 **`True`** 所以我們稱之為 **無窮迴圈** ---- 但我們不會希望寫一支不會停止的程式 而且把這種東西丟到OJ上 會害OJ卡住 所以我們需要設定其他終止條件 當然設定終止條件有很多種作法 等下會介紹最泛用的 **`break`** 和 **`continue`** ---- 但在這之前 我們先來練習一下 **`while`** 迴圈的用法 請大家試著寫寫看[這題](http://mdcpp.mingdao.edu.tw/contest/9/problem/A016) :::spoiler 參考程式 ```cpp= #include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; int i = 1; while (i <= n) { cout << i << ' '; i++; } } ``` ::: ---- ### 更多練習 讓我們看看 [這題](http://mdcpp.mingdao.edu.tw/contest/9/problem/A021) 和 [這題](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=a024) 你會發現迴圈其實是可以有很多變化的 每個人打出來的迴圈可能都會有些許不同 ---- ### [MDCPP Judge A021](http://mdcpp.mingdao.edu.tw/contest/9/problem/A021) :::spoiler 參考解答 ```cpp= #include<bits/stdc++.h> using namespace std; int main() { int sum = 0, m = 0, d; while (sum < 450) { cin >> d; sum += d; m++; } cout << m; } ``` ::: ---- ### [Green Judge a024](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=a024) :::spoiler 參考解答 ```cpp= #include<iostream> using namespace std; int main() { int n, sum = 0; cin >> n; while (n != 0) { sum = sum + n % 10; n /= 10; } cout << sum << '\n'; } ``` ::: --- ## Break & continue ---- 這邊介紹的東西通常會和 **`if` `else`** 一起使用 而且他們一定要放在迴圈裡 **`break`** 執行到時會直接跳出迴圈 **`continue`** 執行到時會直接進入下一次迴圈 沿用之前的範例來說就是 ---- ```cpp= while (詹挹辰是ㄌㄌ控) { if (遇到紅燈) continue; 向著小學全速的前進; if (遇到ㄌㄌ) break; // A } // B ``` 先從 **`break`** 說起 如果執行到break 就會跳出迴圈 可視為跳到 `B` 的地方繼續執行 ---- ```cpp= while (詹挹辰是ㄌㄌ控) { if (遇到紅燈) continue; 向著小學全速的前進; if (遇到ㄌㄌ) break; // A } // B ``` 而 `continue` 則是會跳到 `A` 的地方 仍在迴圈中 但 `向著小學全速的前進` 和下面的判斷式就會被跳過不執行 ---- 雖然 `break` 和 `continue` 好像沒有那麼必要 但它會讓你的程式碼看起來更好懂、整潔 --- ## For ---- 終於教到 `for` 迴圈了! 他和 `while` 究竟有甚麼不同呢? 他們本質都是一樣的 只是寫法不同而己 ---- ### 用法 ```cpp= for (初始條件; 限制條件; 每次迴圈結束須執行的指令) { 要執行的操作 } ``` 看起來可能會有點複雜 那我們把它翻譯成 `while` 看看 上面等價於 ```cpp= 初始條件 while (限制條件) { 要執行的操作 每次迴圈結束須執行的指令 } ``` ---- 沒錯 `for` 只是把所有東西縮到一行之中而已 所以能用 `for` 寫的 `while` 也一定可以 反之亦然 而且並不是每一項都要填 也可以這樣打 ```cpp= for (;;) cout << "hi\n"; ``` 但如果你試過 他會給你無限個 **`hi`** ---- 我們直接用例題來看看他的確切用法吧 [小朋友點名](http://mdcpp.mingdao.edu.tw/contest/9/problem/A016) ```cpp= #include<bits/stdc++.h> using namespace std; int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cout << i << ' '; } } ``` 注意 : `初始條件` 只會被執行一遍 --- ## 挑戰 ---- 我們能不能用迴圈印出九九乘法表呢? 一層迴圈不夠嗎? 那就用兩層阿? 真的不能用一層迴圈嗎? ---- ### 九九乘法表範例 如果沒辦法向下面輸出的一樣整齊沒關係 只要順序是對的就好  ---- ### [來寫個複雜一點的題目吧!](https://codeforces.com/problemset/problem/1498/A) 注意這題因為數字很大所以要用 long long 喔 如果要求兩個數字 $a, b$ 的 $gcd$ 可以像這樣 ```cpp= long long g = __gcd(a, b); ``` 之後會教大家如何自己寫 使用的方法是大家小學學過的輾轉相除法 或是叫做歐幾里得算法 --- ## 巢狀迴圈 ---- ### [空拍圖](http://mdcpp.mingdao.edu.tw/contest/9/problem/A018) 先來想想看這題要怎麼做 ---- 一層迴圈好像不太夠? 那就兩層阿 ---- 巢狀迴圈其實就是很多個迴圈包在一起 ---- ### 思考 我們可以先把題目化簡 先輸出一半就好 ---- 數字 $i$ 會被輸出 $i$ 次 所以我們可以這樣寫 ```cpp= for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { cout << i; } cout << '\n'; } ``` ps : 內層迴圈負責輸出 $i$ 次 $i$ ---- 現在我們有 $1$ ~ $n$ 了 那我們只要把在跑從 $n - 1$ ~ $1$ 解決這題了 我們只要把上面的程式碼稍加修改 ---- ```cpp= for (int i = n - 1; i >= 1; i++) { for (int j = 1; j <= i; j++) { cout << i; } cout << '\n'; } ``` 只要合併兩個程式碼 就可以AC拉 :100: ---- 當然巢狀迴圈還有其他千百種變化 在程式中非常基本且重要 希望大家可以多加練習 讓自己能思緒清楚的打出多層迴圈 ---- ## 練習題 ---- ### [跳格子](http://mdcpp.mingdao.edu.tw/contest/9/problem/A019) 多重輸入在比賽中是非常常見的 ---- ### [輝夜姬的3N+1猜想](http://mdcpp.mingdao.edu.tw/problem/T001) 注意要開 $long \ long$ 喔! 注意要開 $long \ long$ 喔! 注意要開 $long \ long$ 喔! ---- ### [分組競賽](http://mdcpp.mingdao.edu.tw/contest/9/problem/A020) ---- 還有太多太多運用了 你以後會發現沒有用到迴圈就能解的題目其實少之又少 這邊就不再舉例了 --- ## 感謝聆聽