結(jié)構(gòu)化程序設(shè)計

1、關(guān)于結(jié)構(gòu)化程序設(shè)計第一張，PPT共四十頁，創(chuàng)作于2022年6月一個程序應(yīng)包括兩個方面的內(nèi)容:對數(shù)據(jù)的描述：數(shù)據(jù)結(jié)構(gòu)(data structure)對操作的描述：算法(algorithm)著名計算機科學(xué)家沃思提出一個公式: 數(shù)據(jù)結(jié)構(gòu) + 算法 = 程序 數(shù)據(jù)結(jié)構(gòu)算法程序設(shè)計方法語言工具完整的程序設(shè)計應(yīng)該是:第二張，PPT共四十頁，創(chuàng)作于2022年6月 2.1 算法的概念 1. 算法:廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法”。方法1：1+2，+3，+4，一直加到100 加99次方法2：100+(1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50

2、加51次對同一個問題，可有不同的解題方法和步驟例： 求第三張，PPT共四十頁，創(chuàng)作于2022年6月 2. 兩大類計算機算法 為了有效地進行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。希望方法簡單，運算步驟少。計算機算法可分為兩大類別：數(shù)值運算算法：求數(shù)值解，例如求方程的根、求函數(shù)的定積分等。非數(shù)值運算：包括的面十分廣泛，最常見的是用于事務(wù)管理領(lǐng)域，例如圖書檢索、人事管理、行車調(diào)度管理等。第四張，PPT共四十頁，創(chuàng)作于2022年6月 3 . 算法的特性有窮性：包含有限的操作步驟。確定性：算法中的每一個步驟都應(yīng)當是確定的。 有零個或多個輸入：輸入是指在執(zhí)行算法時需要從外界取得必

3、要的信息。有一個或多個輸出：算法的目的是為了求解，“解” 就是輸出。 有效性：算法中的每一個步驟都應(yīng)當能有效地執(zhí)行，并得到確定的結(jié)果 。一個算法應(yīng)該具有以下特點：第五張，PPT共四十頁，創(chuàng)作于2022年6月4. 算法的描述算法的描述方法有多種：歸納為兩類：文字圖形（符號）第六張，PPT共四十頁，創(chuàng)作于2022年6月2.2 算法的描述方法可以用不同的方法表示算法，常用的有：自然語言傳統(tǒng)流程圖結(jié)構(gòu)化流程圖偽代碼PAD圖第七張，PPT共四十頁，創(chuàng)作于2022年6月 2.2.1 用自然語言表示算法 自然語言就是人們?nèi)粘Ｊ褂玫恼Z言，可以是漢語或英語或其它語言。 用自然語言表示通俗易懂，但文字冗長，容易出

4、現(xiàn)“歧義性”。自然語言表示的含義往往不大嚴格，要根據(jù)上下文才能判斷其正確含義，描述包含分支和循環(huán)的算法時也不很方便。 因此，除了那些很簡單的問題外，一般不用自然語言描述算法。 第八張，PPT共四十頁，創(chuàng)作于2022年6月 2.2.2 用流程圖表示算法 美國國家標準化協(xié)會ANSI(American National Standard Institute)規(guī)定了一些常用的流程圖符號：起止框判斷框處理框輸入/輸出框注釋框流向線連接點第九張，PPT共四十頁，創(chuàng)作于2022年6月小結(jié)：流程圖是表示算法的較好的工具。靈活、形象、直觀，可表示任何算法。一個流程圖包括以下幾部分 ：(1)表示相應(yīng)操作的框；(2

5、)帶箭頭的流程線；(3)框內(nèi)外必要的文字說明。 2.2.2 用流程圖表示算法（續(xù)） 第十張，PPT共四十頁，創(chuàng)作于2022年6月 2.2.2 用流程圖表示算法（續(xù)）傳統(tǒng)流程圖的弊端 傳統(tǒng)流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴格限制。 因此，使用者可以毫不受限制地使流程隨意地轉(zhuǎn)向，使流程圖變得毫無規(guī)律，閱讀者要花很大精力去追蹤流程，使人難以理解算法的邏輯。如圖： 第十一張，PPT共四十頁，創(chuàng)作于2022年6月傳統(tǒng)流程圖的流程可以是： 這種如同亂麻一樣的算法稱為BS型算法，意為一碗面條(A Bowl of Spaghetti)，亂無頭緒。缺點：難以閱讀、修改，使算法的可靠性和可維護

