第二章:改變程序流程算法和流程圖2.1.1算法計(jì)算機(jī)語(yǔ)言只是一種工具。光學(xué)習(xí)語(yǔ)言的規(guī)則還不夠，最重要的是學(xué)會(huì)針對(duì)各種類型的問題，擬定出有效的解決方法和步驟即算法。有了正確而有效的算法，可以利用任何一種計(jì)算機(jī)高級(jí)語(yǔ)言編寫程序，使計(jì)算機(jī)進(jìn)行工作。因此，設(shè)計(jì)算法是程序設(shè)計(jì)的核心。并非只有“計(jì)算”的問題才有算法。廣義地說(shuō)，為解決一個(gè)問題而采取的方法和步驟，稱為“算法”。不要把“計(jì)算方法”（computationalmethod）和“算法”（algorithm）這兩個(gè)詞混淆。前者指的是求數(shù)值解的近似方法，后者是指解決問題的一步一步的過程。在解一個(gè)數(shù)值計(jì)算問題時(shí)，除了要選擇合適的計(jì)算方法外，還要根據(jù)這個(gè)計(jì)算方法寫出如何讓計(jì)算機(jī)一步一步執(zhí)行以求解的算法。對(duì)于計(jì)算機(jī)外行來(lái)說(shuō)，他們可以只使用別人已設(shè)計(jì)好的現(xiàn)成算法，只需根據(jù)算法的要求給以必要的輸入，就能得到輸出的結(jié)果。對(duì)他們來(lái)說(shuō)，算法如同一個(gè)“黑箱子”一樣，他們可以不了解“黑箱子”中的結(jié)構(gòu)，只是從外部特性上了解算法的作用，即可方便地使用算法。但對(duì)于程序設(shè)計(jì)人員來(lái)說(shuō)，必須會(huì)設(shè)計(jì)算法，并且根據(jù)算法編寫程序。對(duì)同一個(gè)問題，可以有不同的解題方法和步驟。例如，求1+2+3+…+100，可以先進(jìn)行1+2，再加3，再加4，一直加到100，也可采取100+(1+99)+(2+98)+…+(49+51)+50＝100+50+49×100＝5050。還可以有其它的方法。當(dāng)然，方法有優(yōu)劣之分。有的方法只需進(jìn)行很少的步驟，而有些方法則需要較多的步驟。一般說(shuō)，希望采用方法簡(jiǎn)單，運(yùn)算步驟少的方法。因此，為了有效地進(jìn)行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。一個(gè)計(jì)算問題的解決過程通常包含下面幾步:

確立所需解決的問題以及最后應(yīng)達(dá)到的要求。必須保證在任務(wù)一開始就對(duì)它有詳細(xì)而確切的了解，避免模棱兩可和含混不清之處。

分析問題構(gòu)造模型。在得到一個(gè)基本的物理模型后，用數(shù)學(xué)語(yǔ)言描述它，例如列出解題的數(shù)學(xué)公式或聯(lián)立方程式，即建立數(shù)學(xué)模型。

選擇計(jì)算方法。如定積分求值問題，可以用矩形法、梯形法或辛普生法等不同的方法。因此用計(jì)算機(jī)解題應(yīng)當(dāng)先確定用哪一種方法來(lái)計(jì)算。專門有一門學(xué)科“計(jì)算方法”，就是研究用什么方法最有效、最近似地實(shí)現(xiàn)各種數(shù)值計(jì)算的，換句話說(shuō)，計(jì)算方法是研究數(shù)值計(jì)算的近似方法的。

確定算法和畫流程圖。在編寫程序之前，應(yīng)當(dāng)整理好思路，設(shè)想好一步一步怎樣運(yùn)算或處理，即為“算法”。把它用框圖畫出來(lái)，用一個(gè)框表示要完成的一個(gè)或幾個(gè)步驟，它表示工作的流程，稱為流程圖。它能使人們思路清楚，減少編寫程序中的錯(cuò)誤。

編寫程序。

程序調(diào)試，即試算。一個(gè)復(fù)雜的程序往往不是一次上機(jī)就能通過并得到正確的結(jié)果的，需要反復(fù)試算修改，才得到正確的可供正式運(yùn)行的程序。

正式運(yùn)行得到必要的運(yùn)算結(jié)果。2.1.2流程圖為了表示一個(gè)算法，可以用不同的方法。常用的有：自然語(yǔ)言；傳統(tǒng)流程圖；結(jié)構(gòu)化流程圖；偽代碼；PAD圖等。這里我們主要介紹流程圖。a)

