第一週課程 - HackMD

# 第1週課程 ###### tags: `簡報` --- ## slido ![](https://i.imgur.com/3G3CwgM.png) ---- ## Discord 中央競程 ![](https://hackmd.io/_uploads/S17ThBxeT.png) ---- # 課程規劃 ---- ## 課程安排 ![](https://i.imgur.com/kfIzr9O.png) ---- - 時間：每周四晚上7:00~10:00 - 上課方式： - 上課 - 實作 - 有練習題 - 中間有小比賽、有期末大比賽 ---- ## 計分方式 - 每週題單兩題 - 比賽一題可以抵一週 --- # !我大河馬! --- 這堂課會學到什麼 - 理解演算法的原理及概念 - 學會很多不同的思維 - 理解一個方法的效率好不好 - 團隊合作 --- ## 常見judge - codeforce - leetcode - CSES - UVA - Zerojudge - <a style ="color:red"> Vjudge (上課/比賽會使用)</a> ---- ## judge結果 ![](https://i.imgur.com/KS8Fetw.png) ---- ## 編輯器 - Vscode - codeblocks - ~~DevC++~~ 嫌麻煩的可以使用線上的，EX - [OnlineGDB](https://www.onlinegdb.com/online_c++_compiler) - repl.it --- # 其他資訊 ---- ## 檢定 ---- ## CPE 大學程式能力檢定 - 時間：每學期兩次，學期初、末各一次 - 費用：大學生、碩博士免費。 - 題數：7題3小時 - 檢定時間：晚上6:30 ---- ITSA 程式能力線上自我評量時間：兩個月一次，1,3,5,7,9,11月題數：九題3小時檢定時間：晚上6:00 ---- ## 比賽資訊 ---- ## 事項 - 通常不可跨校，多數比賽三人一組 - 通常從大一到碩一(修課未滿九學期)都可參加 - 題目都英文敘述 - 語言C/C++,java,有些有python,TOPC、ICPC有kotlin - 通常比賽可以帶20 or 25 頁的codebook(程式模板) ---- ## 北區程式設計競賽 - 資格：大學生(初階組：大一，進階組：大二以上) - 時間：5-6月 - 地點：台北商業大學 - 獎項：兩組各前三名、佳作數名 ---- ## <a style ="color:red">NCPC 初賽</a> - 地點：北部台師大南部中山(去年因為疫情改線上各校自己開場地) - 規格：至少4題(似乎都6-7題左右)，3小時 - 主要在9~10月 ---- ## <a style ="color:red">NCPC 決賽</a> - 資格：初賽至少AC一題且每校最多六隊(初賽校內前六) - 地點：北部台師大南部中山 - 時間：通常為初賽後兩周，約為十月初 - 規格：9~15題，五小時 - 參加贈品：資料夾 - 獎項：第一名一隊，第二名兩隊，第三名三隊，佳作取約30~40隊 - 備註：點心很好吃 ---- ## <a style ="color:red">TOPC</a> - ICPC前導賽，為線上賽 - 資格不限，有報名就可以參加 - 時間：八月底~十月初之間 - 規格：3小時，至少七題 - 題目出題沒有很好 ---- ## <a style ="color:red">ICPC</a> 國際大學生程式設計競賽分為regional跟world final ---- ## <a style ="color:red">taiwan ICPC regional</a> 台灣最高規格的比賽 - 時間：11月多 - 地點：連三年北商(2019-2021)，桃園龍潭武漢國中(2022-2023) - 資格： - NCPC決賽取前40隊 - TOPC取前40隊 - NCTU，NCPU各取10隊 - CPE錄取 10 隊，但每校不得超過兩隊。 - TOPC 補滿 ---- ![](https://i.imgur.com/ppwPhi9.jpg =x300)![](https://i.imgur.com/muagxLn.png =x300) ---- ![](https://i.imgur.com/Z6FGntR.jpg =450x)![](https://i.imgur.com/WogMhWv.jpg =450x) ---- - 費用：3000-4000(台灣大比賽中唯一需要費用的) - 規格：9~13題，五小時 - 參加贈品：T-shirt跟包包 - 獎項(獎項依主辦單位決定但很少改動)： - 1~10 金牌 - 11~30 銀牌 - 31~60 銅牌 (台清交加起來約30隊能進銀牌線代表有台清交實力) ---- ## ICPC world final 大學競賽程式最高殿堂時間：5,6月舉行資格：各regional賽區取前1 ~ 2名晉級獎項：前4金牌，5 ~ 8銀牌，9 ~ 12銅牌 ---- ## 營隊資訊 ---- ## 陽明交通大學競技程式訓練營(PCCA)：線上的，講師很優質！ ## NCKU ACM Training Courses：要實體，不過有影片可以看，網路上找的到。 ## 資訊之芽算法班：可以在我的頁面看到(演算法資料那邊)，也是實體的，但是限定高中生，不過它的講義是公開的，很優質！！也有YT影片可以看。  --- # C++ 基礎 --- ## 變數的宣告與指派 ---- ### 變數宣告： ```cpp= int a = 1; long long b = 2; char c = 'a'; double d = 2.564; string e = "ABC"; bool ck = 0; //false ``` ---- ## 常見資料型態： ---- ### int： - 整數型態 - 4Byte 可以存放 -2^31 ~ 2^31-1 - 超過會出現無法預期的結果 - 量級$10^9$ ---- ### long long: - 長整數型態 - 8Byte 可以存放 -2^63 ~ 2^63-1 - 運算速度小於int - 量級$10^{18}$ - 常常會因為忽略使用它而 WA !!! ---- ### double: - double： - 雙倍精確度浮點數 - double的精度為15~16位 - 會有誤差 - 不使用float - 題目很少有浮點數運算 ---- ### char： - 字元型態 - 字元以兩個單冒號括住，像是’a’ - 可以用int型態表示，為ASCII碼，例如’a’ = 97 ---- ### string： - 字串型態 - 很多個字元串在一起，以雙冒號括住，例如 “I am Hippo” - 和char[]語法不太一樣，不過string方便很多，競程不使用char[]。 ---- ### bool： - 布林型態 - 僅表示 true(1) 和 false(0) - 常用來判斷某些情況是否用過了。 ---- ### 不常用和注意事項： - float因為準確度太低，誤差太大，不適合在寫題目使用。 - 需要一開始就定義變數的型態，才能給值。 - 若宣告時未指派值，變數的值不一定是 0，可能是任何數。 ---- ### 指派在程式語言的世界中 = 這個符號有著不同的意思。它代表著的，並非我們日常生活中的等於，而是指派。 ---- 所以，如果我們寫下列的程式碼，意思為 a定義為整數型態，並且給他一個值為3 ```cpp= int a; a = 3; // a你現在被我指派為3了!! ``` ---- 同樣的，以下的程式碼也是合法的，和我們理解的 = 不同，現實中的相等是用==表示 ```cpp= int a = 7412; a = 7413; a = 7414; ``` ---- ### 型態互轉某些型態是可以互相轉換的，例如 ```cpp= int a = 3; long long b = 5; double c = 7.321; a = c; b = c; c = a; ``` 不過要注意的是，當浮點數轉為int時候，小數點會全部捨去。 --- ## 一個完整的程式碼 ```cpp= #include <iostream> using namespace std; int main() { cout << "Hello, World!" << '\n'; return 0; } ``` ---- ### 標頭檔在程式設計中，特別是在C語言和C++中，標頭檔或包含檔案是一個檔案，通常是原始碼的形式，由編譯器在處理另一個原始檔的時候自動包含進來。一般來說，程式設計師通過編譯器指令將標頭檔包含進其他原始檔的開始（或頭部）。一個標頭檔一般包含子程式、變數和其他識別碼的前置聲明。需要在一個以上原始檔中被聲明的識別碼可以被放在一個標頭檔中，並在需要的地方包含這個標頭檔。簡單說，它可以提供工具來使用!! ---- 常用標頭檔 ![](https://i.imgur.com/noaEt76.png) ---- 是不是光看就很累呢？競程常用一個標頭檔涵蓋了上面這些 <bits/stdc++.h> 請務必記起來! 我們只要打#include<bits/stdc++.h> 就可以了 ```cpp= #include <bits/stdc++.h> ``` ---- ### standard 今天程式要寫出像是cout 或是cin等的程式碼時，如果沒有使用using namespace std; 就會讓程式無法成功運作。我們要寫 std::cout, std::cin 這樣很麻煩。注意是因為寫題目比較方便，在外面還是盡量不要用。 ```cpp= #include <bits/stdc++.h> using namespace std; ``` ---- ### 輸入cin ```cpp= int x; cin >> x; ``` 那如果我輸入123abc，x會存放什麼，答案是123 cin一個整數時，程式會一直讀取直到下一個位置的字元不是數字為止！ ---- ### 輸出cout 運作(輸出的東西，不一定要是變數！) ```cpp= int x; cin >> x; cout << " x值為 : " << x << '\n'; ``` 題目正常行尾要輸出換行字元’\n’！ $務必注意cin，cout 的箭頭方向$ ---- ### main函式當你要執行一個程式的時候，電腦需要知道你是從哪裡開始的所以我們需要寫一個main主函式 ```cpp= #include <bits/stdc++.h> using namespace std; int main(void){ int a = 3 ; int b ; cin >> b; cout << a << " " << b << '\n'; return 0; } ``` 這樣就完成了一個基本的程式了，大家嘗試第一題hello,world吧 --- ## 進階輸入輸出大家可以試試看如果遇到的字串為Happy birthday cin之後，cout會出現什麼 ---- 答案是只會出現Happy 因為cin >> a 的時候，遇到空白cin會當成你接收結束，所以此時的a值為"Happy"，那要怎麼去解決呢？ ---- ### getline() 運作原理是讀入直到遇到換行字元(‘\n’) ```cpp= string a; getline(cin,a); cout << a << '\n'; ``` ---- ### 此時此刻又會發生一個問題若前面有輸入假設題目先輸入一個整數，再輸入字串。直覺上會這樣寫 ```cpp= int n; string a; cin >> n; getline(cin,a); cout << n << a << '\n'; ``` ---- 不過此時會發現才剛輸入完一個數字後，程式就輸出結束了 ![](https://i.imgur.com/NFhrZoa.png) ---- 為什麼會這樣呢？因為cin是讀到不是整數的字元，而getline遇到換行字元就結束了。所以輸入5的時候 n 讀到 5 ，不過當你按下enter時，換行字元並非整數字元，所以getline就接收到並且結束。 ---- 這樣要怎麼解決呢？簡單的方法就是我們直接讀取兩次，這樣雖然第一次結束了，但是第二次還是會讀進去。 ```cpp= int n; string a; cin >> n; getline(cin,a); getline(cin,a); cout << n << a << '\n'; ``` 但是這樣會影響程式碼的可讀性，這邊提供兩種方法 ---- ### getchar() ```cpp= int n; string a; cin >> n; getchar(); getline(cin,a); cout << n << a << '\n'; ``` ---- ### cin.ignore() ```cpp= int n; string a; cin >> n; cin.ignore(); getline(cin,a); cout << n << a << '\n'; ``` 大家可以嘗試解決下兩題 ---- ### cin/cout 加速速度在程式解題是相當重要的一部分。常常會遇到雖然有些時候，演算法寫的沒什麼問題卻依然TLE(超時)。而加速的方法有常見的兩種 - 使用輸入優化 ios::sync_with_stdio(false), cin.tie(0); - 避免使用endl來換行，取而代之我們使用’\n’，因為endl是由’\n’和flush組成，flush會使目前輸出的結果立即顯示，所以速度不高 ---- ### 注意 - 若只使用第一點，不使用第二點，則在輸出時仍然會因為flush過慢拖累整體執行效率。 - 若只使用第二點，雖然輸出時不會 flush，但 cin 時預設也會 flush，因此依然很慢。 - 請注意，如果要debug，可以把優化那行先註掉，因為優化完輸出會在程式結束的時候才輸出，有些情況下不會立即顯示，很難debug。 ---- ### 程式碼 ```cpp= #include <bits/stdc++.h> using namespace std; int main(void){ ios::sync_with_stdio(false),cin.tie(0); int a; cin >> a; cout << a << '\n'; } ``` --- ## 四則運算 ```cpp= #include <bits/stdc++.h> using namespace std; int main(void){ int a ,b; cin >> a >> b; cout << "加法:" << a + b << '\n'; cout << "減法:" << a - b << '\n'; cout << "乘法:" << a * b << '\n'; cout << "除法:" << a / b << '\n'; cout << "取餘:" << a % b << '\n'; } ``` ---- ### 常用 - $+$ 加法 - $-$ 減法 - $*$ 乘法 - $/$ 除法 - % 取餘數 ---- ### 注意 - 在進行很大的數字相加/相乘時務必注意，若於運算中之任何時刻超過int可表示的範圍，即使最終答案在int範圍，也會導致overflow而使答案錯誤 ---- ### 運算後指派 ```cpp= a += 5; // a = a + 5 b -= 2; // b = b - 2 c *= 3; // c = c * 3 d /= 4; // d = d / 4 a += b; // a = a + b ``` ### 有些不適用 ```cpp= a = (a + 3) * 8 + b; ``` ---- ### 針對 a = a + 1 , a = a - 1 ，有下列寫法 ```cpp= int a = 1; ++a; // a = a + 1 --a; // a = a - 1 a++; // a = a + 1 a--; // a = a - 1 ``` ---- ### 不同之處 - a++ 會做完事情在+1，++a會先+1在做事情 ```cpp= int main() { int A = 2; int B = 2; int C = A++; int D = ++B; cout << "C = " << C << ",D = " << D << '\n'; return 0; } ``` --- ## 條件判斷與基礎邏輯 ---- ### 格式 ```cpp= if (條件) { 做事情; }else if(條件){ 做事情; }else if(條件){//可以做很多次else if 做事情; }else{ 做事情; } ``` ---- ### 舉個例子 ```cpp= #include <bits/stdc++.h> using namespace std ; int main(void){ int a, b; cin >> a >> b; if(a > b){ cout << "a比較大" << '\n'; }else if(a < b){ cout << "b比較大" << '\n'; }else{ cout << "ab一樣大" << '\n'; } } ``` ---- ### 注意事項特別需要注意的有以下幾點： - 條件由小括弧包含住 - 滿足條件後要做的事情由大括號包含住 - 若滿足條件後要做的事情只有一句(以分號為界)，可不包大括弧 - if 可單獨存在，也就是說，就算沒有後面的 else if 跟 else ，也是合語法的 - if 可多層套疊 ---- ### 基礎邏輯 | 基礎邏輯 | 意思 | 例子 | | -------- | -------- | -------- | | > | 大於 | a > 3 | | < | 小於 | a < 3 | | == | 等於 | a == 3 | | != | 不大於 | a != 3 | | >= | 大於等於 | a >= 3 | | <= | 小於等於 | a <= 3 | ---- | 基礎邏輯 | 意思 | 例子 | | -------- | -------- | -------- | | && | 且 | a > 3 && a != 5 | | \|\| | 或 | a > 3 \|\| a == 0 | | ! | 否 | !(a>3) | ---- ### 注意事項 - 特別注意並沒有 3 < a < 5 這種寫法，需要用 3 < a && a < 5 才行，危險的地方是，這個程式碼並不會導致編譯錯誤 - 多個判斷有前後順序，由前往後，在陣列中很常用來判斷邊界問題。 - 記住!! 等於是 == 而且寫成a=3編譯也不會出錯，然後debug半天才看到，會很想罵髒話! ---- ### 三元運算子什麼是三元運算子(ternary operator)，簡單說它是 if … else … 的精簡版。 ```cpp= 條件式 ? 條件式為true時執行的陳述句 : 條件式為false時執行的陳述句 ``` ---- 上面語法看不懂也沒關係一般寫 if … else … 的例子如下： ```cpp= int ret, a = 10, b = 11; bool state = true; if (state) ret = a; else ret = b; cout << ret << '\n'; ``` ---- 用三元運算子可以寫成 ```cpp= 條件式 ? 條件式為true時執行的陳述句 : 條件式為false時執行的陳述句 ``` ```cpp= int ret, a = 10, b = 11; bool state = true; ret = state ? a : b; cout << ret << '\n'; ``` --- ## 進階運算 ---- ### 浮點數誤差 - 因為電腦是離散的結構，所以在使用double進行加加減減多少會產生一些誤差。 - 此時我們就不以==來判斷是否相等，取而代之的是，我們只需判斷他們之間差的絕對值是否小於特定值，我們稱這個值為epsilon。 ---- 另外，在程式中可以使用1e5,1e6…這種用法，簡單說就是10的X次方，所以我們在定義epsilon可以不用定義的那麼長。例如double eps = 0.000000001; 等價於 eps = 1e-9; ```cpp= double a, b; double eps = 1e-9; cin >> a >> b >> c; if(a > b && a-b < eps) cout << "Equal" << '\n'; else if(a < b && b-a < eps) cout << "Equal" << '\n'; else cout << "not Equal" << '\n'; ``` ---- ### 字元運算 - 在提到char字元的時候，有說到每個字元會對應到一個[ASCII碼 - 詳情點進去看](http://kevin.hwai.edu.tw/~kevin/material/JAVA/Sample2016/ASCII.htm) - 所以字元在進行運算的時候，會將其視為ASCII碼! 例如 'a'+10 其實就是 97+10 對應過去的字元也就是'k'; - 請注意 A’～’Z’以及’a’～’z’以及’0’～’9’，在ASCII table的位置是連續的，但這三者之間並非連續的，'A' 是 65 , 'a' 是 97 , '0' 是48 ---- ### <a style = "color:purple"> "大寫轉小寫" </a> - 因為’a’ 和 ‘A’ 差距是 97-65 = 32 ; 不知道也沒關係可以利用型態互轉來計算 - 我們只要大寫字母 + 差距就會是小寫，反之就減回去。 ```cpp= char c; cin >> c; c += 'a' - 'A'; // c = c + ('a' - 'A'); cout << c ; ``` ---- ### 字元比較 - 字元的比較以ASCII碼來比。例如 ‘a’ > ‘A’ , ‘A’ > ‘0’ - 也可以拿來判斷位元是否在裡面，像是判斷字元是不是小寫 ```cpp= char c; cin >> c; if(c >= 'a' && c <= 'z') cout << "c是小寫" << '\n'; else cout << "C不是小寫" << '\n'; ``` ---- ### 位元運算電腦以二進位 0 和 1 儲存，有以下幾種位元運算 | | 意思 | 例如 | |:--------:|:--------------------------------- |:----------------------:| | & | 且(and)，同1為1，其餘為0 | 100 & 101 = 100 | | \| | 或(or)，其1為1，其餘為0 | 100 \| 101 = 101 | | ^ | 互斥(xor)，其1為1，同1為0，同0為0 | 100 ^ 101 = 001 | | ~ | 非(not)，把1換0，把0換1 | ~ 100 = 011 | ---- ### 左右移 | | 意思 | 例如 | |:--------:|:--------------------------------- |:----------------------:| | << | 左移(將一個變數向左移動並且補0) | 101 << 1 = 1010 | | >> | 右移(將一個變數向右移動並且捨去) | 101 >> 1 = 10 | ---- ### <a style = "color:purple"> "大寫轉小寫" </a> 如果利用xor的性質，是不是就剛好可以讓大小轉小寫，小寫轉大寫了呢？ ```cpp= char c; cin >> c; c = c ^ 32; cout << c << '\n'; ``` ---- ### <a style = "color:purple">"乘$2^n$" 除$2^n$</a> - 利用二進位的特性，假設二進位數字1010 乘2的時候，會變成10100，是不是就剛好向左移動了一位。 - 反之就是除法，所以我們可以這樣寫 ```cpp= int a; cin >> a; cout << "a * 2 = " << (a << 1) << '\n'; cout << "a / 2 = " << (a >> 1) << '\n'; ``` - 請注意，因為cout cin的箭頭和左移右移一樣，所以需要括起來，以免出錯。 ---- ### <a style = "color:purple">"是否為奇數" </a> 我們在判斷一個數字是否為奇數很顯然會這樣寫 ```cpp= int a; cin >> a; if (a % 2 == 1) cout << "是奇數" << '\n'; else cout << "不是奇數" << '\n'; ``` ---- 但我們可以利用 true 為 1, false 為 0 的特性，搭配&且(and)。如果是奇數的話2進位的最右端一定是1，所以&1的結果就會是 1 (true) ```cpp= int a; cin >> a; if (a&1) cout << "是奇數" << '\n'; else cout << "不是奇數" << '\n'; ``` ---- ### 這樣有什麼好處？感覺變得好難理解？理由是使用後者的話可以加速約600%的效率有興趣可以看這篇[利用位元運算加速運算效率](http://chuiwenchiu.wordpress.com/2007/05/11/as3) --- ## 陣列 ---- 如果要儲存5個變數，我們可能會這樣做 ```cpp= int a, b, c, d, e; ``` 但如果100、1000個變數那怎麼辦呢？ ---- ### 宣告使用陣列，可以使用儲存大量資料，語法如下。注意，程式是從0開始，0~初始大小-1。 ```cpp= int a[15]; //a[0]~a[14] 共15個 char b[150]; //b[0]~b[149] 共150個 double c[200]; //c[0]~c[199] 共200個 string str[1500]; //str[0]~str[1499] 共1500個 ``` 也可以在宣告時候給值 ```cpp= int arr[4] = {1,5,3,4}; ``` ---- - 可以不用指派每一個元素的值，只指派前幾個，不足者會自動補 0 - 常常用來全部初始為 0 。 ```cpp= int arr[100] = {0}; ``` ---- 注意: - 若全部未指定值，則陣列中每個元素的值可能是任何值！ - 陣列宣告過後，不可改變大小或重新宣告。 - 程式語言的世界編號由0開始，所以設定大小為n，可用空間為0~n-1 ---- ### 取值和修改如果我們想輸出陣列中位於 3 號的元素的值，這樣寫： ```cpp= cout << arr[3] << '\n'; ``` ---- 陣列中的元素就像一般元素一樣，可以加減乘除，可以任意指派值，直接把它當成平常的變數就好： ```cpp= arr[1] += 15; arr[2] = 5; arr[3] = arr[1] + arr[2]; cout << arr[0] << arr[1] << arr[2] << '\n'; ``` ---- ### RE錯誤 (記憶體區段錯誤) 當陣列取值超過範圍大小，就會跑出RE錯誤，像是剛剛提到 ```cpp= int a[5] = {1,2,3,4,5}; cout << a[5] << '\n'; // Wrong!!! ``` ---- ### 多維陣列陣列是可以有多個維度的，例如： ```cpp= int arr[13][14][15] = {0}; // 設0， cin >> arr[2][5][6]; cout << arr[2][5][6] << '\n'; ``` ---- 用一張圖來看，假設我們 int maze[3][4]，存放的記憶體會長這樣; ![](https://i.imgur.com/kRKZB9h.png) ---- 同時也可以這樣定義 ```cpp= int arr[2][3] ={{1,2,3},{4,5,6}}; ``` 當然我們也不是可以存放無限多的陣列，要注意，在區域變數中乘起來最大約$10^5$~$10^6$，在全域變數中乘起來不可以超過大小限制約$10^8$。 --- ## 迴圈 ---- 當我們需要重複做同一件事很多次，總不能一個一個全部寫出來，如果要重複1000千次，那是不是程式碼就要幾千行，影響了可讀性，所以便會使用迴圈，而迴圈有下列的用法。 ---- ### for 最常用的迴圈，如下： ```cpp= for (int i = 0 ; i < 100 ; i++){ cout << i << '\n' ; // do things } ``` ---- ```cpp= for ( 1 ; 2 ; 3 ){ do things } ``` for迴圈有四件事要做 1. 在第一個在分號前，代表程式執行到迴圈時，第一件會做的事情，像是我宣告了一個 i = 0 2. 在第二個分號前，代表程式進行的條件，如果不滿足，便會離開這個迴圈，像是範例中，只要 i < 100 就會繼續。 3. 執行for迴圈內文，像是我輸出 i 的值 4. 在第二個分號後，代表每次執行迴圈一次後，程式會做的事，像是我讓i的值+1 ---- ### string 基本操作字串長度 : 變數名稱.length() ```cpp= string a; cin >> a; cout << a << "長度=" << a.length() << '\n'; ``` ---- ### string 使用 for迴圈遍歷在處理字串的時候很長需要一個一個字元來判斷，此時就會用到 length()，舉個簡單例子。 ```cpp= string a; cin >> a; for (int i = 0 ; i < a.length() ; i++) { if (a[i] >= '0' && a[i] <= '9') cout << "number" << '\n'; else if (a[i] >= 'a' && a[i] <= 'z') cout << "小寫" << '\n'; else if (a[i] >= 'A' && a[i] <= 'Z') cout << "大寫" << '\n'; else cout << "其他" << '\n'; } ``` ---- 需要特別注意的是，string在陣列上也是從0開始到length()-1，所以for迴圈那邊不能寫<=，會出錯 ---- 有時候我們的迴圈不需要用到變數，像是 ```cpp= int n = 0; for( ; n < 10 ; ){ int x; cin >> x; n += x; } ``` 我們只需要在意n是否小於10這樣寫for迴圈就不好看，所以while就出現了! ---- ### while 用法如下： ```cpp= while(n < 10){ int x; cin >> x; n += x; } ``` 只保留了for迴圈中，是否判斷的部分，這就是while ---- ### 無限迴圈 while(true) 有些時候終止條件很多，沒辦法一行解決的時候可以先使用無限迴圈，再配合break來中止 ---- ### break break就是字面上的意思，可以用來跳出迴圈。直接用例子來看。假設我們要找出哪個數字的三次方為438976 此時我們不知道哪個數字，所以我們可以慢慢加上去，一一判斷是不是答案 ```cpp= int x = 1; while(true){ if (x*x*x == 438976) break; x+=1; } cout << x << '\n'; ``` ---- ### continue continue用於跳過某種情況，但是迴圈會繼續執行。假設今天題目要求輸出1~1000之中，不是偶數的數字，那我們可以這樣寫 ```cpp= for (int i = 1 ; i < 1000 ; i++){ if (i % 2 == 0) continue; else cout << i << '\n'; } ``` --- ## 迴圈特殊應用 ---- ### while ( cin >> n ) 有些題目會先輸入一個整數代表幾筆，但有些卻會要求多筆測資的輸入直到EOF，這時候怎麼辦呢？我們可以利用 cin 函數會回傳true false的特性。 ```cpp= int n; while(cin >> n){ cout << n << '\n'; } ``` cin 回傳true false的條件為，不符合 n 的值。像是整數卻輸入字元就會回傳false. ---- ### do while 有些情況下，我們無論如何要先做一次再來判斷，這時候就可以用do while來寫，像是 ```cpp= int k; cin >> k; do{ cout << k << '\n'; k *= 2; }while(k < 500); ``` ---- 剛提到，有些多筆測資的題目會先輸入一個整數，代表幾筆測資，所以我們可能會這樣寫 ```cpp= int t; cin >> t; for (int i = 0 ; i < t ; i++) { // do things } ``` ---- 但我們也可以利用 true的值是1(只要不等於0都算) false的值是0來寫，所以可以寫成 ```cpp= int t; cin >> t; while(t--){ //dothing } ``` ---- ### 多層迴圈簡單明瞭，所以直接舉個例子，假設我們要輸出box裡面全部的東西，我們就可以這樣寫 ```cpp= int box[2][3] = {{1,2,3},{4,5,6}}; for (int i = 0 ; i < 2 ; i++){ for (int j = 0 ; j < 3 ; j++){ cout << box[i][j] << " "; } cout << '\n'; } ``` ---- ### 注意事項(重要) - 停不下來：執行時候，發現怎麼停不下來。一定是有地方寫錯了，且高機率是判斷式子。 - 或者前面提到的，把 == 寫成 = ，這樣程式也不會結束。 ```cpp= for (int i = 0 ; i < 5 ; i--) ``` ```cpp= for (int i = 0 ; i = 5 ; i++) ``` --- ## 函式 ---- ## 函式是什麼什麼是函式，函式的英文是function，你可以把它想像成一塊有特定功能的程式，它不會被寫在main裡面，因為main本身也是個函式。我們直接來看個例子 ```cpp= void say_hello(){ cout << "Hello~" << '\n'; } ``` ---- 上面的程式中，宣告了一個名為say_hello 的函式。後面的括號內是來裝參數的，不過這個例子沒有參數。大括號底下的內容，就是要做的事情。簡單來說，這個函式就只印 Hello~ 的功能所以我們可以main()呼叫這個函式 ```cpp= void say_hello(){ cout << "Hello~" << '\n'; } int main(void){ say_hello(); say_hello(); } ``` ---- ### 函式的小誇號函式的小誇號是用來裝參數的，可以看下列例子(可以好幾個參數，也可以不要就像上面一樣只有誇號) ```cpp= void sum(int x ,int y){ cout << x + y << '\n'; } int main(void){ int a , b; cin >> a >> b; sum(a,b); } ``` ---- ### 函式的型態與回傳值在上述例子中，我們最前面寫的都是void 意思為並不需要回傳什麼。也可以透過上述例子知道他就只是單純印出一些東西而已。如果要讓函式回傳一個值，就要依照回傳答案的型態定義。 ---- 注意：定義什麼樣形態的函式，只能回傳同樣型態的值才行!! ```cpp= int add10(int x){ return x+10; } int main(void){ int s; cin >> s; s = add10(s); cout << s << '\n'; } ``` ---- ### 函式的定義問題我們把上面的例子程式碼順序改一下 ```cpp= int main(void){ int s; cin >> s; s = add10(s); cout << s << '\n'; } int add10(int x){ return x+10; } ``` ---- 此時會發生以下問題 ![](https://i.imgur.com/5fiMdqI.png) ---- 這是怎麼了？理由是main函式執行的時候，抓不到add10，就像我們在定義變數一樣，必須要先定義才能使用，那又為什麼上上面的例子卻可以用呢？理由是，add10宣告在main之前，所以main抓的到函式。 ---- 那要怎麼解決呢？一是宣告在前面，第二是在一開始的時候宣告函式。 ```cpp= #include <bits/stdc++.h> using namespace std; int add10(int x); int main(void){ int s; cin >> s; s = add10(s); cout << s << '\n'; } int add10(int x){ return x+10; } ``` ---- ### 函式的呼叫前面的範例都是在main主函式裡面呼叫函式，其實函式也可以呼叫函式哦舉個例子，想要判斷是否會被當。 ```cpp= #include<bits/stdc++.h> using namespace std; void IPass () { cout<<"PASS"; } void IFail () { cout<<"FAIL"; } void sayResult (int score) { if(score>=60){ IPass(); } else{ IFail(); } } int main() { int score; cin >> score; sayResult(score); } ``` ---- 可以看到我們在sayResult函式裡面呼叫了IPass()跟IFail() 當然了，自己也可以呼叫自己，像是 ```cpp= void say_hello() { cout<<"Hello~"; say_hello(); } ``` 雖然有點不直覺，不過這可以做到很多神奇的事情，就是我們接下來要介紹的"遞迴" --- ## 遞迴 ---- ```cpp= void say_hello() { cout << "Hello~" << '\n'; say_hello(); } ``` 這個函式在印出Hello~ 之後，會在呼叫自己，自己又會印出Hello~在呼叫自己。就很像一個說哈囉的夢，在夢中說完哈囉會躺在床上在做一個一模一樣的夢，在夢中夢說哈囉，然後在夢中夢躺床坐夢中夢中夢..... ---- 這樣不就不會醒來了嗎？對，如果執行的話會變成永遠的循環，直到當掉為止。 ### 注意所以在使用遞迴函式的時候，需要注意：必須有結束條件，或是在某些條件下才呼叫自己，這樣才有醒來的機會。 ---- ### 經典問題：費波那契數列費波那契定義如下 1. 第0項 = 0 2. 第1項 = 1 3. 其他項 = 前兩項相加 ---- 所以我們可以照定義寫出 ```cpp= int f (int n) { if (n == 0) return 0; else if (n == 1) return 1; else return f(n-1) + f(n-2); } ``` ---- 在主函式就可以呼叫了 ```cpp= #include <bits/stdc++.h> using namespace std; int f(int n){ if (n == 0) return 0; else if (n == 1) return 1; else return f(n-1) + f(n-2); } int main(void) { int n; cin >> n; cout << f(n) << '\n'; } ``` ---- 遞迴是個很神奇的東西，不知道要怎麼知道f(5)，但只需要知道f(4) f(3)的值，而這兩個也無法憑空生出來，所以在繼續呼叫下去值到條件到達，很多時候寫出來自己很難想像是怎麼寫出來的。像是練習題的河內塔，用遞迴寫只需要短短幾行，超級神奇的。 ---- ## 因此遞迴有個名言 ### "遞迴只應天上有，凡人應當用迴圈" --- ## 區域、全域變數、靜態變數 ---- ### 區域變數：起始於變數宣告，結束於宣告敘述所在的區塊的大右括號，在生命週期內會佔用記憶體。缺點：記憶體會被分配在 stack 區段，而這塊區域一般來說並不夠大，因此只要陣列太大，就會立刻 stack overflow。 ---- ```cpp= #include <bits/stdc++.h> using namespace std; int func(int a, int b) { int c = 5; return c*(a+b); // abc都屬於func的區域變數 (和main的abc不衝突) }; int main(void){ int a, b; //屬於main函式的區域變數 cin >> a >> b; cout << func(a,b) << '\n'; for (int i = 0 ; i < 3 ; i++) { int x; //出了for迴圈之後，x就結束了 cin >> x; cout << x << '\n'; } } ``` ---- ### 全域變數宣告在所有區塊和類別之外的變數不可宣告同名的全域變數若沒有給定初始值，會自動給0 生命週期：在程式執行到程式結束期間都會暫用記憶體生存空間：從宣告後的任意程式碼區塊都可存取好處是，相較於區域變數不會被配置到 stack 區，他陣列大小可以取比較大，對於競程來說常常會需要大陣列。 ---- ```cpp= #include <bits/stdc++.h> using namespace std; int arr[10000000]; //全域變數，所以沒有給定初始值會自動給0 int main(void){ int str[100000]; //這邊是區域變數，沒有給定初始值就不會有 } ``` 題外話：雖然在競賽中會因為需要大陣列而用到全域，不過不加上const的全域變數是不好的，會使得程式維護性降低。也不要全部變數都放在全域。 ---- ### 靜態變數(競程幾乎不會用到) 不可宣告同名的靜態變數若沒有給定初始值，會自動給0 生命週期：在程式執行到程式結束期間都會暫用記憶體生存空間：任意程式碼區塊皆可存取詳細用法可以參考[static的5種用法](https://shengyu7697.github.io/cpp-static/)  {%hackmd @themes/dracula %}