# 資訊科技培訓 --- ## 這堂課我們來講講演算法 但不碰程式碼 ---- 首先，我們得認識一下什麼是演算法 > 指一個被定義好的、計算機可施行其指示的有限步驟或次序，常用於計算、數據處理和自動推理。 演算法是有效方法，包含一系列定義清晰的指令，並可於有限的時間及空間內清楚的表述出來。 ---- 可以想像成，我們去設計好幾個步驟 來解決特定問題 這個特定問題很廣泛，你想得到的大部分都有 ---- 像是常聽到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 這裡就不細說ㄌ --- ### 拓墣排序 有向無環圖 ----  ----  ----  ----  ----  ---- 寫法：紀錄入度與出度 ---- 相信大家有稍微懂演算法在幹嘛了吧！ 我們可以用很多演算法來優化眼前問題 ---- 而許多競賽考的就是這個： 如何設計出好的演算法 在時間內解決題目