傳統(tǒng)流程圖用圖表示的算法就是流程圖。流程圖是用一些圖框來(lái)表示各種類型的操作，在框內(nèi)寫出各個(gè)步驟，然后用帶箭頭的線把它們連接起來(lái)，以表示執(zhí)行的先后順序。用圖形表示算法，直觀形象，易于理解。美國(guó)國(guó)家標(biāo)準(zhǔn)化協(xié)會(huì)ANSI曾規(guī)定了一些常用的流程圖符號(hào)，為世界各國(guó)程序工作者普遍采用。最常用的流程圖符號(hào)見圖。

處理框（矩形框），表示一般的處理功能。

判斷框（菱形框），表示對(duì)一個(gè)給定的條件進(jìn)行判斷，根據(jù)給定的條件是否成立決定如何執(zhí)行其后的操作。它有一個(gè)入口，二個(gè)出口。

輸入輸出框（平行四邊形框）。

起止框（圓弧形框），表示流程開始或結(jié)束。

連接點(diǎn)（圓圈），用于將畫在不同地方的流程線連接起來(lái)。如圖中有兩個(gè)以1標(biāo)志的連接點(diǎn)(在連接點(diǎn)圈中寫上“l(fā)”)則表示這兩個(gè)點(diǎn)是連接在一起的，相當(dāng)于一個(gè)點(diǎn)一樣。用連接點(diǎn)，可以避免流程線的交叉或過長(zhǎng)，使流程圖清晰。

流程線（指向線），表示流程的路徑和方向。

注釋框,是為了對(duì)流程圖中某些框的操作做必要的補(bǔ)充說(shuō)明，以幫助閱讀流程圖的人更好地理解流程圖的作用。它不是流程圖中必要的部分，不反映流程和操作。程序框圖表示程序內(nèi)各步驟的內(nèi)容以及它們的關(guān)系和執(zhí)行的順序。它說(shuō)明了程序的邏輯結(jié)構(gòu)?？驁D應(yīng)該足夠詳細(xì)，以便可以按照它順利地寫出程序，而不必在編寫時(shí)臨時(shí)構(gòu)思，甚至出現(xiàn)邏輯錯(cuò)誤。流程圖不僅可以指導(dǎo)編寫程序，而且可以在調(diào)試程序中用來(lái)檢查程序的正確性。如果框圖是正確的而結(jié)果不對(duì)，則按照框圖逐步檢查程序是很容易發(fā)現(xiàn)其錯(cuò)誤的。流程圖還能作為程序說(shuō)明書的一部分提供給別人，以便幫助別人理解你編寫程序的思路和結(jié)構(gòu)。例：對(duì)一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。所謂素?cái)?shù)，是指除l和該數(shù)本身之外，不能被其它任何整數(shù)整除的數(shù)。例如，13是素?cái)?shù)，因?yàn)樗荒鼙?，3，4，…，12整除。判斷一個(gè)數(shù)N(N＞3)是否素?cái)?shù)的方法是很簡(jiǎn)單的：將N作為被除數(shù)，將2到(N—1)各個(gè)整數(shù)輪流作為除數(shù)，如果都不能被整除，則N為素?cái)?shù)。算法可以表示如下：①輸入N的值。②I＝2。③N被I除。④如果余數(shù)為0，表示N能被I整除，則打印N“不是素?cái)?shù)”，算法結(jié)束。否則繼續(xù)。⑤I＝I+1。⑥如果I≤N－l，返回③。否則打印N“是素?cái)?shù)”。然后結(jié)束。實(shí)際上．N不必被2到(N一1)的整數(shù)除，只需被2到N/2間整數(shù)除即可，甚至只需被2到之間的整數(shù)除即可。例如，判斷13是否素?cái)?shù)，只需將13被2，3除即可，如都除不盡，N必為素?cái)?shù)。步驟⑥可改為：⑥：如果I≤，返回③。否則算法結(jié)束。Fortran代碼文件為[e_212_01.f][e_212_02.f]。a)

