HackMD
演算法實作 Using C++
目錄
插入排序法(少量最快)
動態規劃(Dynamic Programming)
二元樹
求解n層河內塔(含路徑過程)
spfa特化演算法(競賽求最短優先)
DFS
Depth-First Search 用於遍歷和搜尋Tree和Graph。以深度為優先順序進行搜索，從起點開始，儘可能深入地訪問每個鄰接節點，直到到達無法再深入的節點或找到目標節點為止。通常使用遞迴或Stack實現。可用於例如迷宮問題、拓撲排序、連通性等。
Sample Question
每次只能前進1或2格，輸入n為目標格數，輸出從起點1到終點n的方法有幾種
//sample 1: 將主block整合呼叫自己與加總分支計算值
#include <iostream>
using namespace std;
// dfs函數，now為目前所在樓層，tg為目標樓層
int dfs(int now, int tg) {
// 已達終點
if (now == tg) {
//剛好達到終點傳回1
return 1;
}
// 已超過終點
if (now > tg) {
return 0;
}
// 創造+1跟+2兩種方法的分支，並讓返回值加總
// 因為剛好達到終點會回傳1，此處進行相加即可達到所有分支達到終點後加總的效果
return dfs(now + 1, tg) + dfs(now + 2, tg);
}
int main() {
int n;
cin >> n;
// 從1開始搜尋到終點n的方法數
cout << dfs(1, n) << endl;
return 0;
}
//sample 2: 將呼叫自身的方法分離，並用counter另外加總不同方法分支回傳值，最終只回傳counter
#include <iostream>
using namespace std;
// dfs函數，now為目前所在樓層，tg為目標樓層
int dfs(int now, int tg) {
// 已達目標
if (now == tg) {
//剛好達到終點傳回1
return 1;
}
// 已超過目標
if (now > tg) {
return 0;
}
int counter = 0;
// 往上一層樓繼續搜尋
counter += dfs(now + 1, tg);
// 往上兩層樓繼續搜尋
counter += dfs(now + 2, tg);
//counter在以上兩種方法分支產生後，會將剛好達到終點的回傳值1加入counter中
// 返回counter即是所有分支最後加總能達到終點的方法數
return counter;
}
int main() {
int n;
cin >> n;
// 從1開始搜尋到終點n的方法數
cout << dfs(1, n) << endl;
return 0;
}
Dijkstra演算法
LCS(最長共同子序列)
LIS(最長(嚴格/非嚴格)遞增子序列)
Kadane's (最大連續和)
輸入一個數列，找出子序列加總中最大值
int sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += x;
max_sum = max(max_sum, sum);
sum = max(sum, 0);
}
cout << sum << endl;
著色判斷
其他結構筆記
遞迴函數
在新增遞迴函數時需要將function拆分為兩個block看待，通常用if架構分隔
- 用於計算的block，最後return的是這條分支的計算結果
- 用於返回最終統整結果的主要block，在這裡最後return時呼叫自身，創造分支進入計算block，經過層層return回來後配合operator，才return最終結果回main function
求n階層
#include <iostream>
using namespace std;
int fac(int n) {
if (n == 0 || n == 1) { // 計算block
return 1;
}
else { // 主block
return n * fac(n - 1);//呼叫自己，創造分支進入計算block
}
}
int main() {
int n;
cin >> n;
cout << n << " 階層 = " << fac(n) << endl;
return 0;
}
地圖座標建構
使用Vector配合自定結構
#include <iostream>
#include <vector>
struct Point {
int x;
int y;
};
int main() {
int N;
cin >> N;
vector<Point> points(N);
for (int i = 0; i < N; i++) {
cin >> points[i].x >> points[i].y;
}
}
