9020C程序設(shè)計(jì)輔導(dǎo)課程02(閱讀)課件

輔導(dǎo)課程二輔導(dǎo)課程二2.1算法的概念2.2簡單算法舉例2.3算法的特性2.4怎樣表示一個(gè)算法2.5結(jié)構(gòu)化程序設(shè)計(jì)方法習(xí)題第2章程序的靈魂——算法2.1算法的概念第2章程序的靈魂——算法一個(gè)程序應(yīng)包括以下兩方面內(nèi)容:(1)對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)(datastructure)。(2)對操作的描述。即操作步驟，也就是算法(algorithm)。數(shù)據(jù)是操作的對象，操作的目的是對數(shù)據(jù)進(jìn)行加工處理，以得到期望的結(jié)果。作為程序設(shè)計(jì)人員，必須認(rèn)真考慮和設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和操作步驟(即算法)。因此，著名計(jì)算機(jī)科學(xué)家沃思(NikiklausWirth)提出一個(gè)公式 數(shù)據(jù)結(jié)構(gòu)+算法=程序一個(gè)程序應(yīng)包括以下兩方面內(nèi)容:實(shí)際上，一個(gè)程序除了以上兩個(gè)主要要素之外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程序設(shè)計(jì)方法進(jìn)行程序設(shè)計(jì)，并且用某一種計(jì)算機(jī)語言表示。因此，可以這樣表示：程序=算法+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計(jì)方法+語言工具和環(huán)境也就是說，以上4個(gè)方面是一個(gè)程序設(shè)計(jì)人員所應(yīng)具備的知識(shí)。在設(shè)計(jì)一個(gè)程序時(shí)要綜合運(yùn)用這幾方面的知識(shí)。在這4個(gè)方面中，算法是靈魂，數(shù)據(jù)結(jié)構(gòu)是加工對象，語言是工具，編程需要采用合適的方法。算法是解決“做什么”和“怎么做”的問題。程序中的操作語句，實(shí)際上就是算法的體現(xiàn)。顯然，不了解算法就談不上程序設(shè)計(jì)。實(shí)際上，一個(gè)程序除了以上兩個(gè)主要要素之外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程本章的學(xué)習(xí)目的：通過介紹有關(guān)算法的初步知識(shí)，讓學(xué)習(xí)者能夠了解如何編寫C程序，從而為后面各章的學(xué)習(xí)建立一定的基礎(chǔ)。本章的學(xué)習(xí)目的：通過介紹有關(guān)算法的初步知識(shí)，讓學(xué)習(xí)者能夠2.1算法的概念算法：為解決一個(gè)問題而采取的方法和步驟。對同一個(gè)問題，可以有不同的解題方法和步驟。方法有優(yōu)劣之分。有的方法只需進(jìn)行很少的步驟，而有些方法則需要較多的步驟。例：高斯求解1到100的連加。一般說，希望采用簡單的和運(yùn)算步驟少的方法。因此，為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。2.1算法的概念本書通過一些典型算法的介紹，幫助讀者了解如何設(shè)計(jì)一個(gè)算法，推動(dòng)讀者舉一反三。希望讀者通過本章介紹的例子了解怎樣提出問題，怎樣思考問題，怎樣表示一個(gè)算法。本書通過一些典型算法的介紹，幫助讀者了解如何設(shè)計(jì)一個(gè)算法，2.2簡單算法舉例例2.1求1×2×3×4×5?？梢杂米钤嫉姆椒ㄟM(jìn)行。步驟1：先求1×2，得到結(jié)果2。步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。這就是最后的結(jié)果。這樣的算法雖然是正確的，但太繁瑣。如果要求1×2×…×1000，則要寫999個(gè)步驟，顯然是不可取的。而且每次都直接使用上一步驟的數(shù)值結(jié)果(如2，6，24等)，也不方便。應(yīng)當(dāng)找到一種通用的表示方法。2.2簡單算法舉例可以設(shè)兩個(gè)變量，一個(gè)變量代表被乘數(shù)，一個(gè)變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。今設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結(jié)果?？梢詫⑺惴ǜ膶懭缦拢?S1：使p=1 S2：使i=2 S3：使p×i，乘積仍放在變量p中，可表示為 p×i=>p S4：使i的值加1，即i+1=>i S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結(jié)束。最后得到p的值就是5!的值。可以設(shè)兩個(gè)變量，一個(gè)變量代表被乘數(shù)，一個(gè)變量代表乘數(shù)。不另設(shè)如果題目改為求1×3×5×7×9×11。算法只需作很少的改動(dòng)即可： S1：1=>p S2：3=>i S3：p×i=>p S4：i+2=>i S5：若i≤11，返回S3；否則，結(jié)束?？梢钥闯?，用這種方法表示的算法具有通用性、靈活性。如果題目改為求1×3×5×7×9×11。例2.2有50個(gè)學(xué)生，要求將他們之中成績在80分以上者打印出來。用n表示學(xué)生學(xué)號，n1代表第一個(gè)學(xué)生學(xué)號，ni代表第i個(gè)學(xué)生學(xué)號。用g代表學(xué)生成績，gi代表第i個(gè)學(xué)生成績，算法可表示如下。 S1：1=>i S2：如果gi≥80，則打印ni和gi，否則不打印 S3：i+1=>i S4：如果i≤50，返回S2，繼續(xù)執(zhí)行；否則，算法結(jié)束。本例中，變量i作為下標(biāo)，用它來控制序號(第幾個(gè)學(xué)生，第幾個(gè)成績)。當(dāng)i超過50時(shí)，表示已對50個(gè)學(xué)生的成績處理完畢，算法結(jié)束。例2.2有50個(gè)學(xué)生，要求將他們之中成績在80分以上者打印例2.3判定2000—2500年中的每一年是否閏年，將結(jié)果輸出。在考慮算法時(shí)，應(yīng)當(dāng)仔細(xì)分析所需判斷的條件，如何一步一步縮小被判斷的范圍。有的問題，判斷的先后次序是無所謂的，而有的問題，判斷條件的先后次序是不能任意顛倒的，讀者可根據(jù)具體問題決定其邏輯。請自學(xué)例2.4和例2.5例2.3判定2000—2500年中的每一年是否閏年，將結(jié)果2.3算法的特性一個(gè)算法應(yīng)該具有以下特點(diǎn)：1.有窮性一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無限的。事實(shí)上，“有窮性”往往指“在合理的范圍之內(nèi)”。究竟什么算“合理限度”，并無嚴(yán)格標(biāo)準(zhǔn)，由人們的常識(shí)和需要而定。2.確定性算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的。2.3算法的特性3.有零個(gè)或多個(gè)輸入所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。一個(gè)算法也可以沒有輸入。4.有一個(gè)或多個(gè)輸出算法的目的是為了求解，“解”就是輸出。沒有輸出的算法是沒有意義的。5.有效性算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。對于不熟悉計(jì)算機(jī)程序設(shè)計(jì)的人來說，他們可以只需根據(jù)算法的要求給以必要的輸入，就能得到輸出的結(jié)果。但對于程序設(shè)計(jì)人員來說，必須會(huì)設(shè)計(jì)算法，并且根據(jù)算法編寫程序。3.有零個(gè)或多個(gè)輸入2.4怎樣表示一個(gè)算法為了表示一個(gè)算法，可以用不同的方法。常用的有自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼、PAD圖等。2.4.1用自然語言表示算法用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)“歧義性”。自然語言表示的含義往往不太嚴(yán)格，要根據(jù)上下文才能判斷其正確含義。此外，用自然語言描述包含分支和循環(huán)的算法，不很方便(如例2.5的算法)。因此，除了很簡單的問題以外，一般不用自然語言描述算法。2.4怎樣表示一個(gè)算法2.4.2用流程圖表示算法流程圖是用一些圖框表示各種操作。用圖形表示算法，直觀形象，易于理解。美國國家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號(見圖2.3)。圖2.32.4.2用流程圖表示算法圖2.3圖2.4中菱形框的作用是對一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的條件是否成立來決定如何執(zhí)行其后的操作。它有一個(gè)入口，兩個(gè)出口。圖2.4圖2.5圖2.4中菱形框的作用是對一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的2.4.3三種基本結(jié)構(gòu)和改進(jìn)的流程圖1.傳統(tǒng)流程圖的弊端傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴(yán)格限制。因此，使用者可以不受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使流程圖變得毫無規(guī)律。這種情況如圖2.13所示。這種算法難以閱讀，也難以修改，從而使算法的可靠性和可維護(hù)性難以保證。如果我們寫出的算法能限制流程的無規(guī)律任意轉(zhuǎn)向，閱讀起來就很方便。2.4.3三種基本結(jié)構(gòu)和改進(jìn)的流程圖但是，算法上難免會(huì)包含一些分支和循環(huán)，而不可能全部由一個(gè)一個(gè)框順序組成。為了解決這個(gè)問題，人們規(guī)定出幾種基本結(jié)構(gòu)，然后由這些基本結(jié)構(gòu)按一定規(guī)律組成一個(gè)算法結(jié)構(gòu)，整個(gè)算法的結(jié)構(gòu)是由上而下地將各個(gè)基本結(jié)構(gòu)順序排列起來的。這樣算法的質(zhì)量就能得到保證和提高。但是，算法上難免會(huì)包含一些分支和循環(huán)，而不可能全部由一個(gè)一個(gè)2.三種基本結(jié)構(gòu)1966年，Bohra和Jacopini提出了以下三種基本結(jié)構(gòu)，作為表示一個(gè)良好算法的基本單元。(1)順序結(jié)構(gòu)，最簡單的一種基本結(jié)構(gòu)。(2)選擇結(jié)構(gòu)，或稱選取結(jié)構(gòu)，或稱分支結(jié)構(gòu)，此結(jié)構(gòu)包含判斷框，根據(jù)判斷結(jié)果選擇執(zhí)行的內(nèi)容。有兩種分支結(jié)構(gòu)：雙分支結(jié)構(gòu)多分支結(jié)構(gòu)(3)循環(huán)結(jié)構(gòu)，它又稱重復(fù)結(jié)構(gòu)。有兩類循環(huán)結(jié)構(gòu)：當(dāng)型循環(huán)直到型循環(huán)2.三種基本結(jié)構(gòu)AB判斷循環(huán)體判斷處理1處理2BA)順序結(jié)構(gòu)B)分支結(jié)構(gòu)C)循環(huán)結(jié)構(gòu)AB判斷循環(huán)體判斷處理1處理2BA)順序結(jié)構(gòu)B)分支結(jié)構(gòu)C)循環(huán)體判斷判斷分支1分支2分支n……(A)DO-UNTIL循環(huán)結(jié)構(gòu)(B)多分支結(jié)構(gòu)A循環(huán)體判斷判斷分支1分支2分支n……(A)DO-UNTIL循s=0i=1i<=100s=s+i開始Yi=i+1N輸出S結(jié)束例：求從1到100的和s=0i=1i<=100s=s+i開始Yi=i+1N輸出S結(jié)2.4.4用N-S流程圖表示算法既然用基本結(jié)構(gòu)的順序組合可以表示任何復(fù)雜的算法結(jié)構(gòu)，那么基本結(jié)構(gòu)之間的流程線就屬多余的了。1973年美國學(xué)者I.Nassi和B.Shneiderman提出了一種新的流程圖形式。在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框，或者說，由一些基本的框組成一個(gè)大的框。這種流程圖又稱N-S結(jié)構(gòu)化流程圖。2.4.4用N-S流程圖表示算法N-S流程圖用以下的流程圖符號：順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)N-S流程圖用以下的流程圖符號：DO-WHILE部分循環(huán)條件DO-UNTIL部分循環(huán)條件A（D)DO-WHILE循環(huán)(E)DO-UNTIL循環(huán)(F)調(diào)用子程序第一個(gè)任務(wù)第二個(gè)任務(wù)第三個(gè)任務(wù)(A)順序True條件（B）IF-THEN-ELSECASE條件值1值2…值3(C)CASE多分支FalseDO-WHILE部分循環(huán)條件DO-UNTIL部分循環(huán)條件A（s=0,i=1i<=100s=s+ii=i+1輸出s例：求從1到100的和s=0,i=1i<=100s=s+ii=i+1輸通過教材的幾個(gè)例子，學(xué)習(xí)者可以了解如何用N-S流程圖表示算法。N-S流程圖設(shè)計(jì)的優(yōu)點(diǎn)功能域明確不可能任意控制轉(zhuǎn)移很容易確定全局和局部數(shù)據(jù)的作用域。通過教材的幾個(gè)例子，學(xué)習(xí)者可以了解如何用N-S流程圖表示算法2.4.5用偽代碼表示算法用傳統(tǒng)的流程圖和N-S圖表示算法，直觀易懂，但畫起來比較費(fèi)事。因此，流程圖適宜表示一個(gè)算法，但在設(shè)計(jì)算法過程中使用不是很理想。為了設(shè)計(jì)算法時(shí)方便，常用一種稱為偽代碼(pseudocode)的工具。偽代碼是用介于自然語言和計(jì)算機(jī)語言之間的文字和符號來描述算法。它如同一篇文章，自上而下地寫下來。每一行(或幾行)表示一個(gè)基本操作。它不用圖形符號，因此書寫方便、格式緊湊，也比較好懂，便于向計(jì)算機(jī)語言算法(即程序)過渡。2.4.5用偽代碼表示算法偽碼表示中計(jì)算機(jī)語言中具有的語句關(guān)鍵字用英文表示，其他的可用漢字表示?？傊员阌跁鴮懞烷喿x為原則。用偽代碼寫算法并無固定的、嚴(yán)格的語法規(guī)則，只要把意思表達(dá)清楚，并且書寫的格式要寫成清晰易讀的形式。從以上例子可以看到：偽代碼書寫格式比較自由，容易表達(dá)出設(shè)計(jì)者的思想。同時(shí)，用偽代碼寫的算法很容易修改。用偽代碼很容易寫出結(jié)構(gòu)化的算法。以上的常用的算法表示方法，在程序設(shè)計(jì)中可以根據(jù)需要和習(xí)慣任意選用。軟件專業(yè)人員一般習(xí)慣使用偽代碼，考慮到國內(nèi)廣大初學(xué)人員的情況，書在以后各章中主要采用形象化的N-S圖表示算法。偽碼表示中計(jì)算機(jī)語言中具有的語句關(guān)鍵字用英文表示，其他的可用2.4.6用計(jì)算機(jī)語言表示算法描述算法只是用不同的形式表示操作的步驟。而要得到運(yùn)算結(jié)果，就必須實(shí)現(xiàn)算法。用計(jì)算機(jī)解題，也就是要用計(jì)算機(jī)實(shí)現(xiàn)算法。計(jì)算機(jī)是無法識(shí)別流程圖和偽代碼的。只有用計(jì)算機(jī)語言編寫的程序才能被計(jì)算機(jī)執(zhí)行。用計(jì)算機(jī)語言表示算法必須嚴(yán)格遵循所用語言的語法規(guī)則，這是和偽代碼不同的。應(yīng)當(dāng)強(qiáng)調(diào)說明的是，寫出了C程序，仍然只是描述了算法，并未實(shí)現(xiàn)算法，只有運(yùn)行程序才是實(shí)現(xiàn)算法。應(yīng)該說，用計(jì)算機(jī)語言表示的算法是計(jì)算機(jī)能夠執(zhí)行的算法。2.4.6用計(jì)算機(jī)語言表示算法2.5結(jié)構(gòu)化程序設(shè)計(jì)方法前面介紹了結(jié)構(gòu)化的算法和三種基本結(jié)構(gòu)。一個(gè)結(jié)構(gòu)化程序就是用高級語言表示的結(jié)構(gòu)化算法。用三種基本結(jié)構(gòu)組成的程序必然是結(jié)構(gòu)化的程序，這種程序便于編寫、閱讀、修改和維護(hù)。這就減少了程序出錯(cuò)的機(jī)會(huì)，提高了程序的可靠性。結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。如果面臨一個(gè)復(fù)雜的問題，是難以一下子寫出一個(gè)層次分明、結(jié)構(gòu)清晰、算法正確的程序的。結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路是，把一個(gè)復(fù)雜問題的求解過程分階段進(jìn)行，每個(gè)階段處理的問題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。2.5結(jié)構(gòu)化程序設(shè)計(jì)方法具體說，采取以下方法保證得到結(jié)構(gòu)化的程序。自頂向下逐步細(xì)化模塊化設(shè)計(jì)結(jié)構(gòu)化編碼我們應(yīng)當(dāng)掌握自頂向下、逐步細(xì)化的設(shè)計(jì)方法。這種設(shè)計(jì)方法的過程是將問題求解由抽象逐步具體化的過程。具體說，采取以下方法保證得到結(jié)構(gòu)化的程序。例如：讀入三個(gè)數(shù)，找出并打印其中的最大數(shù)一級算法①

