CHAP13 演算法概論 高中資訊科技概論 松崗圖書公司.

Presentation on theme: "CHAP13 演算法概論 高中資訊科技概論 松崗圖書公司."— Presentation transcript:

1 CHAP13 演算法概論 高中資訊科技概論 松崗圖書公司

2 本章目錄 13-1 演算法簡介 13-2 演算法表示方法 一、演算法的基本結構 二、演算法的表示 13-3 演算法與電腦解題

3 13-1 演算法簡介

4 13-1 演算法簡介 使用電腦的目的就是要解決問題，為了解決問題， 電腦要能依照給定的步驟執行，這些執行的步驟就 是演算法的概念
13-1 演算法簡介 使用電腦的目的就是要解決問題，為了解決問題， 電腦要能依照給定的步驟執行，這些執行的步驟就 是演算法的概念 演算法 (Algorithm) 是資訊科學中重要的領域之一， 也是使用電腦解決問題所不可或缺的方法

5 13-1 演算法簡介 演算法是一套解決 問題的程序和方法， 不但使用在日常生 活，也使用在每天 的學習活動 製作蛋糕的食譜

6 13-1 演算法簡介 在資訊科學的世界中，許多領域常會用到演算 法。使用電腦一定會用到演算法，例如 壓縮檔案時，會使用到資料壓縮的演算法
13-1 演算法簡介 在資訊科學的世界中，許多領域常會用到演算 法。使用電腦一定會用到演算法，例如 壓縮檔案時，會使用到資料壓縮的演算法 將 CD 音樂轉成 MP3 檔案時，就會使用到聲 音格式轉換的演算法 上網搜尋資料時，就會使用到資料搜尋的演算 法 收發電子郵件時，就會用到許多網路相關的演 算法

7 13-1 演算法簡介 演算法操作步驟的特性： 輸入 (Input) 要有零個或零個以上的外部輸入值
13-1 演算法簡介 演算法操作步驟的特性： 輸入 (Input) 要有零個或零個以上的外部輸入值 輸出 (Output) 經過演算法處理後，至少會有一個或一個以上的輸出結 果 明確性 (Definiteness) 每一個處理動作都必須明確，不可含糊混淆，不同的人 解讀，都可以得到同樣的結果 有限性 (Finiteness) 必須在有限的步驟或時間內結束 有效性 (Effectiveness) 演算法的處理動作必須是有效且具體可行的，同時能讓 使用者使用紙筆計算獲得答案

8 13-1 演算法簡介 一個演算法是明確、有效、最終會結束 的可執行步驟 因此演算法可以定義成：
13-1 演算法簡介 因此演算法可以定義成： 一個演算法是明確、有效、最終會結束 的可執行步驟 正確的演算法，應該能夠將輸入的資料，經過 電腦有限次的運算後，得到所要的輸出資料， 且能完全符合上述的五個特性

9 13-1 演算法簡介 檢驗正確的演算法

10 13-1 演算法簡介 每個人的思考方式不同，設計出來的演算法， 也可能會不同，例如按高矮次序排隊

11 13-2 演算法表示方法

12 13-2 演算法表示方法 演算法的表示方法是指透過人類易懂的自然語 言或文字符號，將電腦解題執行的步驟、邏輯 判斷或流程進行全盤推演，用以表示出解決問 題的方法。

13 一、演算法的基本結構 循序 (Sequence) 結構 選擇 (Selection) 結構 重複 (Iteration) 結構
依先後順序，一個步驟接著一個步驟依序執行。 選擇 (Selection) 結構 依據不同的條件，選擇不同的解題步驟執行。 重複 (Iteration) 結構 部分解題步驟需要反覆執行，直到符合或是不符合某 一條件式時，才會離開重複執行的部份。 重複結構也常被稱為「迴圈 (Loop)」 。

14 一、演算法的基本結構 循序 (Sequence) 結構 例如兩個杯子內的水互相交換的演算法，可使用文字 描述如下：

15 一、演算法的基本結構 選擇 (Selection) 結構 較複雜的問題，通常無法只使用循序結構解決， 因此解題的演算法，必須能依據不同的條件， 選擇不同的解題步驟，這就是選擇結構的功能

16 一、演算法的基本結構 例如考試成績高於 90 分顯示 Excellent 的演算法，可以描述為 選擇 (Selection) 結構
單向選擇結構 例如考試成績高於 90 分顯示 Excellent 的演算法，可以描述為

17 一、演算法的基本結構 選擇 (Selection) 結構 雙向選擇結構 例如根據考試成績判斷是否及格的演算法可以描述如下：

