Download presentation
Presentation is loading. Please wait.
1
8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題
演算法 8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題
2
演算法 演算法就是計算機方法，是設計適合計算機執行的方法。 演算法常需要好的設計與分析，有時也需要腦筋急轉彎，才能找到好解答。
先來個腦筋急轉彎吧 128 金幣問題 地獄與 天堂問題 十個聰明 的囚犯問題
3
8-1 最大數及最小數找法 請找出16、77、25、85、12、8、36及52裡的最大數 承上題，請找出最大數及最小數
承上題，請找出最大數及第二大數 承上題，前三大數如何做呢？ 85 52 85 36 85 8 85 12 85 77 25 77 16 85 52 52 12 85 77 16 77 25 85 12 8 36 52
4
8-2 排序 排序問題：給定n個數，請將它們由小排到大。 排序是電腦經常用到的演算法，資料一旦排序之後，後續尋找便能快速進行。
排序的演算法效率差別很大，當資料量變大時，演算法的好壞將影響執行所需時間甚鉅。 本章介紹幾個排序法 選擇排序法 (selection sort) 泡沫排序法 (bubble sort) 插入排序法 (insertion sort) 快速排序法 (quick sort)
5
選擇排序法 步驟1 一開始整個數列歸類為未排序； 步驟2
從未排序的數中，挑選出最小的數，和未排序數列中的第一個位置元素互調，並將該最小的數歸類到已排序的數列中； 步驟3 重複步驟2，直到所有的數都歸到已排序數列中。 將最小的元素和最前面的對調 前端 已排序 尚未排序
6
選擇排序法
7
插入排序法 一開始只有第一個數在已排序數列裡，其他的數歸類在未排序數列裡； 步驟1 步驟2
將未排序數列的第一個數，插入到已排序的數列中，使得插入後的已排序數列仍然維持由小排到大的性質； 步驟3 重複步驟2，直到所有的數都歸到已排序數列中。 插到合序的位置 已排序 尚未排序
8
插入排序法
9
泡沫排序法 步驟1 一開始整個數列歸類為未排序； 步驟2
從未排序數列的最後一個數開始看起，如果後面的數比前面小，就往前推，在這過程中，最小的數會被推到未排序數列中的第一個位置，將該最小的數歸類到已排序的數列中； 步驟3 重複步驟2，直到沒有往前推的動作為止。 如果後面的元素比前面小，就往前推。 已排序 尚未排序
10
泡沫排序法
11
快速排序法
12
8-3 二元搜尋法 (binary search)
步驟 1 mid←原排序數列的中間數； 步驟 2 將所要搜尋的數與mid相比； 步驟 3 如果搜尋的數與mid相等，則我們已找到，回答該 數在數列裡； 步驟 4 如果目前子數列只剩一個數(此時搜尋的數與mid不等)，則回答該數不在數列裡； 步驟 5 如果搜尋的數小於mid，則只要考慮前半的子數列，mid←前面子數列的中間數，回到步驟2； 步驟 6 如果搜尋的數大於mid，則只要考慮後半的子數列 mid←後面子數列的中間數，回到步驟2；
13
二元搜尋法 (binary search) mid 若搜尋的數小於mid則找前面的子數列 與搜尋 的數相比
14
8-4 動態規劃技巧 動態規劃技巧有三個主要部分： 什麼樣的問題適合用動態規劃技巧來解呢？
遞迴關係(recurrence relation) 列表式運算(tabular computation) 路徑迴溯(traceback) 符合最佳化準則，亦即若將最佳答案解構，解 構後的子答案仍為對應子問題的最佳解。 解題過程中，有許多重複的子問題。
15
費氏數(Fibonacci number)
…… F10 F9 F8
16
列表式計算 列表式計算可避免重複計算 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
17
最長共同子序列 子序列就是將一個序列中的一些(可能是零個)字元去掉所得到的序列，例如：pred、sdn、predent等都是 ”president” 的子序列 給定兩序列，最長共同子序列(LCS)問題是決定一個子序列，使得： 最長共同子序列不一定是唯一 該子序列是這兩序列的子序列 它的長度是最長的
18
LCS例題I p r e s i d e n t p r o v i d e n c e
19
LCS例題II a l g o r i t h m a l i g n m e n t
20
定義遞迴關係式 給定兩序列 A = a1a2…am 及 B = b1b2…bn，令 len (i , j)表示 a1a2…ai 與 b1b2…bj 的 LCS 之長度，則下列遞迴關係可用來計算 len (i, j)：
21
計算LCS的長度
22
LCS的長度為6
23
路徑回溯找出LCS
24
LCS為priden
25
8-5 計算難題 有些問題已證明是無解的 判斷程式是否會停的問題(halting problem) NP-Complete
所有NP-Complete問題，目前都沒有有效的精確解法，而且只要有一個找到有效解法，那所有NP-Complete問題都有有效解法了。 許多看似簡單的問題，都已被證明為NP-Complete，例如： 旅行推銷 員問題 小偷背 包問題
Similar presentations