輸入X1,X2,X3②

將X1與X2的大數(shù)存于MAX中③

將X3與MAX的大數(shù)存于MAX中④

輸出MAX例如：讀入三個(gè)數(shù)，找出并打印其中的最大數(shù)一級算法二級求精②將X1與X2地大數(shù)存于MAX中 Ifx1>x2thenmax=x1 Else max=x2③將X3與MAX的大數(shù)存于MAX中 Ifx3>maxthenmax=x3二級求精程序（C語言）main(){floatx1,x2,x3,max;scanf(“%f,%f,%f”,&x1,&x2,&x3);If(x1>x2) max=x1;else max=x2;If(x3>max) max=x3;Printf(“themaxnumberis:%f”,max);}程序（C語言）可見，模塊化設(shè)計(jì)的思想實(shí)際上是一種“分而治之”的思想，把一個(gè)大任務(wù)分為若干個(gè)子任務(wù)，每一個(gè)子任務(wù)就相對簡單了。本章內(nèi)容十分重要，是學(xué)習(xí)后面各章的基礎(chǔ)。學(xué)習(xí)程序設(shè)計(jì)的目的不只是學(xué)習(xí)一種特定的語言，而是學(xué)習(xí)進(jìn)行程序設(shè)計(jì)的一般方法。掌握了算法就是掌握了程序設(shè)計(jì)的靈魂，再學(xué)習(xí)有關(guān)的計(jì)算機(jī)語言知識(shí)，就能夠順利地編寫出任何一種語言的程序?？梢?，模塊化設(shè)計(jì)的思想實(shí)際上是一種“分而治之”的思想，把一個(gè)輔導(dǎo)課程二輔導(dǎo)課程二2.1算法的概念2.2簡單算法舉例2.3算法的特性2.4怎樣表示一個(gè)算法2.5結(jié)構(gòu)化程序設(shè)計(jì)方法習(xí)題第2章程序的靈魂——算法2.1算法的概念第2章程序的靈魂——算法一個(gè)程序應(yīng)包括以下兩方面內(nèi)容:(1)對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)(datastructure)。(2)對操作的描述。即操作步驟，也就是算法(algorithm)。數(shù)據(jù)是操作的對象，操作的目的是對數(shù)據(jù)進(jìn)行加工處理，以得到期望的結(jié)果。作為程序設(shè)計(jì)人員，必須認(rèn)真考慮和設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和操作步驟(即算法)。因此，著名計(jì)算機(jī)科學(xué)家沃思(NikiklausWirth)提出一個(gè)公式 數(shù)據(jù)結(jié)構(gòu)+算法=程序一個(gè)程序應(yīng)包括以下兩方面內(nèi)容:實(shí)際上，一個(gè)程序除了以上兩個(gè)主要要素之外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程序設(shè)計(jì)方法進(jìn)行程序設(shè)計(jì)，并且用某一種計(jì)算機(jī)語言表示。因此，可以這樣表示：程序=算法+數(shù)據(jù)結(jié)構(gòu)+程序設(shè)計(jì)方法+語言工具和環(huán)境也就是說，以上4個(gè)方面是一個(gè)程序設(shè)計(jì)人員所應(yīng)具備的知識(shí)。在設(shè)計(jì)一個(gè)程序時(shí)要綜合運(yùn)用這幾方面的知識(shí)。在這4個(gè)方面中，算法是靈魂，數(shù)據(jù)結(jié)構(gòu)是加工對象，語言是工具，編程需要采用合適的方法。算法是解決“做什么”和“怎么做”的問題。程序中的操作語句，實(shí)際上就是算法的體現(xiàn)。顯然，不了解算法就談不上程序設(shè)計(jì)。實(shí)際上，一個(gè)程序除了以上兩個(gè)主要要素之外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程本章的學(xué)習(xí)目的：通過介紹有關(guān)算法的初步知識(shí)，讓學(xué)習(xí)者能夠了解如何編寫C程序，從而為后面各章的學(xué)習(xí)建立一定的基礎(chǔ)。本章的學(xué)習(xí)目的：通過介紹有關(guān)算法的初步知識(shí)，讓學(xué)習(xí)者能夠2.1算法的概念算法：為解決一個(gè)問題而采取的方法和步驟。對同一個(gè)問題，可以有不同的解題方法和步驟。方法有優(yōu)劣之分。有的方法只需進(jìn)行很少的步驟，而有些方法則需要較多的步驟。例：高斯求解1到100的連加。一般說，希望采用簡單的和運(yùn)算步驟少的方法。因此，為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。2.1算法的概念本書通過一些典型算法的介紹，幫助讀者了解如何設(shè)計(jì)一個(gè)算法，推動(dòng)讀者舉一反三。希望讀者通過本章介紹的例子了解怎樣提出問題，怎樣思考問題，怎樣表示一個(gè)算法。本書通過一些典型算法的介紹，幫助讀者了解如何設(shè)計(jì)一個(gè)算法，2.2簡單算法舉例例2.1求1×2×3×4×5?？梢杂米钤嫉姆椒ㄟM(jìn)行。步驟1：先求1×2，得到結(jié)果2。步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。這就是最后的結(jié)果。這樣的算法雖然是正確的，但太繁瑣。如果要求1×2×…×1000，則要寫999個(gè)步驟，顯然是不可取的。而且每次都直接使用上一步驟的數(shù)值結(jié)果(如2，6，24等)，也不方便。應(yīng)當(dāng)找到一種通用的表示方法。2.2簡單算法舉例可以設(shè)兩個(gè)變量，一個(gè)變量代表被乘數(shù)，一個(gè)變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。今設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結(jié)果?？梢詫⑺惴ǜ膶懭缦拢?S1：使p=1 S2：使i=2 S3：使p×i，乘積仍放在變量p中，可表示為 p×i=>p S4：使i的值加1，即i+1=>i S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結(jié)束。最后得到p的值就是5!的值。可以設(shè)兩個(gè)變量，一個(gè)變量代表被乘數(shù)，一個(gè)變量代表乘數(shù)。不另設(shè)如果題目改為求1×3×5×7×9×11。算法只需作很少的改動(dòng)即可： S1：1=>p S2：3=>i S3：p×i=>p S4：i+2=>i S5：若i≤11，返回S3；否則，結(jié)束?？梢钥闯觯眠@種方法表示的算法具有通用性、靈活性。如果題目改為求1×3×5×7×9×11。例2.2有50個(gè)學(xué)生，要求將他們之中成績在80分以上者打印出來。用n表示學(xué)生學(xué)號，n1代表第一個(gè)學(xué)生學(xué)號，ni代表第i個(gè)學(xué)生學(xué)號。用g代表學(xué)生成績，gi代表第i個(gè)學(xué)生成績，算法可表示如下。 S1：1=>i S2：如果gi≥80，則打印ni和gi，否則不打印 S3：i+1=>i S4：如果i≤50，返回S2，繼續(xù)執(zhí)行；否則，算法結(jié)束。本例中，變量i作為下標(biāo)，用它來控制序號(第幾個(gè)學(xué)生，第幾個(gè)成績)。當(dāng)i超過50時(shí)，表示已對50個(gè)學(xué)生的成績處理完畢，算法結(jié)束。例2.2有50個(gè)學(xué)生，要求將他們之中成績在80分以上者打印例2.3判定2000—2500年中的每一年是否閏年，將結(jié)果輸出。在考慮算法時(shí)，應(yīng)當(dāng)仔細(xì)分析所需判斷的條件，如何一步一步縮小被判斷的范圍。有的問題，判斷的先后次序是無所謂的，而有的問題，判斷條件的先后次序是不能任意顛倒的，讀者可根據(jù)具體問題決定其邏輯。請自學(xué)例2.4和例2.5例2.3判定2000—2500年中的每一年是否閏年，將結(jié)果2.3算法的特性一個(gè)算法應(yīng)該具有以下特點(diǎn)：1.有窮性一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無限的。事實(shí)上，“有窮性”往往指“在合理的范圍之內(nèi)”。究竟什么算“合理限度”，并無嚴(yán)格標(biāo)準(zhǔn)，由人們的常識(shí)和需要而定。2.確定性算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的。2.3算法的特性3.有零個(gè)或多個(gè)輸入所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。一個(gè)算法也可以沒有輸入。4.有一個(gè)或多個(gè)輸出算法的目的是為了求解，“解”就是輸出。沒有輸出的算法是沒有意義的。5.有效性算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。對于不熟悉計(jì)算機(jī)程序設(shè)計(jì)的人來說，他們可以只需根據(jù)算法的要求給以必要的輸入，就能得到輸出的結(jié)果。但對于程序設(shè)計(jì)人員來說，必須會(huì)設(shè)計(jì)算法，并且根據(jù)算法編寫程序。3.有零個(gè)或多個(gè)輸入2.4怎樣表示一個(gè)算法為了表示一個(gè)算法，可以用不同的方法。常用的有自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼、PAD圖等。2.4.1用自然語言表示算法用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)“歧義性”。自然語言表示的含義往往不太嚴(yán)格，要根據(jù)上下文才能判斷其正確含義。此外，用自然語言描述包含分支和循環(huán)的算法，不很方便(如例2.5的算法)。因此，除了很簡單的問題以外，一般不用自然語言描述算法。2.4怎樣表示一個(gè)算法2.4.2用流程圖表示算法流程圖是用一些圖框表示各種操作。用圖形表示算法，直觀形象，易于理解。美國國家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號(見圖2.3)。圖2.32.4.2用流程圖表示算法圖2.3圖2.4中菱形框的作用是對一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的條件是否成立來決定如何執(zhí)行其后的操作。它有一個(gè)入口，兩個(gè)出口。圖2.4圖2.5圖2.4中菱形框的作用是對一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的2.4.3三種基本結(jié)構(gòu)和改進(jìn)的流程圖1.傳統(tǒng)流程圖的弊端傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴(yán)格限制。因此，使用者可以不受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使流程圖變得毫無規(guī)律。這種情況如圖2.13所示。這種算法難以閱讀，也難以修改，從而使算法的可靠性和可維護(hù)性難以保證。如果我們寫出的算法能限制流程的無規(guī)律任意轉(zhuǎn)向，閱讀起來就很方便。2.4.3三種基本結(jié)構(gòu)和改進(jìn)的流程圖但是，算法上難免會(huì)包含一些分支和循環(huán)，而不可能全部由一個(gè)一個(gè)框順序組成。為了解決這個(gè)問題，人們規(guī)定出幾種基本結(jié)構(gòu)，然后由這些基本結(jié)構(gòu)按一定規(guī)律組成一個(gè)算法結(jié)構(gòu)，整個(gè)算法的結(jié)構(gòu)是由上而下地將各個(gè)基本結(jié)構(gòu)順序排列起來的。這樣算法的質(zhì)量就能得到保證和提高。但是，算法上難免會(huì)包含一些分支和循環(huán)，而不可能全部由一個(gè)一個(gè)2.三種基本結(jié)構(gòu)1966年，Bohra和Jacopini提出了以下三種基本結(jié)構(gòu)，作為表示一個(gè)良好算法的基本單元。(1)順序結(jié)構(gòu)，最簡單的一種基本結(jié)構(gòu)。(2)選擇結(jié)構(gòu)，或稱選取結(jié)構(gòu)，或稱分支結(jié)構(gòu)，此結(jié)構(gòu)包含判斷框，根據(jù)判斷結(jié)果選擇執(zhí)行的內(nèi)容。有兩種分支結(jié)構(gòu)：雙分支結(jié)構(gòu)多分支結(jié)構(gòu)(3)循環(huán)結(jié)構(gòu)，它又稱重復(fù)結(jié)構(gòu)。有兩類循環(huán)結(jié)構(gòu)：當(dāng)型循環(huán)直到型循環(huán)2.三種基本結(jié)構(gòu)AB判斷循環(huán)體判斷處理1處理2BA)順序結(jié)構(gòu)B)分支結(jié)構(gòu)C)循環(huán)結(jié)構(gòu)AB判斷循環(huán)體判斷處理1處理2BA)順序結(jié)構(gòu)B)分支結(jié)構(gòu)C)循環(huán)體判斷判斷分支1分支2分支n……(A)DO-UNTIL循環(huán)結(jié)構(gòu)(B)多分支結(jié)構(gòu)A循環(huán)體判斷判斷分支1分支2分支n……(A)DO-UNTIL循s=0i=1i<=100s=s+i開始Yi=i+1N輸出S結(jié)束例：求從1到100的和s=0i=1i<=100s=s+i開始Yi=i+1N輸出S結(jié)2.4.4用N-S流程圖表示算法既然用基本結(jié)構(gòu)的順序組合可以表示任何復(fù)雜的算法結(jié)構(gòu)，那么基本結(jié)構(gòu)之間的流程線就屬多余的了。1973年美國學(xué)者I.Nassi和B.Shneiderman提出了一種新的流程圖形式。在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個(gè)矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框，或者說，由一些基本的框組成一個(gè)大的框。這種流程圖又稱N-S結(jié)構(gòu)化流程圖。2.4.4用N-S流程圖表示算法N-S流程圖用以下的流程圖符號：順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)N-S流程圖用以下的流程圖符號：DO-WHILE部分循環(huán)條件DO-UNTIL部分循環(huán)條件A（D)DO-WHILE循環(huán)(E)DO-UNTIL循環(huán)(F)調(diào)用子程序第一個(gè)任務(wù)第二個(gè)任務(wù)第三個(gè)任務(wù)(A)順序True條件（B）IF-THEN-ELSECASE條件值1值2…值3(C)CASE多分支FalseDO-WHILE部分循環(huán)條件DO-UNTIL部分循環(huán)條件A（s=0,i=1i<=100s=s+ii=i+1輸出s例：求從1到100的和s=0,i=1i<=100s=s+ii=i+1輸通過教材的幾個(gè)例子，學(xué)習(xí)者可以了解如何用N-S流程圖表示算法。N-S流程圖設(shè)計(jì)的優(yōu)點(diǎn)功能域明確不可能任意控制轉(zhuǎn)移很容易確定全局和局部數(shù)據(jù)的作用域。通過教材的幾個(gè)例子，學(xué)習(xí)者可以了解如何用N-S流程圖表示算法2.4.5用偽代碼表示算法用傳統(tǒng)的流程圖和N-S圖表示算法，直觀易懂，但畫起來比較費(fèi)事。因此，流程圖適宜表示一個(gè)算法，但在設(shè)計(jì)算法過程中使用不是很理想。為了設(shè)計(jì)算法時(shí)方便，常用一種稱為偽代碼(pseudocode)的工具。偽代碼是用介于自然語言和計(jì)算機(jī)語言之間的文字和符號來描述算法。它如同一篇文章，自上而下地寫下來。每一行(或幾行)表示一個(gè)基本操作。它不用圖形符號，因此書寫方便、格式緊湊，也比較好懂，便于向計(jì)算機(jī)語言算法(即程序)過渡。2.4.5用偽代碼表示算法偽碼表示中計(jì)算機(jī)語言中具有的語句關(guān)鍵字用英文表示，其他的可用漢字表示?？傊员阌跁鴮懞烷喿x為原則。用偽代碼寫算法并無固定的、嚴(yán)格的語法規(guī)則，只要把意思表達(dá)清楚，并且書寫的格式要寫成清晰易讀的形式。從以上例子可以看到：偽代碼書寫格式比較自由，容易表達(dá)出設(shè)計(jì)者的思想。同時(shí)，用偽代碼寫的算法很容易修改。用偽代碼很容易寫出結(jié)構(gòu)化的算法。以上的常用的算法表示方法，在程序設(shè)計(jì)中可以根據(jù)需要和習(xí)慣任意選用。軟件專業(yè)人員一般習(xí)慣使用偽代碼，考慮到國內(nèi)廣大初學(xué)人員的情況，書在以后各章中主要采用形象化的N-S圖表示算法。偽碼表示中計(jì)算機(jī)語言中具有的語句關(guān)鍵字用英文表示，其他的可用2.4.6用計(jì)算機(jī)語言表示算法描