三種基本結(jié)構(gòu)傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對(duì)流程線的使用沒有嚴(yán)格限制。因此，使用者可以毫不受限制地使流程隨意地轉(zhuǎn)來(lái)轉(zhuǎn)去，使流程圖變得毫無(wú)規(guī)律，閱讀者要花很大精力去追蹤流程，使人難以理解算法的邏輯。如果我們寫出的算法能限制流程的無(wú)規(guī)律任意轉(zhuǎn)向，而像一本書那樣，由各章各節(jié)順序組成，那樣，閱讀起來(lái)就很方便，不會(huì)有任何困難，只需從頭到尾順序地看下去即可。為了提高算法的質(zhì)量，使算法的設(shè)計(jì)和閱讀方便，必須限制箭頭的濫用，即不允許無(wú)規(guī)律地使流程亂轉(zhuǎn)向，只能按順序地進(jìn)行下去。但是，算法上難免會(huì)包含一些分支和循環(huán)，而不可能全部由一個(gè)一個(gè)框順序組成。如上例不是由各框順序進(jìn)行的，包含一些流程的向前或向后的非順序轉(zhuǎn)移。為了解決這個(gè)問題，人們?cè)O(shè)想，如果規(guī)定出幾種基本結(jié)構(gòu)，然后由這些基本結(jié)構(gòu)按一定規(guī)律組成一個(gè)算法結(jié)構(gòu)，就如同用一些基本預(yù)制構(gòu)件來(lái)搭成房屋一樣，整個(gè)算法的結(jié)構(gòu)是由上而下地將各個(gè)基本結(jié)構(gòu)順序排列起來(lái)的。1966年，Bohra和Jacoplni提出了以下三種基本結(jié)構(gòu)，用這三種基本結(jié)構(gòu)作為表示一個(gè)良好算法的基本單元。

順序結(jié)構(gòu)：如圖所示的虛線框內(nèi)，A和B兩個(gè)框是順序執(zhí)行的。順序結(jié)構(gòu)是最簡(jiǎn)單的一種基本結(jié)構(gòu)。

選擇結(jié)構(gòu)：如圖所示的虛線框中包含一個(gè)判斷框。根據(jù)給定的條件p是否成立而選擇執(zhí)行A和B。p條件可以是“x＞0”或“x＞y”等。注意，無(wú)論p條件是否成立，只能執(zhí)行A或B之一，不可能既執(zhí)行A又執(zhí)行B。無(wú)論走哪一條路徑，在執(zhí)行完A或B之后將脫離選擇結(jié)構(gòu)。A或B兩個(gè)框中可以有一個(gè)是空的，即不執(zhí)行任何操作。

循環(huán)結(jié)構(gòu)：又稱重復(fù)結(jié)構(gòu)，即反復(fù)執(zhí)行某一部分的操作。有兩類循環(huán)結(jié)構(gòu)：

當(dāng)型(While)：當(dāng)給定的條件p成立時(shí)，執(zhí)行A框操作，然后再判斷p條件是否成立。如果仍然成立，再執(zhí)行A框，如此反復(fù)直到p條件不成立為止。此時(shí)不執(zhí)行A框而脫離循環(huán)結(jié)構(gòu)。

直到型(Until)：先執(zhí)行A框，然后判斷給定的p條件是否成立。如果p條件不成立，則再執(zhí)行A，然后再對(duì)p條件作判斷。如此反復(fù)直到給定的p條件成立為止。此時(shí)脫離本循環(huán)結(jié)構(gòu)。注意兩種循環(huán)結(jié)構(gòu)的異同：(1)兩種循環(huán)結(jié)構(gòu)都能處理需要重復(fù)執(zhí)行的操作。(2)當(dāng)型循環(huán)是“先判斷(條件是否成立)，后執(zhí)行(A框)”。而直到型循環(huán)則是“先執(zhí)行(A框)，后判斷(條件)”。(3)當(dāng)型循環(huán)是當(dāng)給定條件成立滿足時(shí)執(zhí)行A框，而直到型循環(huán)則是在給定條件不成立時(shí)執(zhí)行A框。同一個(gè)問題既可以用當(dāng)型循環(huán)來(lái)處理，也可以用直到型循環(huán)來(lái)處理。對(duì)同一個(gè)問題，如分別用當(dāng)型循環(huán)結(jié)構(gòu)和直到型循環(huán)結(jié)構(gòu)來(lái)處理的話，則兩者結(jié)構(gòu)中的判斷框內(nèi)的判斷條件恰為互逆條件。Fortran77和90/95標(biāo)準(zhǔn)都不提供dountil語(yǔ)句，CompaqVisualFortran也不提供此擴(kuò)展（但有些計(jì)算機(jī)系統(tǒng)則提供），因此需要將直到型循環(huán)轉(zhuǎn)換成一個(gè)當(dāng)型循環(huán)結(jié)構(gòu)：直到型循環(huán)等于一個(gè)A框加上一個(gè)當(dāng)型循環(huán)，同時(shí)將給定的判斷條件“取反”。b)

