8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題

Presentation on theme: "8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題"— Presentation transcript:

1 8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題
第8章 演算法 8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題

2 演算法 演算法就是計算機方法，是設計適合計算機執行的方法 演算法常需要好的設計與分析，有時也需要腦筋急轉彎，才能找到好解答
先來個腦筋急轉彎吧 128金幣問題 地獄與天堂問題 十個聰明的囚犯問題

3 法國網球公開賽女雙冠軍 謝淑薇和彭帥

4 Sara Errani and Roberta Vinci of Italy
法國網球公開賽女雙冠亞軍 謝淑薇和彭帥 Sara Errani and Roberta Vinci of Italy

5 8-1 最大數及最小數找法 請找出16、77、25、85、12、8、36及52裡的最大數
請找出16、77、25、85、12、8、36及52裡的最大數及最小數 請找出16、77、25、85、12、8、36及52裡的最大數及第二大數 前三大數如何做呢？

6 8-2 排序 排序問題：給定n個數，請將它們由小排到大 排序是電腦經常用到的演算法，資料一旦排序之後，後續尋找便能快速進行
排序的演算法效率差別很大，當資料量變大時，演算法的好壞將影響執行所需時間甚鉅 本章介紹幾個排序法 選擇排序法（selection sort） 插入排序法（insertion sort） 泡沫排序法（bubble sort） 快速排序法（quick sort）

7 選擇排序法

8 選擇排序法

9 插入排序法

10 插入排序法

11 泡沫排序法

12 泡沫排序法

13 快速排序法

14 8-3 二元搜尋法 （binary search）

15 二元搜尋法

16 8-4 動態規劃技巧 動態規劃技巧有三個主要部份 什麼樣的問題適合用動態規劃技巧來解呢 遞迴關係（recurrence relation）
列表式運算（tabular computation） 路徑迴溯（traceback） 什麼樣的問題適合用動態規劃技巧來解呢 符合最佳化準則，亦即若將最佳答案解構，解構後的子答案仍為對應子問題的最佳解 解題過程中，有許多重複的子問題

17 費氏數(Fibonacci number)

18 如何計算 F10？ F10 F9 F8 F7 F6 ……

19 列表式計算 列表式計算可避免重複計算 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 1 2 3 5 8 13 21
1 2 3 5 8 13 21 34 55

20 最長共同子序列 子序列就是將一個序列中的一些（可能是零個）字元去掉所得到的序列，例如：pred、sdn、predent等都是 ”president” 的子序列 給定兩序列，最長共同子序列（LCS）問題是決定一個子序列，使得 該子序列是這兩序列的子序列 它的長度是最長的 最長共同子序列不一定是唯一

21 LCS例題I president providence

22 LCS例題II a l g o r i t h m a l i g n m e n t

23 定義遞迴關係式

24 計算LCS的長度

25 LCS的長度為6

26 路徑回溯找出LCS

27 LCS為priden

28 8-5 計算難題 有些問題已證明是無解的 NP-Complete 判斷程式是否會停的問題（halting problem）
所有NP-Complete問題，目前都沒有有效的精確解法，而且只要有一個找到有效解法，那所有NP-Complete問題都有有效解法了 許多看似簡單的問題，都已被證明為NP-Complete，例如： 旅行推銷員問題 小偷背包問題