《【教学课件】第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）列表式運算（tabular co
3、mputation）路徑迴溯（traceback）什麼樣的問題適合用動態規劃技巧來解呢符合最佳化準則，亦即若將最佳答案解構，解構後的子答案仍為對應子問題的最佳解解題過程中，有許多重複的子問題,費氏數(Fibonacci number),如何計算 F10？,列表式計算,列表式計算可避免重複計算,最長共同子序列,子序列就是將一個序列中的一些（可能是零個）字元去掉所得到的序列，例如：pred、sdn、predent等都是”president”的子序列 給定兩序列，最長共同子序列（LCS）問題是決定一個子序列，使得該子序列是這兩序列的子序列它的長度是最長的最長共同子序列不一定是唯一,LCS例題I,presidentprovidence,LCS例題II,a l g o r i t h ma 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，例如：旅行推銷員問題小偷背包問題,
