### 在基礎語法之後 - 演算法的學習與實作
鳳山高中 208 施奕婷
---
### [這份簡報的 QR-Code](https://hackmd.io/J_4QarXxRoeyVekJW_ry0Q?view)
---
- **目標**: 學習演算法並撰寫筆記
- **筆記工具**: HackMD (這份簡報也是用它 :D)
- **Online Judge**: CSES
- **參考資料**:
- [交大開放式課程 - 演算法](https://www.youtube.com/playlist?list=PLj6E8qlqmkFtoRpLn6IXnH_eboef-3QvZ)
- [鳳中電資綜合資料存放區](https://swamp-oval-2df.notion.site/oj-83be9932772240bc8de73756814e6e54)
- [SA 流 C++ 競程修練心法](https://hackmd.io/@sa072686/cp/%2F%40sa072686%2FBkTJ0imPB) <- 我個人的愛
- [從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/)
- **特別感謝**:
- 鳳中電資
- BABYMONSTER
---
### HackMD
- **支援 Markdown 語法**:
- 僅僅使用文字與符號，就能快速排版
- 支援程式碼區塊
- LaTeX
- **有 dark mode**:
- 拯救我報廢的雙眼
- **簡報模式 / 書本模式**
---
### 演算法
- 用電腦算數學，解決問題的方法
- 演算法的優劣 ?
- 空間複雜度
- 時間複雜度
---
### CSES
- 經典題型很多
- 是線上評測系統（Online Judge）
- 寫完程式後上傳，它會幫你批改
- 丟輸入給你的程式判斷你的輸出是否正確，注意輸出是否符合題目要求
- 其它常見的 OJ
- [ZeroJudge](https://zerojudge.tw/)
- [kattis](https://open.kattis.com/)
- [Codeforces](https://codeforces.com/)
---
關於閱讀簡報的小提醒 :
以下頁數左右滑會是不同觀念
同一觀念的延伸請往上下滑~
---
### CSES Introductory Problems
#### 1. [Weird Algorithm ](https://cses.fi/problemset/task/1068)
題目會輸入一個整數 n，持續對這個數做下列動作並輸出每次結果，直到 n = 1 :
如果 n 是奇數，n = 3 * n + 1
如果 n 是偶數，n = n / 2
----
這題其實是[考拉茲猜想](https://zh.wikipedia.org/zh-tw/%E8%80%83%E6%8B%89%E5%85%B9%E7%8C%9C%E6%83%B3)，用while迴圈實作即可。
須注意直接用int會overflow。
----
code :
```cpp
#include<bits/stdc++.h>
using namespace std;
void Collatz_conjecture(long long int n){
while(n > 1){
cout << n << " ";
if (n % 2 == 0){
n /= 2;
}
else{
n = 3 * n + 1;
}
}
cout << n;
return;
}
int main(){
long long int n;
cin >> n;
Collatz_conjecture(n);
return 0;
}
```
----
類似題目:
- [FOJ - 失眠](http://fscs.fssh.khc.edu.tw:7122/problem/Dy005) ( Hint : || 前綴和 || )
- [Zerojudge - 考拉茲猜想](https://zerojudge.tw/ShowProblem?problemid=g256)
---
### Data structure - queue
----
queue (佇列) 是一種先進先出(First In First Out, FIFO)的資料結構。
就像排隊一樣，先進到隊伍裡的會先被取出，從排頭取出，從排尾加入。
----
用array可以模擬queue的一些簡易操作:
```cpp
#include <iostream>
using namespace std;
int arr[200];
int head = 0, tail = 0;
//紀錄當前頭尾的位置, 頭包含, 尾不包含
bool isempty(){
return tail == head;
}
bool isfull(){
return tail == 200;
}
void length(){
cout << tail - head << "\n";
}
//新增(從尾端)
void add(int data){
if (isfull()){
cout << "The array is full!!!\n";
}
else{
arr[tail] = data;
tail++;
}
}
//取出(輸出值並刪除)
void get(){
if (isempty()){
cout << "The array is empty!!!\n";
}
else{
cout << arr[head] << "\n";
head++;
}
}
int main() {
add(10);
add(20);
length();
get();
get();
get();
}
```
----
**思考**:
1. 這樣儲存的缺點是甚麼?
-> 當刪除元素時，空出的空間被浪費。
2. 怎樣可以避免空間浪費?
用環狀佇列或linked list，
前者像圓一樣，後面滿的時候從前面繼續加入，並檢查head是否與tail重疊，較易實作。
---
#### Dynamic Programming
何謂動態規劃(Dynamic Programming, dp ) ?
Programming 是指寫程式嗎 ?
實際上是 integer programming / nonlinear programming
(線性 / 非線性規劃)
帶有最佳化的意思。
( 摘要自 [交大開放式課程](https://www.youtube.com/watch?v=359YMyqbEG4) )
----
另一種我也很喜歡的解釋是 programming
指的是一種表格法。
我們經常在思考 dp 問題時，
使用表格來推算。
dp 的基礎是先前提到的
divide and conquer (分治法)。
當切割出來的小部分具有某種規律或相似性，
一而再再而三地出現，
我們就利用當前已知的結果
去推算後續的答案。
----
#### dp 的步驟
1. 定義狀態 ( dp[i] 的意義 ? )
2. 找出轉移式 ( 遞迴式 )
3. 釐清初始狀態 ( 如何出發 ? 終止條件 ? )
----
### 費氏數列
$$
F_0 = 0
$$
$$
F_1 = 1
$$
$$
F_n = F_{n-1} + F_{n-2}, \quad n \geq 2
$$
----
這裡的 f(n) 及為 dp[n]，
所以轉移式就是 dp[i] = dp[i - 1] + dp[i - 2]，
在 n = 2 之後每一項的值是前兩項值的總和，
因此，只要依序取得前幾項的答案，
我們就能往後推算，
時間複雜度為 O(n)。
----
##### 跟遞迴的比較
----
若直接遞迴，
不將資料存到陣列中，
會重複算到同樣顏色的部分，例如 f(3)，
若我們第一次計算時就將資料存起來，
第二次走到時將資料取出即可，
不用繼續往下遞迴，這就是動態規畫的概念。
以空間換取時間，時間複雜度從 O(n^2) 降到 O(n)。
----
### [AtCoder - Frog 1](https://atcoder.jp/contests/dp/tasks/dp_a)
給定石頭總數 N 與 每個石頭的高度 hi，
這隻青蛙最開始在第 1 顆石頭，一次只能跳格或兩格，
從高度 hi 的石頭跳到高度 hj 的石頭，需要花費 ∣ hj - hi ∣
試求從第 1 顆石頭跳到第 N 顆石頭的最小花費
----
**現在青蛙在第 k 顆石頭，
那他的來源有兩種選擇 :**
1. 從第 k - 1 顆石頭跳過來
2. 從第 k - 2 顆石頭跳過來
----
**我們定義 dp[k] 是走到第 k 格的總花費 :**
1. 跳到 k - 1 顆石頭累積的花費 dp[k - 1] + 從第 k - 1 顆石頭跳過來的花費 ∣ hk - h~k-1~ ∣
2. 跳到 k - 2 顆石頭累積的花費 dp[k - 1] + 從第 k - 1 顆石頭跳過來的花費 ∣ hk - h~k-1~ ∣
----
**選擇其中最小的花費 :**
用 int high[N + 1] 儲存 h~i~
----
轉移式 :
dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]),
dp[i - 2] + abs(h[i] - h[i - 2]));
用一個迴圈從 int i = 1 開始跑，
跑到 i = k 時 dp[k - 1] 跟 dp[k - 2] 是已知，
不必擔心前面複雜的選擇過程，
因為每一步都決定了走到該石頭花費最少的路徑
現在我們來檢查初始跟終止的狀態 :
* 初始 : dp[i] = h1
* 終止 : i = N, dp[N] 是所求
----
code :
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int n ; cin >> n;
int high[n];
int dp[n] = {0};
for(int i = 0 ; i < n ; i++){
cin >> high[i];
}
dp[1] = abs(high[1] - high[0]);
for(int i = 2 ; i < n ; i++){
dp[i] = min(dp[i - 1] + abs(high[i] - high[i - 1]), dp[i - 2] + abs(high[i] - high[i - 2]));
}
cout << dp[n - 1];
return 0;
}
```
---
#### 總是 Wrong Answer 沒關係，因為我是 Chill Guy
---
雖然在這次的自主學習中遇到了許多挫折，
有時候連簡單的題目都 debug 半天，
開始自我懷疑並向乖乖祈禱 ( ? )，
甚至問 ChatGPT 也沒能得到正確解答，
但演算法的學習無疑訓練了我的邏輯思考能力，
答案正確 (Accepted) 時的成就感更是無可取代的，
期許自己能持續學習並成長 !!!
---
### - The End -
感謝觀看~ owo
{"title":"自主學習報告","description":"在基礎語法之後 - 演算法的學習與實作","contributors":"[{\"id\":\"149eace9-ccb0-45a8-bc0e-0f85618210ff\",\"add\":11214,\"del\":5532}]"}