# 資訊科技培訓
---
## 這堂課我們來講講演算法
但不碰程式碼
----
首先，我們得認識一下什麼是演算法
> 指一個被定義好的、計算機可施行其指示的有限步驟或次序，常用於計算、數據處理和自動推理。 演算法是有效方法，包含一系列定義清晰的指令，並可於有限的時間及空間內清楚的表述出來。
----
可以想像成，我們去設計好幾個步驟
來解決特定問題
這個特定問題很廣泛，你想得到的大部分都有
----
像是常聽到YT演算法
> 他就是搜集你常看的，再去找到你可能會喜歡的推薦給你
----
但這個例子可能不夠明確 讓我們來看看最早演算法
**歐幾里得演算法**
----
這個東西是用來求最大公因數的
**透過固定的方式，有一套SOP來求出你要的答案**
後來也在許多領域有應用
----
那程式競賽的演算法呢？
基本演算法(APCS說的)大概有：
* **排序 (sorting)**
* **搜尋 (searching)**
* **貪心法則 (greedy method)**
* **動態規劃 (dynamic programming)**
* **圖論（Graph Theory）**
----
來看看一些原理跟題目吧！
---
## 排序 (sorting)
----
排序指的就是 我給你一串數字（陣列）
由小排到大or顛倒過來
----
但是在介紹排序之前，我們要介紹兩個名詞
* 時間複雜度
* 空間複雜度
----
時間複雜度就是算這個程式跑得快不快
通常會以多項式來表示時間 斜率越大就愈慢
空間複雜度則是會用到多少空間
----
正常寫的排序法會是O($n^2$)
但許多演算法都是O($nlogn$)
log是對數 Ex：$log_28=3$
----
簡單判斷時間複雜度的話就是
一層for迴圈就是一次方
那log怎麼做的呢->每次都剖一半
----
[來看個排序影片了解一下吧](https://youtu.be/kPRA0W1kECg)
----
以下介紹幾個簡單的排序演算法
泡抹排序法(Bubble Sort)
選擇排序法(Selection Sort)
插入排序法(Insertion Sort)
----
泡抹排序法(Bubble Sort)
----
選擇排序法(Selection Sort)
----
插入排序法(Insertion Sort)
順便講搜尋XD
---
## 貪心法則 (greedy method)
----
這個比較難懂
簡單來說就是找到一個策略
一直照著這個策略走 最後會是好的....嗎？
----
來看看例題
你現在有1元、5元、10元、50元、100元的硬幣，有很多個
現在要找開459元，最少用幾個硬幣？
----
簡單吧！
4個100,1個50,1個5,4個1 共10個
策略就是由大往下找
----
這個演算法就是直覺想法 但有時候會是對的
----
為什麼是有時候？
來看看例題：
你現在有1元、5元、8元的硬幣，有很多個
要找開15元，最少用幾個硬幣
----
照你的策略，要4個
但是可以3個5元啊，所以就會錯了
----
為什麼呢？
如果你去證明這個貪心是對的話
他必須要是硬幣的大小呈倍數關係
----
沒有倍數的話沒關係
來看看另一個演算法！
---
## 動態規劃 (dynamic programming)
他是用來記錄最佳答案、最好狀態的演算法
----
對他來說 那個硬幣就是一個蛋糕
但對你們來說有點難
----
所以我們來看看一個例題：
小明爬樓梯，一次可以跨1,2步，問走到第7階有幾種走法？
這題其實是排列組合問題
----
排列組合解：
設1步走了x個，2走了y個
那麼x+2y=7
| x | 1 | 3 | 5 | 7 |
| --- | --- | --- | --- | --- |
| y | 3 | 2 | 1 | 0 |
$C^4_1+C^5_2+C^6_1+C^7_0=4+10+6+1=21$
----
但是用動態規劃呢？
解法：記錄狀態及轉移式
考慮每個階梯的小明是從哪個階梯的小明來的
----
圖片說明
所以這題其實就是費氏數列拉
----
大家有稍微懂這演算法在幹嘛了嗎？
簡單來說就是，找出問題的轉移式，推向最正確的答案
----
有空來想想這些題目怎麼解？
```
剛開始的硬幣題目
小明長高了，可以一次跨1,2,3階樓梯，問走到第n階的方法數？
小明想搞你，可以一次跨1,2,3階樓梯，但有個條件，不能連續走同樣階數，問走到第n階的方法數？
一台電梯最多載n公斤，有m個客人，每個客人有體重$W_i$，問最少幾趟載完？
```
---
## 圖論（Graph Theory）
----
他其實是數學的分支
演算法對初學者來說不好懂又難寫
----
圖的儲存與遍歷
----
儲存：
1. 鄰接矩陣
2. 鄰接串列
3. 邊集合
----
1. G[a][b]=e;
2. G[a].push_back(e);
3. vector.push_back({a,b,e});
----
### 圖的遍歷
這很重要，因為很多操作都建立在這上面
----
DFS
透過遞迴(Stack,LIFO)寫法
----
BFS
通常用Queue,FIFO輔助
----
dfs code
```cpp=
int vis[MAX];
void dfs(int v) {
vis[v] = true;
for (int u : G[v]) {
if (!vis[u]) {
dfs(u);
}
}
}
```
----
bfs code
```cpp=
int vis[MAX];
queue<int> BFS;
BFS.push(1);
vis[1] = true;
while (!BFS.empty()) {
int v = BFS.front()
BFS.pop();
for (int u : G[v]) {
if (!vis[u]) {
BFS.push(u);
vis[u] = true;
}
}
}
```
---
圖論還有一個很重要的應用：最短路徑
簡單來說就是從A點走向B點
找到之間的最短距離
----
----
| 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- |:---:|
| 0 | 1 | 8 | 4 | 13 | 17 |
----
其實有一個演算法叫dijkstra
那你會問，啊我知道這要幹嘛？
----
看這張圖
----
讓我們把他的畫質稍微降低一點
```
可以發現，其實地圖上的每個點，對於電腦來說就是一個一個得像素點，而這些像素就像我們剛剛解的那個簡單圖一樣，有很多點，點跟點之間的距離一樣
當然，這不是google地圖真正的演算法，如果這是的話，那我們都可以進google工作了
```
----
圖論的應用還有許多
像是拓撲排序
（可以想成你要先完成一個點才能到另一個點）
----
----
dijkstra
```cpp=
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
//using namespace __gnu_pbds;
#define f first
#define s second
#define pii pair<int,int>
#define pb push_back
#define int long long
#define AC_code ios_base::sync_with_stdio(0);cin.tie(0);
vector<pii> G[200010];
int vis[200010];
signed main(){
AC_code
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int q,w,e;
cin>>q>>w>>e;
G[q].pb({w,e});
//G[w].pb({q,e});
}
priority_queue<pii,vector<pii>,greater<pii>> q;
int ans[200010];
for(int i=0;i<200010;i++)ans[i]=1000000000000000;
ans[1]=0;
q.push({ans[1],1});
while(!q.empty()){
auto tmp=q.top();q.pop();
if(vis[tmp.s])continue;
vis[tmp.s]=1;
for(auto i:G[tmp.s]){
if(ans[i.f]>tmp.f+i.s){
ans[i.f]=tmp.f+i.s;
q.push({ans[i.f],i.f});
}
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
}
```
----
其餘最短路徑演算法：
1. bellman ford(SPFA)
2. Floyd
這裡就不細說ㄌ
---
### 拓墣排序
有向無環圖
----
----
----
----
----
----
寫法：紀錄入度與出度
----
相信大家有稍微懂演算法在幹嘛了吧！
我們可以用很多演算法來優化眼前問題
----
而許多競賽考的就是這個：
如何設計出好的演算法 在時間內解決題目
Google Drive
Gist
Clipboard
Sign in with Wallet
