--- tags: 初階班 --- # 10th 初階班 上課講義 ## 上學期 ### 程式的基礎架構 - 預估上完的時間:第一週 - 講課:方旭誠 #### 課程內容 首先來看看大多數人學習的第一個程式 --- *Hello, world* ```cpp= #include<iostream> // 標頭檔，引入函數庫 using namespace std; // 命名空間，區隔函式的意義 int main() // 主程式碼 { cout << "Hello, world" << endl; // 輸出 system("pause"); // 程式暫停 return 0; // 回傳值 } ``` #### 標頭檔與命名空間 接著來試著解構內部的內容 首先是標頭檔和命名空間 標頭檔就像是一部字典一樣 賦予包含於其中的函式意義 因此當我們需要不同功能的函式時 便須引入相應的標頭檔 > 先將函式看做一種特殊的指令 > 在後面的課程會細講 而命名空間則像是一個識別編號 因為不同功能的函式可能會有相同的名稱 在使用上便會有所衝突 這時運用命名空間的不同 便能精確的定義該函數所應該套用的定義 而我們使用 `std` 命名空間 便是因為 C++ 的標準庫是定義在他之下的 如果不在程式碼前打上`using namespace std;`的話 在使用上會變成這樣 ```cpp= #include<iostream> // 標頭檔，引入函數庫 int main() // 主程式碼 { std::cout << "Hello, world" << std::endl; // 輸出 system("pause"); // 程式暫停 return 0; // 回傳值 } ``` 可以看到 必須在使用某些涵蓋於標準庫內的程式碼時 精確的用 `std::` 標明是 `std` 這個命名空間底下 才能被系統有效執行 再舉個更簡單的例子好了 假如今天復旦國中和~~某間山上學校~~ 都有一個人叫王小明 那這時教育部要怎麼不搞混學生身分呢？ 便是在前面冠上他們所屬的學校 把命名空間想像成校名 就好理解很多了 #### 主程式 接下來的 `int main(){ code... }` 就很簡單明瞭了 就是整個程式運行時 主要程式碼所在的地方 如果你亂改名稱 編譯器會因為找不到 `main` 而錯誤喔~ #### 輸出 再來就是 `cout` 和 `endl` `cout` 是輸出 與之對應的是 `cin // 輸入` 而 `endl` 則是換行 前面有說到 他們是被定義在 `std // 命名空間` 、`iostream // 函式庫`之下的 所以需要引入該函式庫與命名空間才有意義 不過有些關鍵字是 C++ 最初的基底 並不是被後續定義出來的功能 因此不用引入便能執行程式 而這些關鍵字在下回便會提及 這裡先埋個伏筆 關於輸出的規則 大致為`cout << "想輸出的文字";` 其中的 `<<` 為必要語法 `endl` 則視需求加在其中或結尾 ```cpp= // example cout << "Hello, world" << endl; cout << "Hello" << endl << "world"; ``` #### 程式終止 來到最後的兩行 `system("pause");` 的功用主要在執行檔(.exe)上較為顯著 而 `main(){ }` 裡的 `return 0;` 可以理解為回傳一個值 告訴電腦程式已經執行完畢 而 `return` 在 C++ 還有別的用途 這也是後話 上述的兩行程式碼的有無造成的影響 請各位在電腦上用執行檔(.exe)實際操作看看 並觀察小黑窗的顯示資訊有何不同 > **注意** > 在Judge平台上解題時 > 請勿加入 `system("pause");` > 不然系統會出錯哦 #### 技術總結 1. 標頭檔和命名空間關乎程式碼是否具有意義和功能 2. `main(){ }` 是程式運行的主要區域，不要改他的名字 3. `cout` 要加 `<<` 後並用 `""` 包覆要輸出的文字 4. 每行程式碼後**要加分號!!!**，這對電腦來說是一個指令的結束，並不是以 `enter` 或 `space` 作為結束 5. 在Judge平台上不要使用 `system("pause");` 6. `return` 會回傳值，在 `main` 裡作為程式的結束 #### 課堂練習 [DanDanJudge ](http://203.64.191.163/) > a.033 > a.196 --- ### 資料型態與運算子 - 預估上完的時間:第二週 - 講課:羅時瀚 #### 課程內容 這節課我們要上的是資料型態與運算子 而他們也是上回說到的 可以不用呼叫任何標頭檔與命名空間便可使用的指令喔！ #### 資料型態 接下來我們先講到資料型態 資料型態在C或C++是非常重要的 在想使用任何變數前 都要告訴電腦它的資料型態 這個動作叫做宣告 若沒有宣告它的資料型態或搞錯資料型態 都有可能會出現無法編譯的情況 以下就是常見的資料型態 | 資料型態 | 位元組 | 表示範圍 | | -------- | -------- | -------- | | int | 4 | $-2,147,483,648$ ~ $2,147,483,647$ | | unsigned int | 4 | $0$ ~ $4,294,967,295$ | | long long | 8 | $-9,223,372,036,854,775,808$ ~ $9,223,372,036,854,775,807$ | | unsigned long long | 8 | $0$ ~ $18,446,744,073,709,551,615$ | | bool | 1 | $true$ $or$ $false$ | | char | 1 | $-128$ ~ $127$ | | float | 4 | $1.2*10^{-38}$ ~ $3.4*10^{38}$ | | double | 8 | $2.2^*10^{-308}$ ~ $1.8^*10^{308}$ | #### 運算子 |設定運算子 | 功能 | 示範 | | -------- | -------- | -------- | | = | 設定 | a = 1 | | 單元運算子 | 功能 | 示範 | | -------- | -------- | -------- | | + | 正 | +a | | - | 負 | -a | | ++ | 遞增 | \++a,a++ | | \-\- | 遞減 | \-\-a,a\-\- | | ! | 否 | !a | | ~ | 取1的補數 |~a | | 算數運算子 | 功能 | 示範 | | -------- | -------- | -------- | | + | 加 | a + b | | - | 減 | a - b | | * | 乘 | a * b | | / | 除 | a / b | | % | 取餘數 | a % b | | 關係運算子 | 功能 | 示範 | | -------- | -------- | -------- | | > | 大於 | a > b | | < | 小於 | a < b | | >= | 大於等於 | a >= b | | <= | 小於等於 | a <= b | | == | 等於 | a == b | | != | 不等於 | a != b | | 邏輯運算子 | 功能 | 示範 | | -------- | -------- | -------- | | && | AND | a && b | | \|\| | OR | a \|\| b | | ^ | XOR | a ^ b | |AND | true | false | | --- | --- | --- | |**true**| true | false | |**false**| false | false | | OR | true | false | | --- | --- | --- | |**true**| true | true | |**false**| true | false | | XOR | true | false | | --- | --- | --- | |**true**| false | true | |**false**| true | false | #### 技術總結 1. 注意資料型態不同的變數不能做運算 2. 做題目記得，題目給的範圍不能超過你要用的資料型態範圍 3. 邏輯運算子要熟記結果 #### 課堂練習 [DanDanJudge ](http://203.64.191.163/) > a.014 > a.032 > a.035 --- ### if（判斷） - 預估上完的時間:第三週 - 講課:方旭誠 #### 課程內容 今天要教的是 `if` 顧名思義就是做一個假設 再用電腦驗證這個假設是否正確 並做出回應 其實如果要去解構一個程式 就是不停判斷、運算、儲存的過程 所以學習判斷雖簡單 卻至關重要 #### 判斷 先來簡單看看 `if` 的架構 ```cpp= if(判斷條件) { 程式碼...//當條件成立時執行 } else if(判斷條件) { 程式碼...//當if不成立才進行判斷 } else if(判斷條件) { 程式碼...//當上個else if不成立才進行判斷 } else { 程式碼...//當所有都不成立直接執行 } ``` 可以看到 在程式碼內的 `if` 是層層遞近的 先判斷最初的 `if` 是否成立 再一步步往下排查 值得注意的是 **`else if` 可以有多個** **但 `else` 卻能只有一個** 並且他們都必須在前面先有 `if` 的情況下才有效 而如果是使用多個 `if` 則每個 `if` 都會被判斷 互不干擾 就不如 `else if` 那樣只要其中之一成立 便不再判斷 #### 操作示範 接下來我們來試著使用 `if` 搭配之前的上課內容 來做一點簡單的使用示範 ```cpp= #include<iostream> using namespace std; int main() { int x; // 宣告變數 x cin >> x; // 輸入 x 的值 //判斷 x 與 0 的大小關係 if(x > 0) { cout << x << '>' << 0 << endl; } else if(x == 0) { cout << x << '=' << 0 << endl; } else { cout << x << '<' << 0 << endl; } return 0; } ``` 這裡面便運用到了宣告、輸入、判斷、關係運算、輸出 關於關係運算所用的運算子 在上一章節已有提及 而條件判斷除了 `if` 其實還有一種寫法 稱為三元條件運算子 在後面的章節會教給大家~ #### 多條件判斷 不知道大家是否還記得上一章教的邏輯運算子 如果善加利用的話可以達到一次判斷多個條件的效果喔 話不多說 上範例 ```cpp= //example #include<iostream> using namespace std; int main() { int n; cin >> n; if(n >= 0 && n % 4 == 0) // n大於0且為4的倍數 cout << n << endl; // if的指令僅一行時不用大括號 return 0; } ``` 可以看到我們同時判斷了兩個條件 當他們同時成立時才得以輸出 這就是邏輯運算子的應用 #### 技術總結 1. `if` 後的括號裡要放入判斷條件 2. 對於一個 `if`，`else if` 可以有很多個，`else` 只能有一個 3. 運用邏輯運算子做出複合判斷 #### 課堂練習 [DanDanJudge ](http://203.64.191.163/) > a.015 > a.020 > a.021 > a.022 > a.023 --- ### loop & mod (迴圈) - 預估上完的時間:第五週 - 講課:羅時瀚 #### 課程內容 這節課我們要教的是 loop & mod 也就是迴圈和取餘數 迴圈是一個非常重要的東西 它可以控制你的程式要重複執行多少遍 在C++中，有提供三種迴圈可以使用 分別是`for`、`while`、`do while` 其中`for`與`while`較常利用到 而取餘數應用不會那麼廣泛 不過在答案很大時 就會需要取餘數了！ #### for loop `for` 迴圈是最常運用到的迴圈 如果很清楚迴圈要重複執行的次數就可以使用 `for` 迴圈 ```cpp= for (設定迴圈初值; 判斷條件; 設定變化量) { 迴圈主體; // 重複執行的地方 } // 大括號後面不用加分號 ``` 以下為 `for` 迴圈執行的流程 1. 首次進入 `for` 迴圈，設定`迴圈控制變數`的初始值 2. 判斷是否要執行迴圈，當條件判斷值為`true`時，繼續執行`迴圈主體`；反之，若為`false`，則跳出迴圈 3. 執行完`迴圈主體`以後，`迴圈控制變數`會根據`設定變化量`，去更改`迴圈控制變數`的值，再重新執行步驟2 ```flow st=>operation: 設定迴圈初值 cond=>condition: 判斷條件 op=>operation: 迴圈主體 op3=>operation: 跳出迴圈 op2=>operation: 設定增減量 st->cond cond(false)->op3 cond(true)->op->op2(left)->cond ``` 如果我們要計算1加到100的話，就可以用```for```迴圈 ```cpp= int sum = 0; for (int i = 0; i <= 100; i++) { sum += i; } ``` 其實上面的東西很像數學的一個東西 \begin{equation} {sum = \sum^{100}_{i=1} i} \end{equation} 然後可能會有人好奇為什麼`i`要從```0```開始，而不是```1``` 因為有部份情況用到for迴圈時 我們需要搭配到陣列(下章會提) 就習慣將for迴圈的初始值定為```0``` 當然可以自己決定 沒有強迫 #### while loop ```while```迴圈也算很常用的迴圈 有時候我們會不知道迴圈要重複執行多少次 就可以考慮```while```迴圈或 ~~```do while```迴圈~~ ```cpp= 迴圈控制變數; while (判斷條件) { 迴圈主體; 設定增減量; } // 大括號後面不用加分號 ``` 1. 首次進入 `while` 迴圈前，設定`迴圈控制變數`的初始值 2. 檢查判斷條件的內容，當條件判斷值為`true`時，繼續執行`迴圈主體`；反之，若為`false`，則跳出迴圈 3. 執行完`迴圈主體`以後，`迴圈控制變數`會根據`設定增減量`，去更改`迴圈控制變數`的值，再重新執行步驟2 ```flow st=>operation: 設定迴圈初值 cond=>condition: 判斷條件 op=>operation: 迴圈主體 op3=>operation: 跳出迴圈 op2=>operation: 設定增減量 st->cond cond(false)->op3 cond(true)->op->op2(left)->cond ``` 如果我們要計算1加到n，我們也可以用```while```迴圈 ```cpp= int n, i = 1, sum = 0; cin >> n; while (i <= n) { sum += i; i++; } ``` #### do while loop `do while`迴圈也是用在不知道重複執行迴圈次數時 不過`do while`迴圈是「先做再說」 這個迴圈是最少用到的 ```cpp= 迴圈控制變數; do { 迴圈主體; 設定增減量; } while (判斷條件); // 記得要加分號 ``` 1. 首次進入 `do while` 迴圈前，設定`迴圈控制變數`的初始值 2. 先執行`迴圈主體`，再檢查判斷條件的內容，當條件判斷值為`true`時，繼續執行`迴圈主體`；反之，若為`false`，則跳出迴圈 3. 執行完`迴圈主體`以後，`迴圈控制變數`會根據`設定增減量`，去更改`迴圈控制變數`的值，再重新執行步驟2 ```flow st=>operation: 設定迴圈初值 op=>operation: 迴圈主體 op3=>operation: 跳出迴圈 op2=>operation: 設定增減量 cond=>condition: 判斷條件 st->op->op2->cond cond(false)->op3 cond(true)(left)->op ``` `do while`迴圈實在是太少用了，所以我就不加上範例了 :poop: #### break & continue ```break``` 其實也是我們很常用的東西 是用來搭配迴圈的 如果我們在迴圈裡做到某件以達成我們需要做的事時 就可以在之後打上```break``` 那就會直接跳出迴圈 以免增加時間或記憶體 甚至造成無限迴圈 以```while```為例 ```flow st=>operation: 設定迴圈初值 cond=>condition: 判斷條件 op=>operation: 迴圈主體 op3=>operation: 跳出迴圈 op2=>operation: 設定增減量 cond2=>condition: break op1=>condition: 跳出迴圈 st->cond cond(false)->op3 cond(true)->op->cond2(true)->op2(left)->cond cond(true)->op->cond2(false)->op1 ``` ```cpp= int ans = 0; unsigned int a; for (int i = 0; i < 100000; i++) { cin >> a; ans += a; if (ans > 100) { cout << "answer is more than 100\n"; break; } } ``` 像這裡我們要判斷ans有沒有超過100 如果超過了 ans不管如何都還是會超過100 就沒有做下去的意義 那就可以直接用break -- ```continue```是比較少用到 但還是要學 ```continue```會略過迴圈剩下的部分 進行下一次的迴圈 以```while```為例 ```flow st=>operation: 設定迴圈初值 cond=>condition: 判斷條件 op=>operation: 迴圈主體 op3=>operation: 跳出迴圈 op2=>operation: 設定增減量 cond2=>condition: continue st->cond cond(false)->op3 cond(true)->op->cond2(true)->op2(left)->cond cond(true)->op->cond2(false)->cond ``` 我想不到範例code 有用到再說 :poop: #### mod mod，又名模除，符號記做`%` 是一個很好用的東西 簡單來說就是取餘數 就是國小算除法時 ```被除數 / 除數 = 商數 ... 餘數``` 的餘數 ```cpp= int a = 5; double b = 5; int c = 2; cout << a / c << '\n'; // 2 cout << b / c << '\n'; // 2.5 cout << a % c << '\n'; // 1 ``` 它可以應用在判斷奇偶數中 ```cpp= int n; cin >> n; if (n % 2 == 1) cout << "n is an odd number." else if (n % 2 == 0) cout << "n is an even number." ``` 然後寫到後面的題目 ~~ex:期中考~~ 就有可能要你把答案```mod 1e9 + 7``` 原因是因為 1. 它是一個很大的質數且小於 $2^{30}$ 2. 將兩個 ```mod 1e9 + 7``` 的數相加會在```int```的範圍 3. 將兩個 ```mod 1e9 + 7``` 的數相乘會在```long long```的範圍 再來講一些```mod```的運算 - ($a \;mod \;n) \;mod\; n = a \;mod \;n$ - $n^x \;mod \;n = 0$ - $(a + b)\; mod \;n = [(a\; mod \;n) + (b \;mod\; n)]\; mod\; n$ - $a*b \;mod\; n = [(a\; mod\; n)*(b\; mod \;n)]\; mod\; n$ - #### 技術總結 1. `for`迴圈的小括弧中間是用`;`間隔 2. `for`跟`while`迴圈後面不要加`;` 3. `while`迴圈裡面記得加上可以更改`迴圈控制變數`的程式碼 4. ```break```有時候很必須，記得要會用 #### 課堂練習 [DanDanJudge ](http://203.64.191.163/) > a.020 > a.023 > a.191 > a.192 --- ### array( 陣列 ) - 預估上完的時間:第六週 - 講課:方旭誠 #### 課程內容 這堂課要教的是陣列 陣列是一個能用單一資料型態存儲多個資料的容器 讓你免於宣告太多變數 而陣列搭配迴圈也有奇效喔！ #### 宣告陣列 首先來觀察一個陣列的圖示 | arr[4] | `empty` | `empty` | `empty` | `empty` | | --- | --- | --- | --- | --- | | 編號 | arr[0] | arr[1] | arr[2] | arr[3] | 當我們宣告一個陣列時 就會如上方的示意圖一樣 在電腦產生一串連續的存放空間 具體的宣告方式是 ```cpp= int arr[4]; // 以 int 型態宣告一個名為 arr，共 4 格的陣列 ``` > **注意** > 在中括號裡的數字可以是變數 此時陣列中還只是殘值(亂碼) 我們可以選擇從宣告時就指定裡面的內容 或是在後續程式中存入內容 這裡先示範事先指定的方法 ```cpp= //example int arr[4] = {3, 5, 6, 4} ``` 陣列內部現在變成如下的樣子 | arr[4] | 3 | 5 | 6 | 4 | | --- | --- | --- | --- | --- | | 編號 | arr[0] | arr[1] | arr[2] | arr[3] | #### 更改內容 那如果後續要更改怎麼辦呢？ 要知道 陣列雖然是一串連續的資料 但他的每一格是分開處理的 所以當要指定某一格做出操作時 就要用到他的編號了 在開始操作前要先了解到 **陣列的編號由 `0` 開始** 所以一個 `n` 格的陣列 最後一格的編號是 `n-1` 呦 接下來便實際操作陣列的指定修改吧 ```cpp= #include<iostrem> using namespace std; int main() { int arr[4] = {3, 5, 6}; // 只先宣告三個 arr[3] = 4; // 指定第四格的值為 4 } ``` 以上是陣列的指定修改 非常直覺與簡單 但當今天有未知或超多筆數的資料要存入陣列呢？ 因為前面有說陣列每格是單獨處理的 這樣每格一個指令去修改太沒效率了 我們可以運用陣列編號累加的特性搭配迴圈達到這個目的！ #### 陣列與迴圈 記得 `for` 迴圈每執行一遍參數就會產生一次變化嗎 如果將這個規律對應陣列的編號 就能用短短幾行程式掃過陣列每一格了 上範例！ ```cpp= // 連續輸入 int n; cin >> n; int arr[n]; // 用變數決定陣列大小 for(int i = 0; i < n; i++) { cin >> arr[i]; // 用 i 的變動性跑完陣列每一格 } ---分隔線--- // 連續輸出 for(int i = 0; i < n; i++) { cout << arr[i] << endl; } ``` 這樣就能輕輕鬆鬆的對每格陣列做出處理了 因此在接下來的題目裡 迴圈搭配陣列會是很常見的用法喔！ #### 多維陣列 當今天變數後的中括號不只一個時 就可以建構出多維陣列 在這先示範如何宣告 ```cpp= int arr[2][3]; // 宣告一個 2*3 的陣列 ``` 這時陣列長這樣 | 編號 | arr[x][0] | arr[x][1] | arr[x][2] | | --- | --- | --- | --- | | **arr[0][y]** | | | | | **arr[1][y]** | | | | 就猶如一維陣列一樣 可以透過任意一格的編號來對其進行操作 不過要記得第一格是橫行的編號 第二格是直列的編號 想當然 更高維的陣列就更加複雜了 四維更是只存在於想像中 因此在這裡僅做提及 #### 技術總結 1. 陣列編號由 `0` 開始 2. 每格陣列都可以被單獨指定與操作 3. 陣列搭配迴圈可以使操作效率許多 #### 課堂練習 [DanDanJudge ](http://203.64.191.163/) > a.188 > a.203 > a.233 > a.372 --- ### string - 預估上完的時間:第八週 - 講課:羅時瀚 #### 課程內容 今天要說的是string，它有以下幾點特點 - string型別支援長度可改變的字元陣列 - 提供大量的函式 - 屬於C++ STL容器庫 - 使用string的程式必須先引入函數庫 ```#include <string>``` #### 定義 string 並初始化 ``` cpp= string str1; // str1將會是個空字串 cout << str1 << '\n'; // string str2 = "Fudan"; // 把str2初始化為字串字面常數的副本 cout << str2 << '\n'; // Fudan string str3("Fudan"); // 把str3初始化為字串字面常數的副本 cout << str3 << '\n'; // Fudan string str4(str3); // 把str4初始化為str3的副本 cout << str4 << '\n'; // Fudan string str5(5, 'f'); // 把str5初始為5個f cout << str5 << '\n'; // fffff ``` 其實幾乎只會用到第一種跟第二種 :poop: #### 讀入 string ``` cpp= string str1, str2, str3; cin >> str1; // 把「以空白分隔的或換行」字串讀入str1 getline(cin, str2); // 把一整行字串讀入str2 cin.get(str3); // 把一格字元讀入str3 ``` 造成getline()返回的那個換行字元會被捨棄 不會儲存在string #### 字串陣列 因為字串像是陣列一樣存取 所以也可以利用下標取得特定值 ``` cpp= string str = "fudan"; cout << str[0] << '\n'; // 'f' cuot << str[2] << '\n'; // 'd' ``` #### string 的常用函式 - str.empty(): 測試字串是否為空 ``` cpp= string str; cout << (str.empty() ? "yes" : "no") << '\n'; // yes ``` - str.size(): 傳回字串長度 ``` cpp= string str = "Fudan"; cout << str.size() << '\n'; // 5 ``` - str.length(): 傳回字串長度 ``` cpp= string str = "Fudan"; cout << str.length() << '\n'; // 5 ``` - str.find("fd"): 傳回字串fd在str的位置 ``` cpp= string str = "i dont like fd fd"; cout << str.find("fd") << '\n'; // 12 cout << str.find("fd", 13) << '\n'; // 15 cout << str.find("Fd") << '\n'; // 18446744073709551615 ``` $\;\;\;\;\;\;\;$這裡因為字串中沒有"Fd" $\;\;\;\;\;\;\;$則會輸出string::npos $\;\;\;\;\;\;\;$而npos是指這個容器的最大容量 $\;\;\;\;\;\;\;$用來表示不存在的位置 - str.clear(): 清空str ``` cpp= string str = "fudan"; str.clear(); cout << (str.empty() ? "yes" : "no") << '\n'; // yes ``` - str1.swap(str2): 把str1與str2交换 ``` cpp string str1 = "f", str2 = "d"; str1.swap(str2); cout << str1 << ' ' << str2 << '\n'; // d f ``` - str[n] = toupper(str[n]): 將指定字元轉為大寫字母，若非英文字母則不處理 ``` cpp= string str = "fudan"; str[0] = toupper(str[0]); cout << str << '\n'; // Fudan ``` - str[0] = tolower(str[0]): 將指定字元轉為小寫字母，若非英文字母則不處理 ``` cpp= string str = "FUDAN"; str[0] = tolower(str[0]); cout << str << '\n'; // fUDAN ``` #### ASCII碼 前面提過字串像是陣列一樣存取，而每格都以ASCII碼的格式存取 1. 大寫英文字母A ~ Z (65 ~ 90) 2. 小寫英文字母a ~ z (97 ~ 122) 3. 數字0 ~ 9 (48 ~ 57) ![](https://i.imgur.com/fHoMLt8.png) 因此可以用來 1. 字元轉成整數 2. 整數轉成字元 3. 判斷字元內容是大寫英文字母、小寫英文字母、數字或其他 4. 轉換字元英文大小寫 可以結合前面講過的字串陣列 ``` cpp= string str1 = "F", str2 = "FuDan"; int a = 68; cout << (int)str1 << '\n'; // 70 cout << (char)a << '\n'; // D for (int i = 0; i < str2.length(); i++) cout << (int)str2[i] << ' '; // 70 117 68 97 110 ``` #### 技術總結 1. `string` 的用法、運用地方十分廣泛，一定要學好 2. `getline(cin, str)`是用在要讀入一個字串，但中間有空格時 3. `字串陣列`也是從`0`開始 4. 每個函數都要記住使用方法 5. `ASCII碼`可以只記`0`、`A`、`a`的，剩下自己去推敲 #### 課堂練習 [DanDanJudge ](http://203.64.191.163/) > a.001 > a.007 > a.012 > a.013 > a.188 > a.199 > a.261 > a.423 ### bubble sort (氣泡排序法) - 預估上完的時間:第九週 - 講課:方旭誠 #### 課程內容 今天上的是排序法 顧名思義就是將數字或文字進行排序 以呈現由大到小或由小到大的分布 這章節的內容牽引了許多進階語法的基礎 因此相當重要 #### 原理 排序法為了讓數列採取規律排序 因此會需要不斷的比較兩者的大小 再進行交換 因此會需要一個陣列來儲存一連串資料 再來需要一個迴圈掃過陣列的每一格 以及一個判斷如何交換的標準 這就是泡沫排序法的基本架構 #### 基本架構 因為泡沫排序法較難用文字描述其概念 因此直接上最基本的程式碼 ```cpp= #include<iostream> using namespace std; int main() { int n = 10, tmp; // 宣告陣列大小和暫存變數 int arr[n] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; for(int i = 0; i < n; i++) { // 陣列共有n格 for(int j = 0; j < n-1; j++) { // 判斷每一格大小關係 if(arr[j] > arr[j+1]) { // 如果前比後小就交換 tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } // 最後陣列為 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} return 0; } ``` 這樣應該不難理解這是一個將數列由**小排到大**的程式 但其中的程式碼卻略顯繁雜 而且存在著效率的問題 因此我們馬上要看到如何優化它 #### 優化 首先要處理的是中間交換部份的問題 `C++` 其實提供了一個實用的函式給我們 用法如下 ```cpp= swap(前一格編號, 後一格編號); ``` 他可以用於交換順序 將中間三行的功能替代掉 接著處理效率問題 仔細想會知道 其實有些格子是已經在前面被判斷過與交換過了 所以我們應該在程式碼 透過修改運行邏輯來忽略已判斷部分 並加上可自行定義的範圍 最後整合出最精簡的版本 ```cpp= #include<iostream> using namespace std; int main() { int n; while(cin >> n) { int arr[n]; for(int i = 0; i < n; i++) cin >> arr[i]; for(int i = n-1; i > 0; i--) for(int j = 0; j <= i-1; j++) if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]); } return 0; } ``` 這便是最終的版本了 但不幸的是 `C++`其實還提供了一個函式可以概括~~氣泡~~排序法的整個流程 :::spoiler `進階教學有話要說` 欸欸這排序法不是氣泡排序喔， 它是由 `quick sort` 和 `heap sort` 組合起來的， 有興趣可以去查查看喔！ ::: #### sort 函式 ```cpp= #include<algorithm> // 要先引入這個函式庫 sort(初始位置, 末位置+1); ``` 這個函式只要放入陣列的參數 就能將它**由小到大**排列完畢 當然它有別種排序邏輯可供調整 在這裡先賣個關子 總之如果使用了 `sort` 程式碼會縮短成 ```cpp= #include<iostream> #include<algorithm> using namespace std; int main() { int n; while(cin >> n) { int arr[n]; for(int i = 0; i < n; i++) cin >> arr[i]; sort(arr, arr + n); } return 0; } ``` 相當的精簡 精簡到我不知怎麼描述了 不過程式的領域博大精深 比`sort`還快的排序法比比皆是 因此學好基礎觀念才是王道 不要濫用方便的函式就失去了學習的動力 #### 技術總結 1. 排序的核心就是比較與交換 2. 學好排序必須觀念紮實，不要好逸惡勞 3. **DanDanJudge上關於sort的題目通常是毒瘤** :poop: #### 課堂練習 [DanDanJudge ](http://203.64.191.163/) > a.083 > a.208 > a.248 --- ### 函式&遞迴 :::spoiler `進階教學有話要說` 函式不一定是遞迴，遞迴一定是函式。 ::: - 預估上完的時間:第十週 - 講課:羅時瀚 #### 課程內容 C++裡面有很多函式了，其實大多是有人去寫並加入進去的 當然，如果你在一個程式裡有要一直重複的動作，也可以把它寫成函式 今天就要教大家怎麼自訂函式還有遞迴 #### 函式 在自訂函式之前，有幾件事需要先了解 - 參數:函式的輸入 - 回傳值:函式的輸出 - 宣告函式在```using namespace std;```之下、```int main()```之上 - 函式一旦執行到```return```，就會立刻回傳，略過之後所有程式碼 - 函式有分為兩種類型:```有回傳值```、```無回傳值``` 宣告函式的格式如下 ```cpp= #include <bits/stdc++.h> using namespace std; //有回傳值 資料型態 函式名稱 (變數1的資料型態 變數1的名稱, 變數2的資料型態 變數2的名稱...) { //do anything you want return 回傳值; } //無回傳值 void 函式名稱 (變數1的資料型態 變數1的名稱, 變數2的資料型態 變數1的名稱...) { //do anything you want } int main () { //your code } ``` **前面雖然說宣告函式在```using namespace std;```之下、```int main()```之上 但只要先宣告函式，函式主體就可以寫在```int main()```之下** ```cpp= #include <bits/stdc++.h> using namespace std; void 函式名稱 (變數1的資料型態, 變數2的資料型態...); int main () { //your code } void 函式名稱 (變數1的資料型態 變數1的名稱, 變數2的資料型態 變數2的名稱...) { //do anything you want } ``` 範例(有回傳值) ```cpp= #include <bits/stdc++.h> using namespace std; int add(int x, int y) { return (x + y); } int main () { int a, b; while (cin >> a >> b) { int ans = add(a, b); cout << ans << '\n'; } } ``` 範例(無回傳值) ```cpp= #include <bits/stdc++.h> using namespace std; void hw() { cout << "hello, world" << '\n'; } int main () { int n; cin >> n; while (n--) { hw(); } } ``` #### 遞迴 接下來要講的是遞迴 遞迴最大的特性就是 1. 在函式中使用函式自身 2. 通常有終止條件 一般來說，終止條件就是```return``` 不知道大家有沒有聽過```費式數列``` 就是```1.1.2.3.5.8.13.21...``` 其中我們可以知道 $\begin{cases} f(0) = 1 \\ f(1) = 1 \\ f(n) = f(n - 1) + f(n - 2) & n \geq 2 \end{cases}$ 那如果我們要求$f(4)$ 就可以先去求$f(3)$和$f(2)$ 要求$f(3)和f(2)$ 我們可以從$f(0)和f(1)$推敲 ```cpp= #include <bits/stdc++.h> using namespace std; int f(int n) { if (n == 0 || n == 1) return 1; else return f(n - 1) + f(n - 2); } int main () { int n; while (cin >> n) cout << f(n) << '\n'; } ``` 那如果沒有回傳值的話 就直接在適當的位置加上```return``` 就會回朔到上一次的遞迴 遞迴在之後的演算法可能會很常用到 像是DFS、TREE 都會用到 不過真的沒什麼範例 等真正用到的時候應該可以更加理解 這裡我還是丟一小段我寫DFS的code來解說一下 ```cpp= void findQ (int y) { for (int i = 0; i < n; i++) { if (check (i, y)) { vec[y] = i; if (y == n - 1) { if (flag2) cout << '\n'; else flag2 = true; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (j == vec[i]) cout << "Q"; else cout << "_"; } cout << '\n'; } ans++; return; } else findQ (y + 1); } } } ``` #### 技術總結 1. 要注意哪時要有回傳值，哪時要用```void``` 2. 如果要將函式主體寫在```int main()```之下，那記得一開始宣告只要打資料型態，不用打變數名稱 3. 演算法會很頻繁的用到函式，不過現在真的沒甚麼範例 #### 課堂練習 [DanDanJudge ](http://203.64.191.163/) 我找不到練習 :poop: ------------ ## 下學期 ### vector - 預估上完的時間:第一週 - 講課:羅時瀚 #### 課程內容 其實```vector```有點類似```array``` 像是```array```可以存```string```，```vector```也可以 只是```vector```的容量比```array```大 而```vector```可以做的事也更多 舉例來說，可以：新增或移除元素、取得長度(雖然應該array也可以)...... #### 宣告 那先來舉例```vector```如何宣告 ```cpp= vector <資料型態> 名稱(長度); vector <int> vec(5); ``` 當然，也可以不用宣告長度 ```cpp= vector <int> vec; ``` #### 函式 1. 存取 - 就像array一樣 ```cpp= vector <int> vec(5); for (int i = 0; i < 5; i++) vec[i] = i; ``` 2. 新增或移除 - vec.push_back() 新增元素至 vector 的尾端，不過因為要改變記憶體，所以會比一般存取還耗時間 ```cpp= vector <int> vec(5); for (int i = 0; i < 5; i++) vec[i] = i; int n = 5; vec.push_back(n); for (int i = 0; i < vec.size(); i++) cout << vec[i] << ' '; ``` :::info output : 0 1 2 3 4 5 ::: - vec.pop_back() 刪除 vector 最尾端的元素 ```cpp= vector <int> vec(5); for (int i = 0; i < 5; i++) vec[i] = i; vec.pop_back(); for (int i = 0; i < vec.size(); i++) cout << vec[i] << ' '; ``` :::info output : 0 1 2 3 ::: - vec.clear() 清空 vector 裡所有的元素 3. 取得長度 - vec.size() 取得 vector 目前的長度 ```cpp= vector <int> vec; for (int i = 0; i < 3; i++) vec.push_back(i); cout << vec.size() << '\n'; ``` :::info output :3 ::: 4. 迭(ㄉ一ㄝˊ)代 ( iterator ) - vec.begin() 回傳一個 iterator，指向vector的第一個元素 - vec.end() 回傳一個 iterator，指向vector的最後一個元素的下一位 ```cpp= vector <int> vec(5); for (int i = 0; i < 5; i++) cin >> vec[i]; sort (vec.begin(), vec.end()); ``` #### 技術總結 1. vector真的很好用，我學會之後就很少用array了 2. 新增元素的方式要記得，對你們應該是很陌生的 3. 宣告長度是用```（）```，不像array是用```[]``` #### 課堂練習 [DanDanJudge](http://203.64.191.163/) > a589 ### 二分搜 (Binary Search) 二分搜顧名思義就是將東西分成兩份，然後再搜尋 不過前提當然是要先將```array``` ```sort```一遍 試玩一次範例 `code` 應該就懂了 1. 先設 `l, r`，代表搜尋的左界跟右界 2. `mid`就是中位數 3. 搜尋的數字比中位數大，`l = mid + 1` 4. 搜尋的數字比中位數小，`r = mid - 1` :::spoiler `code` ```cpp= #include <bits/stdc++.h> using namespace std; int main () { int n; cin >> n; int arr[n]; for (int i = 0; i < n; i++) cin >> arr[i]; sort (arr, arr + n); int m; while (cin >> m) { int l = 0, r = n - 1; while (l < r) { int mid = (l + r) / 2; if (m > arr[mid]) l = mid + 1; else if (m < arr[mid]) r = mid - 1; else if (m == arr[mid]) { cout << mid + 1 << '\n'; break; } if (m == arr[l]) cout << l + 1 << '\n'; else cout << "404 not found\n"; } } ``` ::: #### 技術總結 1. 二分搜在一些檢定很常考，還蠻重要的 2. 記得要先排序好數列再二分搜 #### 課堂練習 [DanDanJudge](http://203.64.191.163/) > a702 **(其實這一題偏難，練習好基礎的可以來想想看這一題)**