《第8章演算法.ppt》由会员分享，可在线阅读，更多相关《第8章演算法.ppt（26页珍藏版）》请在三一文库上搜索。
1、第8章 演算法,8-1 最大數及最小數找法 8-2 排序 8-3 二元搜尋法 8-4 動態規劃技巧 8-5 計算難題,演算法,演算法就是計算機方法，是設計適合計算機執行的方法 演算法常需要好的設計與分析，有時也需要腦筋急轉彎，才能找到好解答 先來個腦筋急轉彎吧 128金幣問題 地獄與天堂問題 十個聰明的囚犯問題,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裡的最大數及第二大數 前三大數如何做呢？,8-2 排序,排序問題：給定n個數
2、，請將它們由小排到大 排序是電腦經常用到的演算法，資料一旦排序之後，後續尋找便能快速進行 排序的演算法效率差別很大，當資料量變大時，演算法的好壞將影響執行所需時間甚鉅 本章介紹幾個排序法 選擇排序法（selection sort） 插入排序法（insertion sort） 泡沫排序法（bubble sort） 快速排序法（quick sort）,選擇排序法,選擇排序法,插入排序法,插入排序法,泡沫排序法,泡沫排序法,快速排序法,8-3 二元搜尋法 （binary search）,二元搜尋法,8-4 動態規劃技巧,動態規劃技巧有三個主要部份 遞迴關係（recurrence relation）
3、列表式運算（tabular computation） 路徑迴溯（traceback） 什麼樣的問題適合用動態規劃技巧來解呢 符合最佳化準則，亦即若將最佳答案解構，解構後的子答案仍為對應子問題的最佳解 解題過程中，有許多重複的子問題,費氏數(Fibonacci number),如何計算 F10？,列表式計算,列表式計算可避免重複計算,最長共同子序列,子序列就是將一個序列中的一些（可能是零個）字元去掉所得到的序列，例如：pred、sdn、predent等都是 ”president” 的子序列 給定兩序列，最長共同子序列（LCS）問題是決定一個子序列，使得 該子序列是這兩序列的子序列 它的長度是最長
4、的 最長共同子序列不一定是唯一,LCS例題I,president providence,LCS例題II,a l g o r i t h m a l i g n m e n t,定義遞迴關係式,計算LCS的長度,LCS的長度為6,路徑回溯找出LCS,LCS為priden,8-5 計算難題,有些問題已證明是無解的 判斷程式是否會停的問題（halting problem） NP-Complete 所有NP-Complete問題，目前都沒有有效的精確解法，而且只要有一個找到有效解法，那所有NP-Complete問題都有有效解法了 許多看似簡單的問題，都已被證明為NP-Complete，例如： 旅行推銷員問題 小偷背包問題,