---
# System prepended metadata

title: 高二進階程式設計 - 課程補充
tags: [ck, mycourse]

---

[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>