18 一、演算法的基本結構 重複 (Iteration) 結構 重複結構是指演算法中，某一區塊的解題步驟需要反 覆執行，直到符合或是不符合某一條件式時，才會離 開重複執行的部份，這些條件式也是由邏輯判斷式所 組成的。重複結構也常被稱為「迴圈 (Loop)」

19 一、演算法的基本結構 重複 (Iteration) 結構 前測式重複結構 例如欣賞音樂會的聽眾入場的演算法，可用文字描述如下

20 一、演算法的基本結構 重複 (Iteration) 結構 後測式重複結構 例如捷運購票機購票的演算法，可用文字描述如下

21 一、演算法的基本結構 結構化設計 電腦解題中，使用「結構化設計」的演算法是很重要 的一項設計方法，它具有和模組化設計相同的優點， 所以常常被使用在電腦解題上 結構化設計的要素： 使用循序、選擇和重複三種基本結構 使用由上而下的解題方法設計 模組間應具有高度的獨立性，彼此不會互相影響

22 二、演算法的表示 文字 (自然語言) 流程圖 (Flowchart) 虛擬碼 (Pseudo Code)

23 二、演算法的表示 文字 使用自然語言來表示演算法，使用方便，最接近人類 的使用習慣。 但敘述易過於冗長，使用的詞彙認知若不同，易造成 誤解； 自然語言的種類繁多，不同的使用者常會發生認知差 異，因此用以表達演算法，會比較不精確

24 二、演算法的表示 流程圖 (Flowchart) 流程圖的功能是將解決問題的順序與步驟，使 用特定的圖形和符號表達出來。 為了方便流通與閱讀，流程圖的符號是固定且 統一的，每個符號都有其特殊意義，閱讀時很 容易一目了然

25 二、演算法的表示 流程圖 的符號

26 二、演算法的表示 循序結構的表示圖

27 二、演算法的表示 選擇結構的表示圖

28 二、演算法的表示 重複結構的表示圖

29 二、演算法的表示 流程圖 日常生活許多演算法都可 以使用流程圖表示，例如 大富翁遊戲的簡易規則

30 二、演算法的表示 流程圖 日常生活許多演算法都可 以使用流程圖表示，例如 大富翁遊戲的簡易規則
較複雜的演算法可使用模 組化表示，先用較大模組 的流程圖表示解題的演算 法，然後再逐步細緻化， 將各個大模組細分成多個 小模組，每個小模組再使 用各別的流程圖描述

31 二、演算法的表示 流程圖 以常用的自動櫃員機 ATM 為例，其簡易流程 圖可描述如右，其中「更 改密碼」與「提款」兩項 作業的模組，可另行使用 流程圖說明

32 二、演算法的表示 流程圖的優缺點 流程圖具有許多優點，但複雜的流程圖中，如果箭頭 符號太多交錯時，會使其所代表的演算法結構不易理 解，大型軟體系統常使用流程圖來表示系統的結構

33 二、演算法的表示 流程圖的繪製軟 體 文書處理、試算表、 或簡報軟體內建的繪 圖功能，通常可提供 繪製簡易的流程圖
複雜的流程圖可以用 專業的繪製軟體，例 如免費軟體 Dia、免 費的線上繪製流程圖； 或使用 Microsoft Visio 等軟體

34 二、演算法的表示 虛擬碼 (Pseudo Code)※
虛擬碼是一種介於自然語言與程式語言的敘述，使用 不正規且較直覺的符號，在演算法發展過程中，將問 題解決的邏輯表達出來。其撰寫與修改都比流程圖容 易，且沒有一定的語法標準，也不受限於某一種特定 的程式語言，通常是由使用者以特定的關鍵字、簡潔 的敘述或運算式來表示。

35 二、演算法的表示 使用虛擬碼的目的包含： 虛擬碼 (Pseudo Code)※
因為程式語言不容易直接寫出完整的解題架構， 且較缺乏直覺性，使用虛擬碼可以使程式設計師 不用分心於複雜的程式語言語法，能專注於問題 解決的處理過程。 寫作方便、敘述清晰、方便閱讀整體解題架構。 容易轉化成電腦程式。

36 二、演算法的表示 虛擬碼 (Pseudo Code)※ 使用虛擬碼時，常會使用指定敘述 (Assignment Statement)，將運算結果儲存起 來，本單元將以符號 「←」 來表示指定的意思， 指定敘述的表示法如下：

37 二、演算法的表示 虛擬碼 (Pseudo Code)※
其中變數是用來表示資料的名稱，所以上頁的表示式 可以說成是「將運算式的值指定給名稱」。例如

38 二、演算法的表示 基本結構 循序結構 相對應的例子如

39 二、演算法的表示 基本結構 選擇結構 相對應的例子如

40 二、演算法的表示 基本結構 重複結構 相對應的例子如