結(jié)構(gòu)流程圖1973年美國(guó)學(xué)者I.Nassi和B.Shneiderman提出了一種新的流程圖形式。在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個(gè)矩形框內(nèi)。在該框內(nèi)還可以包含其它的從屬于它的框，即可由一些基本的框組成一個(gè)大的框。這種適于結(jié)構(gòu)化程序設(shè)計(jì)的流程圖稱N-S結(jié)構(gòu)化流程圖，它用以下的流程圖符號(hào)：(1)順序結(jié)構(gòu)：A和B兩個(gè)框組成一個(gè)順序結(jié)構(gòu)。(2)選擇結(jié)構(gòu)：當(dāng)p條件成立時(shí)執(zhí)行A操作，p不成立則執(zhí)行B操作結(jié)構(gòu)。(3)循環(huán)結(jié)構(gòu)：當(dāng)型循環(huán)結(jié)構(gòu)下，圖符表示先判斷后執(zhí)行，當(dāng)p條件成立時(shí)反復(fù)執(zhí)行A操作，直到p條件不成立為止。直到型循環(huán)結(jié)構(gòu)下，圖符表示先執(zhí)行后判斷，當(dāng)p條件不成立時(shí)反復(fù)執(zhí)行A操作，直到p條件成立為止。用以上三種N-S流程圖中的基本框．可以組成復(fù)雜的N-S流程圖，以表示算法。例：將判別素?cái)?shù)的算法用N-S流程圖表示。上面的非結(jié)構(gòu)化流程圖不是由三種基本結(jié)構(gòu)組成的：圖中間的循環(huán)部分有兩個(gè)出口，不符合基本結(jié)構(gòu)的特點(diǎn)。由于不能直接分解為三種基本結(jié)構(gòu)，應(yīng)當(dāng)先作必要的變換再用N-S流程圖的三種基本結(jié)構(gòu)的符號(hào)來(lái)表示。即將第一個(gè)菱形框的兩個(gè)出口匯合在一點(diǎn)。其方法是設(shè)一個(gè)標(biāo)志值K，它的初始狀態(tài)為0(表示N為素?cái)?shù))，當(dāng)K≠0時(shí)為非素?cái)?shù)。注意當(dāng)型和直到型的判斷條件。Fortran代碼文件為[e_212_03.f90]。N-S圖表示算法的優(yōu)點(diǎn)是：比傳統(tǒng)流程圖緊湊易畫，尤其是它廢除了流程線。整個(gè)算法結(jié)構(gòu)是由各個(gè)基本結(jié)構(gòu)按順序組成的，其上下順序就是執(zhí)行時(shí)的順序。寫算法和看算法只需從上到下進(jìn)行就可以了，十分方便。歸納起來(lái)，一個(gè)結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的；在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個(gè)基本結(jié)構(gòu)范圍之內(nèi)(如循環(huán)中流程的跳轉(zhuǎn))；一個(gè)非結(jié)構(gòu)化的算法可以用一個(gè)等價(jià)的結(jié)構(gòu)化算法代替，其功能不變。如果一個(gè)算法不能分解為若干個(gè)基本結(jié)構(gòu)，則它必然不是一個(gè)結(jié)構(gòu)化的算法。c)

偽代碼表示的算法用傳統(tǒng)的流程圖和N-S圖表示算法直觀易懂，但畫起來(lái)比較費(fèi)事，在設(shè)計(jì)一個(gè)算法時(shí)，可能要反復(fù)修改，而修改流程圖是比較麻煩的。因此，流程圖適宜于表示一個(gè)算法，但在設(shè)計(jì)算法過程中使用不是很理想的(尤其是當(dāng)算法比較復(fù)雜、需要反復(fù)修改時(shí))。為了設(shè)計(jì)算法時(shí)方便，常用一種稱為偽代碼的工具。偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。它如同一篇文章一樣，自上而下地寫下來(lái)。每一行(或幾行)表示一個(gè)基本操作。它不用圖形符號(hào)，因此書寫方便、格式緊湊，易懂也便于向計(jì)算機(jī)語(yǔ)言算法(即程序)過渡?？梢杂糜⑽?、漢字、中英文混合表示算法，以便于書寫和閱讀為原則。用偽代碼寫算法并無(wú)固定的、嚴(yán)格的語(yǔ)法規(guī)則，只要把意思表達(dá)清楚，并且書寫的格式要寫成清晰易讀的形式。例如，對(duì)于電子在特殊幾何構(gòu)型材