第8章演算法ppt課件

1、第8章 演算法8-1 最大數(shù)及最小數(shù)找法8-2 排序8-3 二元搜尋法8-4 動態(tài)規(guī)劃技巧8-5 計(jì)算難題8-2全華科技圖書全華科技圖書演算法演算法n演算法就是計(jì)算機(jī)方法，是設(shè)計(jì)適合計(jì)算機(jī)執(zhí)行的方法n演算法常需求好的設(shè)計(jì)與分析，有時(shí)也需求腦筋急轉(zhuǎn)彎，才干找到好解答 n先來個(gè)腦筋急轉(zhuǎn)彎吧 n128金幣問題 n地獄與天堂問題 n十個(gè)聰明的囚犯問題 8-3全華科技圖書全華科技圖書8-1 最大數(shù)及最小數(shù)找法最大數(shù)及最小數(shù)找法n請找出16、77、25、85、12、8、36及52裡的最大數(shù) n請找出16、77、25、85、12、8、36及52裡的最大數(shù)及最小數(shù)n請找出16、77、25、85、12、8、36

2、及52裡的最大數(shù)及第二大數(shù)n前三大數(shù)如何做呢？8-4全華科技圖書全華科技圖書8-2 排序排序n排序問題：給定n個(gè)數(shù)，請將它們由小排到大 n排序是電腦經(jīng)常用到的演算法，資料一旦排序之後，後續(xù)尋找便能快速進(jìn)行n排序的演算法效率差別很大，當(dāng)資料量變大時(shí)，演算法的好壞將影響執(zhí)行所需時(shí)間甚鉅n本章介紹幾個(gè)排序法n選擇排序法selection sortn插入排序法insertion sortn泡沫排序法bubble sortn快速排序法quick sort 8-5全華科技圖書全華科技圖書選擇排序法選擇排序法8-6全華科技圖書全華科技圖書選擇排序法選擇排序法8-7全華科技圖書全華科技圖書插入排序法插入排序法

3、 8-8全華科技圖書全華科技圖書插入排序法插入排序法8-9全華科技圖書全華科技圖書泡沫排序法泡沫排序法 8-10全華科技圖書全華科技圖書泡沫排序法泡沫排序法8-11全華科技圖書全華科技圖書快速排序法快速排序法8-12全華科技圖書全華科技圖書8-3 二元搜尋法二元搜尋法 binary search 8-13全華科技圖書全華科技圖書二元搜尋法二元搜尋法8-14全華科技圖書全華科技圖書8-4 動態(tài)規(guī)劃技巧動態(tài)規(guī)劃技巧 n動態(tài)規(guī)劃技巧有三個(gè)主要部份n遞迴關(guān)係recurrence relationn列表式運(yùn)算tabular computationn路徑迴溯tracebackn什麼樣的問題適合用動態(tài)規(guī)劃技

4、巧來解呢n符合最正確化準(zhǔn)則，亦即假設(shè)將最正確答案解構(gòu)，解構(gòu)後的子答案仍為對應(yīng)子問題的最正確解n解題過程中，有許多重複的子問題 8-15全華科技圖書全華科技圖書費(fèi)氏數(shù)費(fèi)氏數(shù)(Fibonacci number) 8-16全華科技圖書全華科技圖書如何計(jì)算如何計(jì)算 F10？ F10F9F8F8F7F7F68-17全華科技圖書全華科技圖書列表式計(jì)算列表式計(jì)算n列表式計(jì)算可防止重複計(jì)算F0F1F2F3F4F5F6F7F8F9F10011235813 21 34 558-18全華科技圖書全華科技圖書最長共同子序列最長共同子序列n子序列就是將一個(gè)序列中的一些能夠是零個(gè)字元去掉所得到的序列，例如：pred、sd

5、n、predent等都是 president 的子序列 n給定兩序列，最長共同子序列LCS問題是決定一個(gè)子序列，使得n該子序列是這兩序列的子序列n它的長度是最長的n最長共同子序列不一定是獨(dú)一 8-19全華科技圖書全華科技圖書LCS例題例題Ipresidentprovidence8-20全華科技圖書全華科技圖書LCS例題例題IIa l g o r i t h ma l i g n m e n t8-21全華科技圖書全華科技圖書定義遞迴關(guān)係式定義遞迴關(guān)係式8-22全華科技圖書全華科技圖書計(jì)算計(jì)算LCS的長度的長度8-23全華科技圖書全華科技圖書LCS的長度為的長度為68-24全華科技圖書全華科技圖書路徑回溯找出路徑回溯找出LCS8-25全華科技圖書全華科技圖書LCS為為priden8-26全華科技圖書全華科技圖書8-5 計(jì)算難題計(jì)算難題 n有些問題已證明是無解的n判斷程式能否會停的問題halting problemn NP-Complete n一切NP-Complete問題，目前都沒有有效的精確解