6、性難以保證。解決辦法：必須限制箭頭的濫用，即不允許無規(guī)律地使流程隨意轉(zhuǎn)向，只能順序地進行下去。 第十二張，PPT共四十頁，創(chuàng)作于2022年6月 2.2.3 用N-S圖表示算法 1973年美國學(xué)者I.Nassi和B.Shneiderman提出了一種新的流程圖形式。 在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個矩形框內(nèi)，在該框內(nèi)還可以包含其它的從屬于它的框，或者說，由一些基本的框組成一個大的框。這種流程圖又稱N-S結(jié)構(gòu)化流程圖。第十三張，PPT共四十頁，創(chuàng)作于2022年6月 N-S流程圖用以下的流程圖符號： (1)順序結(jié)構(gòu)(2)選擇結(jié)構(gòu)(3)循環(huán)結(jié)構(gòu)第十四張，PPT共四十頁，創(chuàng)作于2

7、022年6月 2.2.4 用偽代碼表示算法概念：偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法。特點：它如同一篇文章一樣 ，自上而下地寫下來。每一行(或幾行)表示一個基本操作。它不用圖形符號，因此書寫方便 、格式緊湊，也比較好懂，也便于向計算機語言算法(即程序)過渡。用處：適用于設(shè)計過程中需要反復(fù)修改時的流程描述。第十五張，PPT共四十頁，創(chuàng)作于2022年6月 2.2.5 簡單算法舉例 例2.1: 求12345 步驟1：先求12，得到結(jié)果2步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6步驟3：將6再乘以4，得24步驟4：將24再乘以5，得120太繁瑣如果要求121000，則要寫

8、999個步驟第十六張，PPT共四十頁，創(chuàng)作于2022年6月 S1：使p=1。 S2：使i=2。 S3：使pi，乘積仍放在變量p中，可表示為：pi p S4：使i的值加1，即i+1i 。 S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結(jié)束。最后得到p的值就是5!的值。可以設(shè)兩個變量：一個變量代表被乘數(shù)，一個變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結(jié)果, 算法可改寫： 第十七張，PPT共四十頁，創(chuàng)作于2022年6月S1：1pS2：3 iS3：pi pS4：i+2 pS5：若i11，返回S3。

9、否則，結(jié)束。 如果題目改為：求13511算法只需作很少的改動：算法簡練第十八張，PPT共四十頁，創(chuàng)作于2022年6月 用這種方法表示的算法具有通用性、靈活性。S3到S5組成一個循環(huán)，在實現(xiàn)算法時 要反復(fù)多次執(zhí)行S3，S4，S5等步驟，直到某一時刻，執(zhí)行S5步驟時經(jīng)過判斷，乘數(shù)i已超過規(guī)定的數(shù)值而不返回S3步驟為止。此時算法結(jié)束，變量p的值就是所求結(jié)果。第十九張，PPT共四十頁，創(chuàng)作于2022年6月 例2.2：將求5!的算法用流程圖表示 如果需要將最后結(jié)果打印出來，可在菱形框的下面加一個輸出框。 第二十張，PPT共四十頁，創(chuàng)作于2022年6月例2.3 將例2.1的求5!算法用N-S圖表示第二十一

10、張，PPT共四十頁，創(chuàng)作于2022年6月開始 置t的初值為1 置i的初值為2 當i=5，執(zhí)行下面操作： 使t=ti 使i=i+1 循環(huán)體到此結(jié)束 輸出t的值 結(jié)束也可以寫成以下形式： BEGIN算法開始 1t 2 i while i5 ti t i+1 i print t END算法結(jié)束例2.4 求5!。用偽代碼表示算法：第二十二張，PPT共四十頁，創(chuàng)作于2022年6月2.3 結(jié)構(gòu)化程序設(shè)計方法一、結(jié)構(gòu)化程序的三種基本結(jié)構(gòu) Bohra和Jacopini提出了以下三種基本結(jié)構(gòu)： 順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu) 用這三種基本結(jié)構(gòu)作為表示一個良好算法的基本單元。第二十三張，PPT共四十頁，創(chuàng)作于202

11、2年6月三種基本結(jié)構(gòu)的圖示： 順序結(jié)構(gòu)選擇結(jié)構(gòu)第二十四張，PPT共四十頁，創(chuàng)作于2022年6月循環(huán)結(jié)構(gòu)的圖示： 當型(While型)循環(huán)結(jié)構(gòu) 直到型(Until型)循環(huán) 第二十五張，PPT共四十頁，創(chuàng)作于2022年6月二、三種基本結(jié)構(gòu)的共同特點：(1)只有一個入口。 (2)只有一個出口。（請注意：一個菱形判斷框有兩個出口，而一個選擇結(jié)構(gòu)只有一個出口。不要將菱形框的出口和選擇結(jié)構(gòu)的出口混淆。）(3)結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到。(4)結(jié)構(gòu)內(nèi)不存在“死循環(huán)”(無終止的循環(huán))。 第二十六張，PPT共四十頁，創(chuàng)作于2022年6月 圖中沒有一條從入口到出口的路徑通過A框不正確的流程表示：流程內(nèi)的死循

