高二進階程式設計 - 課程補充

[TOC] --- ## 課程補充資料 #### 2-1 函式 > 將陣列傳到函式內 ```cpp! int total(int arr[], int n) { int summ=0; for(int i=0; i<n; i++) { summ += arr[i]; } return summ; } int main() { int a[5] = {1, 2, 3, 4, 5}; cout<< total(a, 5); } ``` #### 2-2 遞迴函式 - [Recursion Visualizer](https://recursion.vercel.app/) - [Hanoi Tower ![](https://i.ytimg.com/vi/8XQmuPKOgy8/hq720.jpg =350x)](https://www.youtube.com/watch?v=8XQmuPKOgy8) ```cpp! void Hanoi(char From, char Buff, char To, int disk) { if(disk == 1) { cout<< "move " << From << " -> " << To<< endl; } else { Hanoi(From, To, Buff, disk - 1); Hanoi(From, Buff, To, 1); // cout<< "move " << From << " -> " << To<< endl; Hanoi(Buff, From, To, disk - 1); } } // Hanoi('A', 'B', 'C', 3); ``` #### 3-1 指標、參考 - 指標 (pointer) ```cpp! int a; int *ptr_a; // 宣告指標 ptr_a = &a; // & 變數 -> 取位址 *ptr_a = 5; // * 位址 -> 取變數(並修改) // 對 *ptr_a 的修改，也會影響到變數 a ``` - 參考 (reference) ```cpp! int a; int &ref_a = a; // 宣告參考、連結到 a 變數 ref_a = 5; // 直接修改到 a 的值 ``` #### 3-4 多維陣列 - 陣列 & 函式 ```cpp! void show_1D(int arr[], int n) { for(int i=0; i<n; i++) cout<< arr[i]<< " "; cout<< endl; } // arr[][100] <- 第二格必填、且不能是變數 void show_2D(int arr[][100], int m, int n) { for(int i=0; i<m; i++) { for(int j=0; j<n; j++) { cout<< arr[i][j]<< " "; } cout<< endl; } } void show_another_2D(int arr[][100], int m, int n) { for(int i=0; i<m; i++) { show_1D(arr[i], n); // 可以把 arr[i] 視為一個一維陣列 } } int main() { int arr_1d[10] = {}, arr_2d[50][100] = {}; show_1D(arr_1d, 10); show_2D(arr_2d, 50, 100); } ``` - 無限制長度陣列 `vector` ::: spoiler 展開 ```cpp= #include <iostream> #include <vector> // 需要引入函式庫才能使用 using namespace std; int main() { vector<int> arr; // 宣告一維陣列，int 型態，"長度為 0" /* 填入資料 */ arr.push_back(123); // 填入一筆資料 123 arr.push_back(456); // 在陣列最後填入新數字 456 // 目前狀態: arr[0]: 123, arr[1]: 456 for (int i=0; i<5; i++) { int a; cin>> a; arr.push_back(a); // 將 5 個數字輸入並儲存至 arr } /* 查看大小 */ cout<< arr.size()<< endl; // 目前 arr 長度為 7 /* 顯示全部資料 */ for(int i=0; i<arr.size(); i++) { cout<< arr[i]<< " "; } // cout 123 456 ...五個輸入的數字 } ``` > 常犯的錯誤 ```cpp!= int main() { vector<int> arr; cout<< arr[0]; // ERROR: 目前 arr 長度為 0，無法存取 } ``` > 特別的初始化方式 ```cpp= int main() { vector<int> arr(10, 2); // 初始化長度為 10，資料為 2 的 int 陣列 // 使用陣列，宣告 10 個 vector，每個 vector 長度為 0 vector<int> arr_2d[10]; // 使用 vector 宣告 10 個 vector，每個 vector 長度為 0 vector< vector<int> > arr_2dd(10); // 使用 vector 宣告 10 個 vector，每個 vector 長度為 20，並初始值為 5 // 這也可以拿來用在宣告二維陣列 vector< vector<int> > arr_2ddd(10, vector<int> (20, 5)); } ``` > 再更延伸一些，傳遞函式時，vector 與傳統陣列的差異 ```cpp= void reset_arr_1(int arr[], int n) { for(int i=0; i<n; i++) { arr[i] = 0; } } void reset_vec_1(vector<int> arr) { // 不用傳遞 n，因為 arr.size() 就是長度 for(int i=0; i<arr.size(); i++) { arr[i] = 0; } } void reset_vec_2(vector<int> &arr) { // 從 reset_vec_1 微調輸入部分 for(int i=0; i<arr.size(); i++) { arr[i] = 0; } } int main() { int arr[5] = {1, 2, 3, 4, 5}; vector<int> vec(5, 123); // 長度為 5 資料為 123 reset_arr_1(arr, 5); // 可以清空 arr reset_vec_1(vec); // 無法清空 vec // 所以要用第二個版本，有點類似傳遞指標的概念，使用這個叫 reference 的東西 // void reset_vec_2(vector<int> &arr) reset_vec_2(vec); // 可以清空 vec } ``` ::: #### 3-3 Linked List - [Slides](https://slides.com/oscarsslides/linked-list) #### 3-5 字串 [ASCII: 文字編碼](https://upload.wikimedia.org/wikipedia/commons/1/1b/ASCII-Table-wide.svg) - recap: ```c++! char c = 'a'; if(c == 'a') // true if(c == "a") // Compiled Error if(c < 'c') // true ``` ```cpp! char c; cin>> c; if('a' <= c && c <= 'z') {} // 抓小寫英文 if('0' <= c && c <= '9') {} // 抓數字 sum += c - '0' // 計算數字 ``` - c++ string 讀整行 (連空格都吃) ```c++! string s; getline(cin, s); ``` #### 4-1 堆疊 - [後序運算](https://ithelp.ithome.com.tw/articles/10244316) #### 5-1 演算法分析 - 時間複雜度 - [不同排序法的效能差異](https://www.youtube.com/watch?v=BeoCbJPuvSE) - [Desmos - Time Complexity](https://www.desmos.com/calculator/zpzzboy6sz?lang=zh-TW) #### 5-2 排序 - [視覺化排序流程](https://visualgo.net/zh/sorting) #### 5-4 窮舉稍微微調了一下課本的 permutation :::spoiler permutation ```cpp= #include <iostream> using namespace std; // 輸出陣列內容 void print(int arr[], int n) { for(int i=0; i<n; i++) { cout<< arr[i]<< " "; } cout<< endl; } // 檢查 target 有沒有在 arr[0~n-1] 出現 bool exists(int arr[], int n, int target) { for(int i=0; i<n; i++) { if(arr[i] == target) { return true; } } return false; } void permutation(int arr[], int n, int place) { if(n == place) { print(arr, n); return ; // 離開函式 } // else for(int i=0; i<n; i++) { // 試圖在 arr[ place ] 填入 i if(exists(arr, place, i) == false) { arr[place] = i; permutation(arr, n, place + 1); // 繼續往後填寫 (place+1) } } } int main() { int arr[5] = {}; permutation(arr, 5, 0); // 陣列, 長度, 從哪開始填寫 } ``` ::: 如果還是理解困難的話，可以看看程式是如何變這樣的 :::spoiler 單純的 combination ```cpp= for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { for(int k=0; k<n; k++){ cout<< i<< " "<< j<< " "<< k<< endl; } } } ``` ::: - 變陣列版本 :::spoiler combination + array ```cpp= void print(int arr[], int n) { for(int i=0; i<n; i++) { cout<< arr[i]<< " "; } cout<< endl; } int main() { int n=3, arr[3] = {}; int to_fill; // 填在哪一格 for(int i=0; i<n; i++) { to_fill = 0; arr[to_fill] = i; for(int j=0; j<n; j++) { to_fill = 1; arr[to_fill] = j; for(int k=0; k<n; k++){ to_fill = 2; arr[to_fill] = k; print(arr, n); } } } } ``` ::: - 再將重複的層層迴圈，塞到遞迴中 :::spoiler combination + array + recursion ```cpp= void print(int arr[], int n) { for(int i=0; i<n; i++) { cout<< arr[i]<< " "; } cout<< endl; } void combination(int arr[], int n, int to_fill) { if(n == to_fill) { print(arr, n); return ; } // else for(int i=0; i<n; i++) { arr[to_fill] = i; combination(arr, n, to_fill + 1); } } int main() { int n=3, arr[3] = {}; combination(arr, n, 0); } ``` ::: 這樣應該就可以理解了 (? premutation 就是不能重複的 combination 而已 #### 6-3 八皇后 > 從 permuatation 再往後延伸，斜線不衝突 `conflict` :::spoiler 八皇后 ```cpp= #include <iostream> using namespace std; int max_score = 0; void print(int arr[], int n) { for(int i=0; i<n; i++) { cout<< arr[i]<< " "; } cout<< endl; } // 檢查 target 有沒有在 arr[0~n-1] 出現 bool exists(int arr[], int n, int target) { for(int i=0; i<n; i++) { if(arr[i] == target) { return true; } } return false; } // 斜線衝突 bool conflict(int arr[], int to_fill, int i) { for(int j=0; j<to_fill; j++) { if( abs(to_fill - j) == abs(i - arr[j]) ) { return true; } } return false; } void combination(int arr[], int n, int to_fill) { if(n == to_fill) { print(arr, n); return ; } // else for(int i=0; i<n; i++) { // to_fill == 2 if(exists(arr, to_fill, i)) { // [0, 1, ?] continue; } if(conflict(arr, to_fill, i)) { continue; } arr[to_fill] = i; combination(arr, n, to_fill + 1); } } int main() { int n=8, arr[8] = {}; combination(arr, n, 0); } ``` ::: #### 6-4 動態規劃 [簡報2 ![image](https://hackmd.io/_uploads/By9h5cKZgg.png =500x)](https://slides.com/oscarsslides/the-coin-questions) #### 4-3 & 6-5 樹狀結構 ![image](https://hackmd.io/_uploads/SyAuoTBB1e.png =500x) `from https://app.smartdraw.com/` | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | x | - | + | + | 3 | x | 1 | 3 | 4 | | | 2 | 3 | | | ``` string tree = " x-++3x134 23 "; // length: 16 index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 value: x - + + 3 x 1 3 4 2 3 ``` :::spoiler 規律 ![image](https://hackmd.io/_uploads/Hy2SC32fgl.png =200x) ::: :::spoiler 二元樹視覺化函式 (幫助 DEBUG) ```cpp= #include <iostream> #include <iomanip> #include <cmath> using namespace std; void show(int tree[], int maxLevel) { int nodeWidth = 2; // 節點寬度 int index = 1; // 1-indexed for (int level = 1; level <= maxLevel; ++level) { int numNodes = pow(2, level - 1); // 該層節點數 int spaceBetween = pow(2, maxLevel - level + 1); // 節點間距 int initialSpace = spaceBetween / 2; // 前置空格 cout << string(initialSpace * nodeWidth, ' '); for (int i = 0; i < numNodes; ++i) { cout << setw(nodeWidth) << tree[index++]; // 節點之間的空格 cout << string((spaceBetween * nodeWidth) - nodeWidth, ' '); } cout << endl << endl; // 每層空一行 } } ``` 用法 ```cpp= int tree[32]; show(tree, 4); // 顯示 4 層 ``` ::: :::spoiler 二元樹走訪 [後序運算](https://ithelp.ithome.com.tw/articles/10244316) ``` pre-order : x-+343 +x231 post-order: 34+3- 23x1+x inorder : 3+4-3x 2x3+1 ``` ::: #### Heap [視覺化](https://visualgo.net/en/heap) :::spoiler Heap 範例 Code https://visualgo.net/en/heap ```cpp= #include <iostream> #include <iomanip> #include <cmath> using namespace std; void show(int tree[], int maxLevel) { int nodeWidth = 2; // 節點寬度 int index = 1; // 1-indexed for (int level = 1; level <= maxLevel; ++level) { int numNodes = pow(2, level - 1); // 該層節點數 int spaceBetween = pow(2, maxLevel - level + 1); // 節點間距 int initialSpace = spaceBetween / 2; // 前置空格 cout << string(initialSpace * nodeWidth, ' '); for (int i = 0; i < numNodes; ++i) { cout << setw(nodeWidth) << tree[index++]; // 節點之間的空格 cout << string((spaceBetween * nodeWidth) - nodeWidth, ' '); } cout << endl << endl; // 每層空一行 } } int heap_top(int heap[]) { return heap[1]; } void heap_push(int heap[], int n, int value) { // 1 ... n int pos = n + 1; heap[pos] = value; while(pos != 0 && heap[pos] < heap[pos/2]) { swap(heap[pos], heap[pos/2]); pos = pos / 2; } } void heap_pop(int heap[], int n) { // 1 ... n heap[1] = heap[n]; n -= 1; int pos = 1; while(true) { // show(heap, 5); int min_pos = pos; int left = pos*2, right=pos*2+1; if(left < n && heap[left] < heap[min_pos]) { min_pos = left; } if(right < n && heap[right] < heap[min_pos]) { min_pos = right; } if(min_pos == pos) { break; // pos 最小 or left, right 超出範圍 } else { swap(heap[pos], heap[min_pos]); pos = min_pos; } } } int main() { // index 0 不使用，-1 表示空節點 int tree[64] = {}; for(int i=1; i<=15; i++) { tree[i] = i; } show(tree, 4); cout<< "---------------------------------------------------"<< endl; heap_push(tree, 15, 0); show(tree, 5); cout<< "---------------------------------------------------"<< endl; heap_pop(tree, 16); show(tree, 5); return 0; } ``` ::: #### 4-4 圖形結構 [Graph Visualizer](https://graphonline.top/) [BFS / DFS](https://seanperfecto.github.io/BFS-DFS-Pathfinder/) <div style="height: 500px;"></div>