41 二、演算法的表示 巢狀結構 巢狀結構 (Nested Structure) 是在選擇或重複 結構中，包含其它選擇或重 複結構。
例如在 if ... then ... else 結構內又有 if ... then ... else 結構；或在 while ... do ... 結構內又有 if ... then ... else 結構

42 二、演算法的表示 巢狀結構 例如要依天氣狀況，決定活動項目的演算法，可以表示 如下

43 二、演算法的表示 巢狀結構 使用虛擬碼表示演算法時，應該適度縮排，以增加可讀 性，使演算法更容易除錯，例如

44 二、演算法的表示 巢狀結構 使用虛擬碼表示模組時，本單元將以下列方式表示一個完 整的模組，其中程序名稱代表模組的名稱。當虛擬碼的某 個敘述需要執行模組時，只要以使用「呼叫程序 程序名 稱」表示就可以了

45 二、演算法的表示 巢狀結構 例如簡易 ATM 的例子中，可以使用虛擬碼定義「提款 作業」和「更改密碼作業」兩個模組

46 二、演算法的表示 巢狀結構 完整的簡易 ATM 的電腦解題演算法，可以使用下列虛 擬碼表示

47 13-3 演算法與電腦解題

48 13-3 演算法與電腦解題 進行電腦解題時，要先針對所要解決的問題，形 成解題的概念，再將這些概念使用演算法表示出 來，最後再將演算法轉化成程式，讓電腦可以執 行，求出問題的解答

49 13-3 演算法與電腦解題 分析演算法是在不同的輸入大小時，計算該演算 法所執行的基本運算次數。當輸入資料的情況不 同時，許多演算法的執行次數也會不同。通常會 分析以下三種情形： 1.最差情形：演算法執行基本運算次數的最大值 2.最佳情況：演算法執行基本運算次數的最小值 3.平均情況：演算法執行基本運算次數的平均值

50 13-3 演算法與電腦解題 演算法的優劣和問題解決的品質息息相關，例 如
13-3 演算法與電腦解題 演算法的優劣和問題解決的品質息息相關，例 如 具有高效率和能搜尋到更多正確資料之演算法 的搜尋引擎，能提供更快速、更正確的搜尋資 料 更嚴密的加密演算法，將更能保障資料在網路 傳輸時的安全性 更有效率的排程演算法，將能為航空公司或貨 運公司設計出最省錢的交通路徑

51 13-3 演算法與電腦解題 並不是所有問題都可以使用電腦解決的，有些 問題是無法使用演算法解決的，例如判斷一個 程序是否會在有限的時間之內結束運行的問題， 便無法使用電腦解題

52 13-3 演算法與電腦解題 在可以使用電腦解決的問題中，有一部分問題 是可以找到具有較高執行效率的演算法，例如 溫度單位間的轉換、閏年的判斷等，這些問題 的演算法，通常可以在有限的時間內完成

53 13-3 演算法與電腦解題 有些問題，看起來似乎很容易使用電腦解決，但是實 際上，卻不容易找到一個有效率的演算法，即使使用 高效率的電腦，也很難找到最佳解，例如

54 13-3 演算法與電腦解題 貨運路線問題 要找出送貨的最短路徑，先要將所有可能的送貨路徑列出，再計算每條路徑的距離，才能找出最短的送貨路徑與距離。

55 13-3 演算法與電腦解題 貨運路線問題 如果使用電腦找出運送貨物到 20 家便利商店的最短路 徑，若電腦每秒鐘可排一條運送的路徑，共需要 × 1010 年 (一年約 3.15 × 107 秒)。若電腦每秒可排 一百萬(106)條路徑，也要 76,800 年才能找到最佳解。 即使使用更快的電腦，或使用更多部電腦同時平行處理， 所得到的效果也很有限，要找出此類問題更有效率的演 算法，有賴更進一步研究。

56 13-3 演算法與電腦解題 以輾轉相除法求兩數最大公因數

57 13-3 演算法與電腦解題 以輾轉相除法求兩數最大公因數-問題分析

58 13-3 演算法與電腦解題 以輾轉相除法求兩數最大公因數-解題方法 使用文字表示

59 13-3 演算法與電腦解題 以輾轉相除法求兩數最大公因數-解題方法 使用文字表示-測試與修正

60 13-3 演算法與電腦解題 以輾轉相除法求兩數最大公因數-解題方法 使用流程圖表示

61 13-3 演算法與電腦解題 以輾轉相除法求 兩數最大公因數 -解題方法 使用流程圖表示- 測試與修正

62 13-3 演算法與電腦解題 以輾轉相除法求兩數最大公因數-解題方法 使用虛擬碼表示

63 13-3 演算法與電腦解題 以輾轉相除法求兩數最大公因數-解題方法 使用虛擬碼表示-測試與修正

64 本章內容結束