12、環(huán)第二十七張，PPT共四十頁，創(chuàng)作于2022年6月 三、 結(jié)構(gòu)化程序設(shè)計方法優(yōu)點一個結(jié)構(gòu)化程序 就是用高級語言表示的結(jié)構(gòu)化算法。用三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這種程序便于編寫、便于閱讀、便于修改和維護。 結(jié)構(gòu)化程序設(shè)計強調(diào)程序設(shè)計風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。結(jié)構(gòu)化程序設(shè)計方法的基本思路是：把一個復(fù)雜問題的求解過程 分階段進行，每個階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。 第二十八張，PPT共四十頁，創(chuàng)作于2022年6月采取以下方法來保證得到結(jié)構(gòu)化的程序：自頂向下；逐步細化；模塊化設(shè)計；結(jié)構(gòu)化編碼。兩種不同的方法：自頂向下，逐步細化；自下而上，逐步積累。第二十

13、九張，PPT共四十頁，創(chuàng)作于2022年6月 用這種方法逐步分解，直到作者認為可以直接將各小段表達為文字語句為止。這種方法就叫 做“自頂向下，逐步細化”。 第三十張，PPT共四十頁，創(chuàng)作于2022年6月自頂向下，逐步細化方法的優(yōu)點： 考慮周全，結(jié)構(gòu)清晰，層次分明，作者容易寫，讀者容易看。如果發(fā)現(xiàn)某一部分中有一段內(nèi)容不妥，需要修改，只需找出該部分修改有關(guān)段落即可，與其它部分無關(guān)。我們提倡用這種方法設(shè)計程序。這就是用工程的方法設(shè)計程序。第三十一張，PPT共四十頁，創(chuàng)作于2022年6月 四、 結(jié)構(gòu)化程序設(shè)計過程1、確定算法 分析問題（建立數(shù)學(xué)模型、選擇公式），寫出算法描述2、編寫程序 用計算機語言寫出

14、算法的程序3、上機調(diào)試 輸入（編輯程序）編譯、連接、執(zhí)行程序 輸出結(jié)果 第三十二張，PPT共四十頁，創(chuàng)作于2022年6月舉例：張丘建算經(jīng)中提出“百雞問題”：假定公雞每只5元，母雞每只3元，小雞一元3只?，F(xiàn)有100元，要求買100只雞。問：公雞、母雞、小雞各多少只？（體會編程步驟） （1）分析：cocks+hens+chicks=100 5*cocks+3*hens+chicks/3=100 其中：0cocks19 0hens33 0chicks100 思路：依次取cocks的值域中的值，然后求其余兩數(shù)，看是否合乎題意。（累試法、枚舉法） 第三十三張，PPT共四十頁，創(chuàng)作于2022年6月舉例：張

15、丘建算經(jīng)中提出“百雞問題”：假定公雞每只5元，母雞每只3元，小雞一元3只?，F(xiàn)有100元，要求買100只雞。問：公雞、母雞、小雞各多少只？（體會編程步驟） cocks=0當cocks 19時 hens=0 當cocks 33時 找滿足題意的chicks數(shù) hens加1 cocks加1 算法描述： cocks=0當cocks 19時 找滿足題意的hens， chicks數(shù)。 cocks加1 細化第三十四張，PPT共四十頁，創(chuàng)作于2022年6月舉例：張丘建算經(jīng)中提出“百雞問題”：假定公雞每只5元，母雞每只3元，小雞一元3只?，F(xiàn)有100元，要求買100只雞。問：公雞、母雞、小雞各多少只？（體會編程步驟

16、） cocks=0 當cocks 19時 hens=0 當cocks 33時 chicks=100-cocks-hens 如果5*cocks+3*hens+chicks/3=100 則輸出 hens加1 cocks加1算法描述： cocks=0當cocks 19 hens=0 當cocks 33 找滿足題意的chicks數(shù) hens加1 cocks加1細化第三十五張，PPT共四十頁，創(chuàng)作于2022年6月（2）用計算機語言寫程序#include void main( ) int cocks=0,hens,chicks; while(cocks=19) hens=0; while(hens=33) chicks=100-cocks-hens; if ( 5.0*cocks+3.0*hens+chicks/3.0=100.0) printf(“%d,%d,%dn”,cocks,hens,chicks); he