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