结构化程式设计的观念.doc

21第四章 演算法4-1 結構化程式設計的觀念4-2 演算法的介紹4-3 氣泡排序演算法簡述4-4 二分搜尋演算法簡述4-5 快速排序演算法簡述本章要介紹的演算法(Algorithm)就是用文字或虛擬碼，表達解決問題的先後順序和步驟。(全華)一般常常須要用到流程圖 4-1 結構化程式設計的觀念一般要設計結構化程式，會使用流程圖(Flow Chart)及虛擬碼(Pseudo code)當輔助工具。方便設計者理清程式架構及邏輯次序，讓程式更週詳，並能協助錯誤偵錯，詳細說明如下節所述。4-1-1流程圖(Flow Chart)在樓房建築時均須依紙張設計施工圖，程式設計時亦相同，可是程式設計的施工圖稱為流程圖。流程圖就是利用各種特定的符號，以圖表的方式說明工作處理的方法和步驟，其主要的功用是規劃程式及幫助程式的閱讀。流程圖依其用途分為系統流程圖與程式流程圖，前者用以描述整個工作系統中各部門之間的關係，後者是利用簡明、標準的圖形及線條來描述程式的處理步驟，有助於簡化問題的描述，並幫助他人了解整個程式的架構，不同形狀的符號用末端帶有箭號的流程線連接起來，符號的形狀表示執行工作的種類，流程線的方向則代表執行的順序，以下將常用的程式流程圖符號列表如表4-1。表 4-1 流程圖符號表名稱符號範例VB敍述或意義1.起訖符號End,程式的開始或結束2.輸入/輸出符號A=InputBox(“訊息”)，Msgbox(“訊息”)，表示資料之輸入或結果的輸出3.處理符號表示執行或處理某些工作4.決策判斷符號If A5 then S=S+1End if5.副程式符號Sub Sb(x,y) End subFunction F(a,b)End Function6.報表符號表示以列表機印出報表文件7.迴圈符號表示程式迴圈控制變數初值及終值的設定8.連結符號u轉接到另一頁v避免流線交叉w避免交線太長9.流程符號表示程式進行的方向10.註解符號表示對某一流程加以註解繪圖流程圖的輔助工具稱為流程規，若要使用電腦軟體則可以使用Visio，因為Visio已將各種現成的符號作成物件，使用者可以方便改變大小及位置。4-1-2 虛擬碼(Pseudo code)程式設計除了可用流程圖外，另一種輔助工具稱為虛擬碼(Pseudo code)，所謂虛擬碼就是將解決問題的方法，逐步以文字表達的方式條列出來，其使用的文字類似英文文句。通常我們在解決一個問題時，必須有計劃的處理，始能達到迅速有效目的。同樣在我們利用電腦來幫助我們處理問題時，因為電腦本身不像人腦具有思考能力，所以我們就必須先將解決問題的方法與步驟以及次序告訴電腦，電腦便會依照程式邏輯順序的指示逐步執行。當我們接觸到問題，直接把程式寫出來是非常困的，尤其是遇到複雜問題時，可說是無從寫起，最好的方法是先把解決問題的想法，一個歩驟一個步驟的記下來，此種方法即是虛擬碼。虛擬碼最直接簡單的方法就是文字敍述，用一般口語化的文字，而把它整理條序陳述出來而已。例如，到加油站加油，以下列文字敘述(一) 把車開到加油站。(二) 打開油門。(三) 加油。(四) 蓋上油門。(五) 依加油數量付錢。虛擬碼是來描述程式語言，但其寫法並非以程式語言的指令來描寫，而是一般通用的句子來構成的一種描述語言的方式，其中虛擬碼具備有明確而有次序的步驟，而且有效的解決問題，進而推展至程式語言時，不會受到程式語言類別的限制，也就是虛擬碼適用於各種程式語言。4-1-3 結構化程式設計開發VB應用程式的五個階段第一階段：分析問題階段第二階段：設計演算法及流程圖第三階段：設計使用者介面第四階段：撰寫程式碼第五階段：驗證程式正確性開發大型系統的程式時，上述五個階段通常由專人分項負責。結構化程式設計 隨著電腦的普及，與應用環境的多元化，電腦應用程式設計的工作，日益複雜。往往程式是由一組工作人員分工撰寫，日後可能又必須面臨修正或維護的工作。所以，一套有系統的軟體開發方法是非常重要的。 程式發展的過程，包括分析問題、找出演算法、繪製流程圖、撰寫程式、測試程式、編寫文件等步驟。每一個步驟都有其銜接上的重要性，也都發展初一些實現的策略。在撰寫程式階段，最常採用的方法是結構化程式設計。 結構化程式設計的好處，除了撰寫程式時容易分工，以及程式結構好、方便閱讀之外，也有助於測試程式、編寫文件，以及日後維護。當然在演算法和流程圖方面，也要配合提供可使用結構化程式設計的安排。本章將介紹結構化程式設計的意義，以及透過Visual Basic實現結構化程式設計的方法。 結構化程式設計的意義 結構化程式設計的觀念，是一種由上而下(Top-Down)，先將程式功能分解誠多個獨立子功能的模組(Module)，就每個模組的功能設計一段程式，最後再整合成一個功能完整的程式。結構化程式設計的特性如下： 一、唯一出口整個程式的執行應該只有一個程式執行結束的出口。結構化程式只有一處可以結束程式的執行，避免程式執行時，有多處可以結束執行工作。 二、由上而下細分功能結構化程式設計的第一步，是由上而下逐步細化程式功能，把一個大程式先分解成幾個功能獨立的模組。如果有某個模組的功能還可以細分，應該再將該模組分解成更小的模組。如圖一所示，以某成績檔案管理系統為例，各個模組間形成階層式的功能結構圖。 三、模組化程式設計每個模組都是功能獨立的程式片段。在程式語言中，通常模組程式可分為副程式(Subroutine)和函數(Function)兩種。模組和磨組之間，以傳遞資料(稱為參數或引數)的方式連繫。模組的劃分要講求功能的獨立，同一層模組之間，關聯越少越好。 四、使用三種基本控制結構結構化的程式，不論在副程式、或函數中，都以第五章所介紹的循序、選擇、重複等三種基本控制結構，將程式表達出來。 五、避免使用GoTo敘述GoTo敘述會使控制結構混亂，不便於閱讀程式。隨意使用GoTo敘述，也會影響程式的模組化。所以，結構化程式設計是儘量避免使用GoTo敘述的。 六、程式閱讀性高除了模組化程式設計和使用三種基本控制結構，使程式較易閱讀之外，採用結構化程式設計，還要注意取有意義的變數名稱、使用程式註解、適當的程式內縮排列等，以提高程式的閱讀性。 圖一 各模組間階層式功能結構圖 Visual Basic 使用程序(Procedure)來實現模組化程式設計。每個程序都是功能獨立的程式區段，或可視為軟體元件。使用程序的好處在於容易偵錯和減少重複性工作。常用的Visual Basic程序可分為Sub程序(副程式)和Function程序(函數)兩大類。其中Sub程序又區分為一般程序和事件程序兩類。4-2 結構化程式設計寫出好的程式必須經過幾個步驟：(1)研究問題的內容，確認輸入資料是什麼，要經過怎麼樣的處理，以及那些資料要輸出；(2)準備一份對問題有詳細描述的說明書；(3)利用流程圖和虛擬碼等工具來解決問題，這種漸進的程序通常稱為由上而下逐步細化法(Top-down stepwise refinement)；(4)用適當的程式語言把解決的方法寫成程式，這個步驟也包括了一些文書性的雜務，像是鍵入程式、修改拼錯的字等等；(5)測試和除錯(debug)，測試程式就是看看它是否符合要求，如果不合就必須除錯，找出那裏不對勁並加以改正。這個步驟要一直進行到程式可以正常工作為止)；(6)對程式加上註解(documentation)，註解應該在程式發展的每一個階段中就慢慢寫好了，但程式拿來使用之後，還應加上詳細而正確的註解，使得別人也能看懂這個程式，要修改時也比較方便。設計程式時，先想後寫這句話特別重要。好的程式應該是容易了解、容易操作、容易修改以及沒有什麼錯誤，而且還要有效率、正確、可靠和功能完備。有效率的意思是，在使用最少主記憶體的情況下也能訊速的執行，正確的意思是合乎原來的需要；可靠的意思是它能在一些沒有料想到的情況下工作；功能完備則是它可以接受約合法輸入範圍很廣。為了達到以上要求許多人紛紛提倡結構化程式設計，其理念大致如以下四點:1. 由上而下(Top-Down)設計方法：將工作分割成數個子工作，每個子工作再細分，直到所有工作都能用簡單指令完成，如圖 4-1。2. 模組化(Module)：整個程式是由許多的模組所組合而成的，每一模組負責特定工作，而且只有一個入口及一個出口，請看圖 4-1。圖 4-1 成績處理各模組間階層式功能結構圖3. 儘量避免使用GoTo指令：Goto是一種無條件的跳躍，已違反結構化程式設計的原則，因為由由上而下及模組化 的原則，我們希望任何的子工作均是去作一件事，且入口及出口明確，而Goto卻是去一個未知的地方。如果一個程式有兩個以上的Goto指令，就容易造成程式的混亂，維護及偵錯的困難。良好的程式設計應用程序(或稱副程式)代替Goto，因為程序代表一件事，有去有回。4. 使用循序、選擇及重覆等三種基本結構：經過實驗證明所有複雜的程式邏輯皆可用循序(Sequence)、選擇(Select)及重覆(Iteration)等三種結構，茲將三種基本結構以流程圖及虛擬碼說明如下:(1) 循序結構(sSequence Structure)循序結構的流程圖及虛擬碼如下流程圖： 虛擬碼：.鬧鐘叫關鬧鐘起床.圖 4-1(2) 選擇結構(Select Structure)常用的選擇結構有以下三種，演算法中的If及Then稱為關鍵字或保留字。 If then 流程圖： 虛擬碼：.If 肚子餓 then 吃東西.圖 4-2 If then Else流程圖： 虛擬碼：.If 肚子餓 then 吃東西Else 往前走Endif.圖 4-3 Select Case 流程圖： 虛擬碼：.Select Case 交通費種類Case 飛機 交通費=1000Case 火車 交通費=800Case 汔車 交通費=600EndSelect .圖 4-4(3) 重覆結構(Repetition Structure)常用的重覆結構有三種，分別是重覆固定次數迴圈，前測試迴圈及後測試迴圈，請看以下流程圖及虛擬碼的表示。 重覆固定次數迴圈(電腦自動計數，若完成預定次數，則自動離開，特別適用於預知執行次數者)。流程圖： 虛擬碼：.For I=1 to 5 夾菜 吃飯 喝湯Next I.圖 4-5 前測試迴圈末知欲重覆次數，但須先測試條件成立才可執行連續的重覆動作，如自動提款機的提款作業，每次付款前均須測試存戶密碼、餘額及提款機內現鈔再行付款。流程圖： 虛擬碼：.Do 餘額足夠? 付款Loop.圖 4-6 後測試迴圈末知欲重覆次數，但可先執行動作再測試條件者，如一般人的吃飯動作，一面吃飯一面測試是否吃飽。流程圖： 虛擬碼：.Do 吃飯 夾菜Loop 未吃飽？.圖 4-7範例4-1-3A 試分別以流程圖、虛擬碼及VB程式完成下列事項演算法設計下列程式1.輸入三個數，計算其和與平均，並輸出結果。2.求1+2+3+10之和，並輸出結果。 解1.流程圖： 虛擬碼：輸入A,B,C三個數合計三個數S=A+B+C求三數平均AVG=S/3顯示合計及平均VB程式：A=InputBox(“輸入A值”,0)A=InputBox(“輸入A值”,0)A=InputBox(“輸入A值”,0)S=A+B+CAVG=S/3PRINT S,AVG2. 已知重覆次數，使用For Next流程圖： 虛擬碼：迴圈1到10重覆執行10次作累加動作S=S+I迴圈結束顯示合計SVB程式：For I=1 to 10 S=S+1Next IPRINT S,AVG結構化程式優點 、利用由上而下的設計觀念，層次分明容易了解。、每一個模組很小，而且獨立，容易書寫。、可簡化程式的測試與除錯，容易維護。、可提高生產效率，降低程式開發的費用。 流程圖及虛擬碼說明範例4-2 演算法的介紹二、演算法演算法(Algorithm)的定義：為解決某一問題而規劃出來，一系列有次序且明確的步驟。一般來說，當利用電腦來解決問題時，在實際動手去撰寫程式之前，程式設計師先要構思出可行且有效率的處理程序，這些抽象的思考過程通常採用演算法來作具體的呈現，以作為撰寫程式的依據。就像我們在建房子前必須先繪製藍圖，然後依據藍圖就可以建出堅固而且合用的建築物，而演算法就是程式設計師的藍圖。一個好的演算法，必須滿足下列五個條件： 1. 有 限 性：就是要在有限個步驟內解決問題。 2. 明 確 性：每個步驟都必須清楚地表達出來。 3. 輸入資料：包含零個或一個以上的輸入資料。 4. 輸出資料：至少產生一個輸出。 5. 有 效 性：每一個步驟如果交由設計師利用紙和筆來執行，必須能在有限的時間內完成。演算法的常用表示方式有兩種：一種是使用流程圖，另一種是使用演算法語言。2.演算法語言(Algorithm)演算法語言是使用文字敘述來說明處理問題的步驟，有點類似程式語言，由於此種表示方式較易於改寫成任何程式語言，複雜的演算法大都採用此種方式來描述演算法。演算法是指完成一個任務所需要的具體步驟和方法。也就是說給定初始狀態或輸入資料，能夠得出所要求或期望的終止狀態或輸出資料。演算法常常含有重複的步驟和一些比較或邏輯判斷。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間複雜度與時間複雜度來衡量。所謂演算法(Algorithm)，就是解決問題的處理步驟。以電腦解決一個問題，可能有許多種不同的方法。每一種方法都是一個演算法。此階段的工作，就是要想出一種較好的解決問題方法。所謂好的方法，主要是指電腦執行此演算法的速度較快者。 當電腦程式運作的較慢的時候，我們第一個想到問題可能是電腦硬體設備不夠，CPU或記憶體不夠大，要升級嗎？似乎要花不少錢呢？如果這時你手頭剛好不方便的話，那怎麼辦呢？有沒有什麼方法可以解決呢？或許你該考慮一下是否該換一個更快的演算法了。演算法 解決問題的計算方法. 演算法特性 1. 不一定有輸入 2. 最少一個輸出 3. 有限性 4. 明確性 5. 有效性 虛擬碼 虛擬碼(pseudo-code)本身並非程式語言,它是描述程式邏輯的結構化自然語言。 演算法是指完成一個任務所需要的具體步驟和方法。也就是說給定初始狀態或輸入資料，能夠得出所要求或期望的終止狀態或輸出資料。演算法常常含有重複的步驟和一些比較或邏輯判斷。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間複雜度與時間複雜度來衡量。演算法的時間複雜度演算法的時間複雜度是指演算法需要消耗的時間資源。一般來說，電腦演算法是問題規模n 的函式f(n)，演算法的時間複雜度也因此記做 因此，問題的規模n 越大，演算法執行的時間的增長率與f(n) 的增長率正相關，稱作漸進時間複雜度（Asymptotic Time Complexity）。編輯 演算法的空間複雜度演算法的空間複雜度是指演算法需要消耗的空間資源。其計算和表示方法與時間複雜度類似，一般都用複雜度的漸近性來表示。同時間複雜度相比，空間複雜度的分析要簡單得多。演算法的特徵輸入：一個演算法必須有零個或以上輸入量。 輸出：一個演算法應有一個或以上輸出量，輸出量是演算法計算的結果。 明確性：演算法的描述必須無歧義，以保證演算法的實際執行結果是精確地符合要求或期望，通常要求實際執行結果是確定的。 有限性：依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統類比的一串運算，而圖靈機器只有有限個狀態、有限個輸入符號和有限個轉移函數（指令）。而一些定義更規定演算法必須在有限個步驟內完成任務。 有效性：又稱可行性。能夠實作，演算法中描述的操作都是可以透過已經實作的基本運算執行有限次來實作。演算法的實作演算法不單單可以用電腦程式來實作，也可以在人工神經網路、電路或者機械裝置上實作。編輯 範例編輯 求最大值演算法這是演算法的一個簡單的例子。我們有一串隨機數列。我們的目的是找到這個數列中最大的數。如果將數列中的每一個數位看成是一顆豆子的大小,可以將下面的演算法形象地稱為撿豆子：首先將第一顆豆子放入口袋中。 從第二顆豆子開始檢查，如果正在檢查的豆子比口袋中的還大，則將它撿起放入口袋中，同時丟掉原先口袋中的豆子。直到最後一顆豆子。 最後口袋中的豆子就是所有的豆子中最大的一顆。 下面是一個形式演算法，用近似於程式語言的虛擬碼（偽代碼）表示给定：一个数列“list，以及数列的长度length(list) largest = list1for counter = 2 to length(list): if listcounter largest: largest = listcounterprint largest符號說明:= 用於表示賦值。即：右邊的值被賦予給左邊的變數。 Listcounter用於表示數列中的第counter項。例如：如果counter的值是5，那麼Listcounter表示數列中的第5項。 = 用於表示小於或等於。 編輯 求最大公約數演算法求兩個自然數的最大公約數 設兩個變數 M 和 N如果 M N，則交換 M 和 N M 被 N 除，得到餘數 R 判斷 R0，正確則 N 即為最大公約數，否則下一步 將 N 賦值給 M，將 R 賦值給 N，重做第一步。 用BASIC 代碼表示 IF M N THEN SWAP M,N DO WHILE R 0 R = M MOD N M = N N = R LOOP PRINT N4-3 氣泡排序演算法簡述排序是指將一堆資料依某一鍵值(key) 來排排序(Sorting)的基本功能是依某種條件將資料項目按順序排列，例如依照數字的大小由小至大排列，或是按筆畫順序排列姓名Bubble Sort 範例30 20 60 40 10 50 第一回合結果 20 30 40 10 50 60 第二回合結果 20 30 10 40 50 60 第三回合結果 20 10 30 40 50 60 第四回合結果 10 20 30 40 50 60 第五回合結果 10 20 30 40 50 604-4 二分搜尋演算法簡述二分搜尋法（binary search） 例：有一陣列A存放已排序資料為2,5,7,11,22,34，試問22存在於這個A陣列的第幾個位置。 說明： （1）假設x是我們要找的；將陣列分為兩部分，找出此陣列的中間點y，如果x大於y，則選擇中間點右邊的陣列，反之，則選擇左邊的陣列。 （2）反覆做（1）的動作，直到找到x，或是只剩一個數時，如果最後一個數不等於x，則x不在此數列中。 （3）二分搜尋法較適用於已排序好的情況。 輸入：n個已排序資料的陣列A 欲找尋的數k 輸出：22在陣列A中的位置location 演算法： 圖解： 二分搜尋法 限制:資料必須已經排序過。 概念:(假設資料遞增排序過)將資料以中間項分為前後兩半,將搜尋值與中間項比較, 若等於中間項則找到,若比中間項大則從後半繼續同樣方式搜尋,若比中間項小則從前半繼續同樣方式搜尋, 直到找到或沒有該元素存在為止。 實作:範例:從1、4、6、33、47、58中搜尋資料33 位置1位置2位置3位置4位置5位置6說明1x4x6x334758計算(1+6)/2的整數部分得到中央位置為3(註:1為現階段搜尋範圍的第一筆資料位置編號,6為現階段搜尋範圍的最後一筆資料位置編號.),所以資料33與第3個位置的資料6比較,33比較大所以不用理會第3個位置之前的資料(註:第3個位置的資料比較過了,當然也不理會了.)從第3個位置之後的資料繼續搜尋.搜尋範圍 比較後不理會範圍 中央位置下一階段搜尋範圍 1x4x6x3347x58x計算(4+6)/2的整數部分得到中央位置為5(註:4為現階段搜尋範圍的第一筆資料位置編號,6為現階段搜尋範圍的最後一筆資料位置編號.),所以資料33與第5個位置的資料47比較,33較小所以不用理會第5個位置之後的資料(註:第5個位置的資料比較過了,當然也不理會了.)從第5個位置之前的資料繼續搜尋.搜尋範圍 下一階段搜尋範圍 中央位置比較後不理會範圍 1x4x6x33有此資料47x58x計算(4+4)/2的整數部分得到中央位置為4(註:4為現階段搜尋範圍的第一筆資料位置編號,4也是為現階段搜尋範圍的最後一筆資料位置編號.),所以資料33與第4個位置的資料33比較,二者相等故有此資料.搜尋範圍中央位置4-5 快速排序演算法簡述Quick Sort (快速排序法) 排序方法: 將尚未排序好之資料分割(partition) 成兩組, 分割後其中一組之資料必須小於或等於另一組之資料 分割基本原則: 由要進行分割之群組中選一筆資料當成中間值 將所有小於或等於中間值之資料搬移到中間值左邊 將所有比中間值大的資料搬移到中間值右邊 分割完畢後, 等於是排好一筆資料(即中間值被排好) 將分割好之兩組資料, 分別再以上述同樣方式進行分割成更小的群組, 當分割至每一群組只有一筆資料時, 即完成排序排序效率: 比較次數: O(N*Log2N) O(N2) 平均而言: O(N*Log2N)快速排序法（Quick sort）說明： （1）先找一個指標（為求方便，通常是第一個數），將，數列中大於這個指標的數，都放在右邊，反之則放在左邊。 （2）和合併排序法相似，但快速排序法的優點是比較節省空間。 輸入：n個資料的陣列A 輸出：A陣列中的資料依一定的次序排列 演算法：private Sub Quick_Sort()Dim A(n) As IntegerDim n As IntegerDim high As IntegerDim low As IntegerDim pivot As IntegerIf high low then Partition(low,high,pivot)Quick_Sort(low,pivot-1)Quick_Sort(piovt+1,high)End IfEnd Sub實例： 9-5-8快速排序法最後我們來討論另外一種平均執行情形非常好的排序方法，是由C.A.R. Hoare所創作的快速排序法，它可以說是在我們所介紹的各種排序法中，有最好的平均執行情形 (Best average behavior) 。在介入排序法中，用來控制介入動作的鍵Ai是被放進已排好順序之部份序列 (B1.Bi-1) 的正確位置，而快速排序法是將鍵Ai放到整個序列 (Ai+1.Aj) 的正確位置。因此鍵Ai被放入As的位置後，As則已達定點，且一切isAis，則AjAs。故在把As放入正確位置後，原來的序列就分割成包含記錄Ai.As-1與記錄As+1.Aj兩個序列，現在把As+1.Aj放入堆疊，Ai.As-1呼叫排序副程式，再把第二次產生的後面序列放進堆疊，前面序列再呼叫排序副程式，重覆以上動作，直至前面序列皆已完成排序手續，再自堆疊取元素出來排序，如有須要再分別進堆疊與呼叫排序副程式，直到堆疊為空堆疊，排序完成，其演繹邏輯如下：程序列印1. Procedure Qsort (m,n)2. IF mn THEN i=m:j=n+13. REPEAT i=i+1 UNTIL A(i)A(m)4. REPEAT j=j-1 UNTIL A(j)A(m)5. IF ij THEN SWAP A(i),A(j):GOTO 36. SWAP A(m),A(j)7. QSORT (m,j-1)8. QSORT (j+1,n)9. END程序說明1. 假設A陣列指標m，n之間欲進行排序。2. 前面第m+1個位置開始往後找，找到比第m個位置大的元素為止，設該位置指標為i。3. 從後面第n個位置開始往前找，找到比第m個位置小的元素為止，設該位置指標為j。4. 若ij時SWAP A(m),a(J)。此時A(m)這個元素調至A(j)並達到定點，對於所有cj則A(c)(j)，且所有cA(j)，原序列以A(j)隔成兩個序列。其中c為A陣列中任意指標。5. 將後段序列進堆疊，前段序列重覆2，3，4的動作，並將新的後段進堆疊、新的前段重覆2，3，4的動作，直到前段剩下序列長度為1的已完全排序序列，並依序至堆疊取未排序段來排序，直到堆疊為空為止，則此時序列全部排序完成。範例9-5-8試根據快速排序演繹邏輯寫一程式，處理資料的排序工作。主題使讀者應用堆疊，了解計算機遞迴結構。輸入50，99，32，76，16，43，71，13，45，11，23，15，66，77，34，18，91