8章演算法.pptVIP

第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個數，請將它們由小排到大 排序是電腦經常用到的演算法，資料一旦排序之後，後續尋找便能快速進行 排序的演算法效率差別很大，當資料量變大時，演算法的好壞將影響執行所需時間甚鉅 本章介紹幾個排序法 選擇排序法（selection sort） 插入排序法（insertion sort） 泡沫排序法（bubble sort） 快速排序法（quick sort） 選擇排序法 選擇排序法 插入排序法 插入排序法 泡沫排序法 泡沫排序法 快速排序法 8-3 二元搜尋法 （binary search） 二元搜尋法 8-4 動態規劃技巧 動態規劃技巧有三個主要部份 遞迴關係（recurrence relation） 列表式運算（tabular computation） 路徑迴溯（traceback） 什麼樣的問題適合用動態規劃技巧來解呢 符合最佳化準則，亦即若將最佳答案解構，解構後的子答案仍為對應子問題的最佳解 解題過程中，有許多重複的子問題 費氏數(Fibonacci number) 如何計算 F10？ 列表式計算 列表式計算可避免重複計算 最長共同子序列 子序列就是將一個序列中的一些（可能是零個）字元去掉所得到的序列，例如：pred、sdn、predent等都是 ”president” 的子序列 給定兩序列，最長共同子序列（LCS）問題是決定一個子序列，使得 該子序列是這兩序列的子序列 它的長度是最長的 最長共同子序列不一定是唯一 LCS例題I LCS例題II 定義遞迴關係式 計算LCS的長度 LCS的長度為6 路徑回溯找出LCS LCS為priden 8-5 計算難題 有些問題已證明是無解的 判斷程式是否會停的問題（halting problem） NP-Complete 所有NP-Complete問題，目前都沒有有效的精確解法，而且只要有一個找到有效解法，那所有NP-Complete問題都有有效解法了 許多看似簡單的問題，都已被證明為NP-Complete，例如： 旅行推銷員問題 小偷背包問題 8-* 計算機概論 全華科技圖書 F10 F9 F8 F8 F7 F7 F6 …… 55 34 21 13 8 5 3 2 1 1 0 F10 F9 F8 F7 F6 F5 F4 F3 F2 F1 F0 president providence a l g o r i t h m a l i g n m e n t 8-* 計算機概論 全華科技圖書