# 資訊科技競賽培訓 DAY 3 --- 初探演算法 ---- 什麼是演算法? <!-- 讓他們發表意見(slido) --> ---- 電腦可以執行的方法，這個方法可以讓我們得到問題的答案 ---- 舉個例子：1+2=? ---- ```cpp= #include <iostream> using namespace std; signed main() { cout << 1 + 2 << endl; } ``` 不就這樣而已嗎，那為什麼要學演算法 ? ---- 學習演算法，其實是要讓我們達成兩件事情： 1. 加速處理問題的速度 2. 處理那些很難的問題 ---- 第一種: 加速處理問題的速度 ----  ---- 第一種方法：計算時間: 10秒  ---- 第二種方法：計算時間: 2秒  ---- 第三種方法：計算時間: 0.2秒  ---- 由此可知，好的演算法可以讓我們運算速度快一些 其實這就是「時間複雜度」的概念，有興趣的同學可以上網查查看 ---- 第二種：處理那些很難的問題  --- # 經典演算法介紹 ---- 來個數學題 ---- 下圖為一個7x6格子盤，由左上走到右下，每一次只能往右走一個或者往下走一格，試問在所有這樣走法的路徑中，數字和最小者為何? |0|1|3|2|3|4|5| |-|-|-|-|-|-|-| |2|2|1|4|6|2|0| |1|9|9|9|9|9|1| |4|7|-3|2|1|-2|1| |9|8|7|0|1|2|7| |-3|2|2|3|1|-3|1| ---- 我們先試試挑最小的走 ---- |<p style="color: red">0</p>|<p style="color: red">1</p>|3|2|3|4|5| |-|-|-|-|-|-|-| |2|<p style="color: red">2</p>|<p style="color: red">1</p>|<p style="color: red">4</p>|<p style="color: red">6</p>|<p style="color: red">2</p>|<p style="color: red">0</p>| |1|9|9|9|9|9|<p style="color: red">1</p>| |4|7|-3|2|1|-2|<p style="color: red">1</p>| |9|8|7|0|1|2|<p style="color: red">7</p>| |-3|2|2|3|1|-3|<p style="color: red">1</p>| ---- 總和是: 26 這是最小總和嗎? ---- 正確答案是：11 ---- 動態規劃(Dynamic Programming) ---- 把大問題拆解成小問題，然後一步步解決他 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = ? 1 + 1 = 2 2 + 2 + 2 + 2 = ? 2 + 2 = 4 4 + 4 = 8 ---- 回到前面的題目，我們來看看最佳走法: ---- |<p style="color: blue">0</p>|<p style="color: blue">1</p>|3|2|3|4|5| |-|-|-|-|-|-|-| |2|<p style="color: blue">2</p>|<p style="color: blue">1</p>|4|6|2|0| |1|9|<p style="color: blue">9</p>|9|9|9|1| |4|7|<p style="color: blue">-3</p>|<p style="color: blue">2</p>|<p style="color: blue">1</p>|<p style="color: blue">-2</p>|1| |9|8|7|0|1|<p style="color: blue">2</p>|7| |-3|2|2|3|1|<p style="color: blue">-3</p>|<p style="color: blue">1</p>| |4|5|4|0|4|5|<p style="color: blue">4</p>| ---- 我們可以從動態規劃的角度切入： 先處理前面幾個格子的問題 每個格子只會從上面和左邊走到 ---- |0|1|3|2|3|4|5| |-|-|-|-|-|-|-| |2|2|1|4|6|2|0| 這是剛剛前兩排的個格子 最上面那排的我們知道，都是從左邊過來 那第二排第二個的2從哪邊過來比較好呢 ? ---- 顯然是從上面來吧 ! 那第二排的第三個格子呢 ? 我們是不是可以先分別計算「上方格子的最短路徑加總」跟「左方格子的最短路徑加總」，比較誰比較小，代表就是從那邊來 ? ---- 那「上方格子的最短路徑加總」跟「左方格子的最短路徑加總」怎麼算 ? 一樣 ! 只要計算這兩個格子的「上方格子的最短路徑加總」跟「左方格子的最短路徑加總」就好了 ! ---- |0|1|3|2|3|4|5||0|1|4|6|9|13|18| |-|-|-|-|-|-|-|-|-|-|-|-|-|-|-| |2|2|1|4|6|2|0||2|3|4|8|14|15|15| |1|9|9|9|9|9|1||3|12|13|17|23|24|16| |4|7|-3|2|1|-2|1||7|14|10|12|13|11|12| |9|8|7|0|1|2|7||16|22|17|12|13|13|19| |-3|2|2|3|1|-3|1||13|15|17|15|14|10|11| --- 既然剛提到google地圖，那就來看看最短路徑吧 ---- 假設每條路線的距離一樣長，請問A->B最短的距離是多少  ---- ## BFS 演算法 ----  ----  ----  ----  ----  ----  ---- 也許你會疑惑，這東西完全沒有用啊，現實中的地圖又不長那樣 ---- 但如果每個點線變得更密集呢? ---- 再看一次這張圖  ---- 讓我們把他的畫質稍微降低一點  <!-- 可以發現，其實地圖上的每個點，對於電腦來說就是一個一個得像素點，而這些像素就像我們剛剛解的那個簡單圖一樣，有很多點，點跟點之間的距離一樣 --> <!-- 當然這不是google地圖真正的演算法，如果這是的話，那我們都可以進google工作了 --> ---- 演算法除了設計一個特別的方法之外，如何簡化問題也是其精隨所在 <!-- 當我們簡化了問題，再把問題丟給電腦時，電腦就可以用它強大的運算能力，把用來解決簡單問題的方法，拿來解決複雜的問題 --> --- 讓我們再看一個有趣的問題 ---- 你和你的朋友正在玩Minecraft，你們想要通關遊戲 你們必須透過一連串的步驟來打倒終界龍， 步驟有先後順序 而你們知道每個步驟要花多少時間 那想預估會花多少時間通關，該怎麼做? (不能把所有時間加起來，因為你們人手夠多，可以同時做) <!-- 這裡讓他們想一下怎麼簡化問題 --> ---- 簡化問題 ----  ---- 設計方法 ---- 拓樸排序 ----  ----  ----  ----  ----  --- 思考如何用電腦解決問題就是演算法的樂趣所在 ---- 其實大多數的考試都是在考你如何撰寫一個好的演算法 包括 APCS 和其他比賽等等 --- Q&A TIME