演算法的观念.ppt

1、Chapter 5演算法,5.1演算法的觀念 5.2演算法的表示 5.3演算法的發現 5.4反覆的結構 5.5遞迴結構 5.6效率及正確性,5.1演算法的觀念,非正式地定義演算法為一連串用來說明工作如何被完成的步驟。 演算法的正式定義 圖 5.1 中所述演算法的正式定義。 單一個演算法可以用很多種方式來表示。如溫度轉換演算法的例子 F(9 / 5)C + 32 將攝氏溫度乘以 9/5，然後再將乘積加上 32。,圖 5.1一個演算法的定義,程式（program）與工作單元（process）之間的差異。一個程式是表示演算法的方式之一。 程式一詞是指一個為電腦應用設計的演算法的正式表示方式。 工作單

2、元為執行程式的活動。,5.2演算法的表示,原式（primitives）及虛擬碼（pseudocode）的基本觀念。 原式 演算法的表示方式需用到某種語言的形式。 圖 5.2 所示，其中描述用一張正方形的紙來摺一隻小鳥的演算法。 計算機科學家建立了明確的構件，可用以表達相關的演算法。這些構件稱為原式（primitive）。,圖 5.2用一張正方形的紙來摺紙鳥,一群的原式搭配一些規則，就說明了原式可以如何地結合，來代表構成程式語言（programming language）更複雜的概念。 每個原式是由兩個部份所組成：語法（syntax）及語意（semantics）。語法是指原式以符號表示的方法，而

3、語意是指原式的意義。 圖 5.3 表示一些用在摺紙的原式。,圖 5.3 摺紙的基本 原式,虛擬碼 較不正規且較直覺的符號系統，稱為虛擬碼（pseudocode）。 於演算法發展過程中用來非正式地表達觀念的一種符號系統。 使用以下的形式 名稱 運算式 名稱是一個敘述性的名詞，運算式則描述將與該名稱相關聯的值。,指定名稱為運算式的值，例如 RemainingFunds CheckingBalance SavingsBalance 依條件的真或偽擇一執行的條件式,某個條件為真時，連續執行一個或一陳述。,縮排（indentation） 可以增加程式的可閱讀性。如下敘述,procedure 程序名。 圖

4、 5.4 是名為 Greetings 程序的虛擬碼表示式，能夠列印“Hello” 三次。,圖 5.4Greeting 程序以虛擬碼來表示,在 while 陳述的結尾括弧之後，加上一串字 end while 而產生如下陳述：,5.3演算法的發現,發展一個程式需要兩個主要動作：發現其內涵的基本演算法及將演算法表示成程式。 問題解決技巧的基本原則：,發展計算機程式的階段如下,逐步細分法（stepwise refinement）：逐步細分法是一種由上而下方法論（top-down methodology），步驟是由一般到特定。 相反地，由下而上方法論（bottom-up methodology）是從特定

5、到一般。,5.4反覆的結構,反覆結構（iterative structure） 是指一群的指令以迴圈的方式重複地執行。 迴圈控制 重複使用一個或一串指令是演算法中稱為迴圈（loop）的重複結構。,圖 5.6用虛擬碼寫成的依序搜尋演算法,迴圈結構由初設（initialize）、測試（test）及修改（modify）三項動作組成，測試動作的責任是藉由檢驗顯示終止應該發生的條件式而終止迴圈，這個條件式稱為終止條件（termination condition）。,圖 5.7重複控制的組成,語意如圖 5.8 的流程圖（flowchart）。 在圖 5.9 的結構則要求迴圈本體要在終止條件的測試之前被執行

6、。,while 迴圈結構稱為前測迴圈。 repeat 迴圈結構稱為後測迴圈（posttest loop）。,圖 5.8while 迴圈結構,圖 5.9repeat 結構,插入排序演 算法, 圖 5.10對含有 Fred、Alex、Diana、Byron及 Carol 的名單依字母次序做排序,圖 5.11插入排序演算法的虛擬碼,5.5遞迴結構,遞迴結構（recursive structure） 提供重複結構的迴圈方法一個替代方案。 遞迴則將這組需要重複的指令視為自己的一個子工作。 二分搜尋演算法,圖 5.12應用策略在一個名單中找尋 John,圖 5.14二分搜尋演算法的虛擬碼,圖 5.15,圖

7、 5.16,遞迴控制 遞迴程式在要求更多啟動之前要先測試終止條件（常被稱為 base case 或 degenerative case）。,圖 5.17,5.6效率及正確性,演算法的效率 研究演算法所需用到如運算時間及儲存空間等資源之議題的重要性，這個領域稱為演算法分析（algorithm analysis）。 一般均會包含最佳狀況分析（best-case analysis）、最糟狀況分析（worst-case analysis），以及平均狀況分析（average case analysis）。,圖 5.18插入排序應用於一個最糟狀況,圖 5.19插入排序演算法最糟狀況之分析圖,圖 5.20二

8、分搜尋演算法最糟狀況之分析圖,應用在一份有 n 項資料的清單，則依序搜尋法將會平均作 n/2 次的比對，而二分搜尋法在最糟的情況下頂多做lg n 次比對（lg n 代表以 2 為底的 n 的對數值）。 big-theta notation 插入排序法以 (n2) 為代表符號的一類。二分搜尋列入以 (lg n) 為代表符號的一類。 軟體驗證 有位旅行家帶著有七個金環的鏈子住在隔離的旅館七個晚上，每晚的租金是一個金環且隔天早上需馬上付，請問最少要切斷幾個金環才能在每天早上準時付款而且不會提早付？,圖 5.21只要切斷三個金環就可鬆開金環圈,圖 5.22只要切斷一個金環就可鬆開金環圈,被相信是對的程式與對的程式是不同的。 軟體驗證（verification of software）很重要，找尋有效的驗證技巧仍是計算機科學中研究的領域。 目前研究的方法中是運用正規邏輯（formal logic）的技術來證明一個程式的正確性。 程式正確性的證明是基於一開始所假設的先決條件（precondit