第2章-程序的靈魂——算法

1、2.1算法的概念算法的概念2.2簡單算法舉例簡單算法舉例2.3算法的特性算法的特性2.4怎樣表示一個算法怎樣表示一個算法2.5結(jié)構(gòu)化程序設(shè)計方法結(jié)構(gòu)化程序設(shè)計方法習題習題第第2 2章章 程序的靈魂程序的靈魂算法算法一個程序應包括以下兩方面內(nèi)容一個程序應包括以下兩方面內(nèi)容:(1) 對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)(data structure)。(2) 對操作的描述。即操作步驟，對操作的描述。即操作步驟， 也就是算法也就是算法(algorithm)。數(shù)據(jù)是操作的對象，操作的目的是對數(shù)據(jù)進行加工數(shù)據(jù)

2、是操作的對象，操作的目的是對數(shù)據(jù)進行加工處理，以得到期望的結(jié)果。作為程序設(shè)計人員，處理，以得到期望的結(jié)果。作為程序設(shè)計人員，必須認真考慮和設(shè)計數(shù)據(jù)結(jié)構(gòu)和操作步驟必須認真考慮和設(shè)計數(shù)據(jù)結(jié)構(gòu)和操作步驟(即算法即算法)。因此，著名計算機科學家沃思因此，著名計算機科學家沃思(Nikiklaus Wirth)提提出一個公式出一個公式數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 算法算法 = 程序程序?qū)嶋H上，一個程序除了以上兩個主要要素之外，還實際上，一個程序除了以上兩個主要要素之外，還應當采用結(jié)構(gòu)化程序設(shè)計方法進行程序設(shè)計，并應當采用結(jié)構(gòu)化程序設(shè)計方法進行程序設(shè)計，并且用某一種計算機語言表示。因此，可以這樣表且用某一種計算機語

3、言表示。因此，可以這樣表示：示：程序程序 = 算法算法 + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) + 程序設(shè)計方法程序設(shè)計方法 + 語言工具語言工具和環(huán)境和環(huán)境也就是說，以上也就是說，以上4個方面是一個程序設(shè)計人員所應具個方面是一個程序設(shè)計人員所應具備的知識。在設(shè)計一個程序時要綜合運用這幾方備的知識。在設(shè)計一個程序時要綜合運用這幾方面的知識。在這面的知識。在這4個方面中，算法是靈魂，數(shù)據(jù)結(jié)個方面中，算法是靈魂，數(shù)據(jù)結(jié)構(gòu)是加工對象，語言是工具，編程需要采用合適構(gòu)是加工對象，語言是工具，編程需要采用合適的方法。算法是解決的方法。算法是解決“做什么做什么”和和“怎么做怎么做”的的問題。程序中的操作語句，實際上就是算法的

4、體問題。程序中的操作語句，實際上就是算法的體現(xiàn)。顯然，不了解算法就談不上程序設(shè)計?，F(xiàn)。顯然，不了解算法就談不上程序設(shè)計。我們的目的是使讀者通過學習本書，能夠知道怎樣我們的目的是使讀者通過學習本書，能夠知道怎樣編寫一個編寫一個C程序，并且能夠編寫出不太復雜的程序，并且能夠編寫出不太復雜的C程程序。書中將通過一些實例把以上序。書中將通過一些實例把以上4個方面的知識結(jié)個方面的知識結(jié)合起來，介紹如何編寫一個合起來，介紹如何編寫一個C程序。程序。由于算法的重要性，在本章中先介紹有關(guān)算法的初由于算法的重要性，在本章中先介紹有關(guān)算法的初步知識，以便為后面各章的學習建立一定的基礎(chǔ)。步知識，以便為后面各章的學習

5、建立一定的基礎(chǔ)。2.1 算算 法法 的的 概概 念念從事各種工作和活動，都必須事先想好進行的步驟，從事各種工作和活動，都必須事先想好進行的步驟，然后按部就班地進行，才能避免產(chǎn)生錯亂。然后按部就班地進行，才能避免產(chǎn)生錯亂。不要認為只有不要認為只有“計算計算”的問題才有算法。廣義地說，的問題才有算法。廣義地說，為解決一個問題而采取的方法和步驟，就稱為為解決一個問題而采取的方法和步驟，就稱為“算法算法”。 對同一個問題，可以有不同的解題方法和步驟。方對同一個問題，可以有不同的解題方法和步驟。方法有優(yōu)劣之分。有的方法只需進行很少的步驟，法有優(yōu)劣之分。有的方法只需進行很少的步驟，而有些方法則需要較多的步

6、驟。一般說，希望采而有些方法則需要較多的步驟。一般說，希望采用簡單的和運算步驟少的方法。因此用簡單的和運算步驟少的方法。因此 ，為了有效，為了有效地進行解題，不僅需要保證算法正確，還要考慮地進行解題，不僅需要保證算法正確，還要考慮算法的質(zhì)量，選擇合適的算法。算法的質(zhì)量，選擇合適的算法。本書所關(guān)心的當然只限于計算機算法，即計算機能本書所關(guān)心的當然只限于計算機算法，即計算機能執(zhí)行的算法。執(zhí)行的算法。計算機算法可分為兩大類別：數(shù)值算法和非數(shù)值算計算機算法可分為兩大類別：數(shù)值算法和非數(shù)值算法。數(shù)值運算的目的是求數(shù)值解法。數(shù)值運算的目的是求數(shù)值解 。非數(shù)值運算包。非數(shù)值運算包括的面十分廣泛，最常見的是用

7、于事務管理領(lǐng)域。括的面十分廣泛，最常見的是用于事務管理領(lǐng)域。目前，計算機在非數(shù)值運算方面的應用遠遠超過目前，計算機在非數(shù)值運算方面的應用遠遠超過了在數(shù)值運算方面的應用。由于數(shù)值運算有現(xiàn)成了在數(shù)值運算方面的應用。由于數(shù)值運算有現(xiàn)成的模型，可以運用數(shù)值分析方法，因此對數(shù)值運的模型，可以運用數(shù)值分析方法，因此對數(shù)值運算的算法研究比較深入，算法比較成熟。對各種算的算法研究比較深入，算法比較成熟。對各種數(shù)值運算都有比較成熟的算法可供選用。人們常數(shù)值運算都有比較成熟的算法可供選用。人們常常把這些算法匯編成冊常把這些算法匯編成冊(寫成程序形式寫成程序形式)，或者將這，或者將這些程序存放在磁盤或磁帶上，供用戶

8、調(diào)用。些程序存放在磁盤或磁帶上，供用戶調(diào)用。而非數(shù)值運算的種類繁多，要求各異，難以規(guī)范化，而非數(shù)值運算的種類繁多，要求各異，難以規(guī)范化，因此只對一些典型的非數(shù)值運算算法因此只對一些典型的非數(shù)值運算算法(例如排序算例如排序算法法)作比較深入的研究。其他的非數(shù)值運算問題，作比較深入的研究。其他的非數(shù)值運算問題，往往需要使用者參考已有的類似算法重新設(shè)計解往往需要使用者參考已有的類似算法重新設(shè)計解決特定問題的專門算法。決特定問題的專門算法。本書不可能羅列所有算法，只是想通過一些典型算本書不可能羅列所有算法，只是想通過一些典型算法的介紹，幫助讀者了解如何設(shè)計一個算法，推法的介紹，幫助讀者了解如何設(shè)計一個

9、算法，推動讀者舉一反三。希望讀者通過本章介紹的例子動讀者舉一反三。希望讀者通過本章介紹的例子了解怎樣提出問題，怎樣思考問題，怎樣表示一了解怎樣提出問題，怎樣思考問題，怎樣表示一個算法。個算法。2.2 簡單算法舉例簡單算法舉例例例2.1 求求12345?？梢杂米钤嫉姆椒ㄟM行?？梢杂米钤嫉姆椒ㄟM行。步驟步驟1： 先求先求12，得到結(jié)果，得到結(jié)果2。步驟步驟2： 將步驟將步驟1得到的乘積得到的乘積2再乘以再乘以3，得到結(jié)果，得到結(jié)果6。步驟步驟3： 將將6再乘以再乘以4，得，得24。步驟步驟4： 將將24再乘以再乘以5，得，得120。這就是最后的結(jié)果。這就是最后的結(jié)果。這樣的算法雖然是正確的，但

10、太繁瑣。如果要求這樣的算法雖然是正確的，但太繁瑣。如果要求121000，則要寫，則要寫999個步驟，顯然是不可個步驟，顯然是不可取的。而且每次都直接使用上一步驟的數(shù)值結(jié)果取的。而且每次都直接使用上一步驟的數(shù)值結(jié)果(如如2，6，24等等)，也不方便。應當找到一種通用的，也不方便。應當找到一種通用的表示方法。表示方法?？梢栽O(shè)兩個變量，一個變量代表被乘數(shù)，一個變量可以設(shè)兩個變量，一個變量代表被乘數(shù)，一個變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。今設(shè)每一步驟的乘積放在被乘數(shù)變量中。今設(shè)p為被乘為被乘數(shù)，數(shù)，i為乘數(shù)。用循環(huán)算

11、法來求結(jié)果。可以將算法為乘數(shù)。用循環(huán)算法來求結(jié)果?？梢詫⑺惴ǜ膶懭缦拢焊膶懭缦拢篠1： 使使p=1S2： 使使i=2S3： 使使pi，乘積仍放在變量，乘積仍放在變量p中，可表示為中，可表示為pi=pS4： 使使i的值加的值加1，即，即i+1 = iS5： 如果如果i不大于不大于5，返回重新執(zhí)行步驟，返回重新執(zhí)行步驟S3以及其后以及其后的步驟的步驟S4和和S5；否則，算法結(jié)束。最后得到；否則，算法結(jié)束。最后得到p的值的值就是就是5!的值。的值。上面的上面的S1，S2代表步驟代表步驟1，步驟，步驟2S是是step(步步)的縮寫。這是寫算法的習慣用法。的縮寫。這是寫算法的習慣用法。請讀者仔細分析這個

12、算法，能否得到預期的結(jié)果。請讀者仔細分析這個算法，能否得到預期的結(jié)果。顯然這個算法比前面列出的算法簡練。顯然這個算法比前面列出的算法簡練。如果題目改為求如果題目改為求1357911。算法只需作很少的改動即可：算法只需作很少的改動即可： S1： 1=pS2： 3=iS3： pi=pS4： i+2=iS5： 若若i11，返回，返回S3； 否則，結(jié)束。否則，結(jié)束?？梢钥闯?，用這種方法表示的算法具有通用性、靈可以看出，用這種方法表示的算法具有通用性、靈活性。活性。S3到到S5組成一個循環(huán)，在實現(xiàn)算法時，要組成一個循環(huán)，在實現(xiàn)算法時，要反復多次執(zhí)行反復多次執(zhí)行S3、S4、S5等步驟，直到某一時刻，等步驟

13、，直到某一時刻，執(zhí)行執(zhí)行S5步驟時經(jīng)過判斷，乘數(shù)步驟時經(jīng)過判斷，乘數(shù)i已超過規(guī)定的數(shù)值已超過規(guī)定的數(shù)值而不返回而不返回S3步驟為止。此時算法結(jié)束，變量步驟為止。此時算法結(jié)束，變量p的值的值就是所求結(jié)果。就是所求結(jié)果。由于計算機是高速進行運算的自動機器，實現(xiàn)循環(huán)由于計算機是高速進行運算的自動機器，實現(xiàn)循環(huán)是輕而易舉的，所有計算機高級語言中都有實現(xiàn)是輕而易舉的，所有計算機高級語言中都有實現(xiàn)循環(huán)的語句。因此，上述算法不僅是正確的，而循環(huán)的語句。因此，上述算法不僅是正確的，而且是計算機能實現(xiàn)的較好的算法。且是計算機能實現(xiàn)的較好的算法。請讀者仔細分析循環(huán)結(jié)束的條件，即請讀者仔細分析循環(huán)結(jié)束的條件，即S5

14、步驟。如果步驟。如果在求在求1211時，將時，將S5步驟寫成步驟寫成S5： 若若i11，返回，返回S3。這樣會有什么問題這樣會有什么問題?會得到什么結(jié)果會得到什么結(jié)果?例例2.2 有有50個學生，要求將他們之中成績在個學生，要求將他們之中成績在80分以上分以上者打印出來。用者打印出來。用n表示學生學號，表示學生學號，n1代表第一個學代表第一個學生學號，生學號，ni代表第代表第i個學生學號。用個學生學號。用g代表學生成績，代表學生成績，gi代表第代表第i個學生成績，算法可表示如下。個學生成績，算法可表示如下。S1：1=iS2：如果：如果gi80，則打印，則打印ni和和gi，否則不打印，否則不打印

15、S3：i+1=iS4：如果：如果i50，返回，返回S2，繼續(xù)執(zhí)行；否則，算法結(jié)，繼續(xù)執(zhí)行；否則，算法結(jié)束。束。本例中，變量本例中，變量i作為下標，用它來控制序號作為下標，用它來控制序號(第幾個學第幾個學生，第幾個成績生，第幾個成績)。當。當i超過超過50時，表示已對時，表示已對50個學個學生的成績處理完畢，算法結(jié)束。生的成績處理完畢，算法結(jié)束。例例2.3 判定判定20002500年中的每一年是否閏年，將結(jié)年中的每一年是否閏年，將結(jié)果輸出。果輸出。閏年的條件是：閏年的條件是： 能被能被4整除，但不能被整除，但不能被100整除的整除的年份都是閏年，如年份都是閏年，如1996年，年，2004年是閏年

16、；能年是閏年；能被被100整除，又能被整除，又能被400整除的年份是閏年。如整除的年份是閏年。如1600年、年、2000年是閏年。不符合這兩個條件的年年是閏年。不符合這兩個條件的年份不是閏年。份不是閏年。算法可表示如下：算法可表示如下： 設(shè)設(shè)y 為被檢測的年份?？刹扇∫韵虏襟E：為被檢測的年份。可采取以下步驟： S1：2000=yS2： y不能被不能被4整除，則輸出整除，則輸出y “不是閏年不是閏年”。然后轉(zhuǎn)。然后轉(zhuǎn)到到S6S3：若：若y能被能被4整除，不能被整除，不能被100整除，則輸出整除，則輸出y “是是閏年閏年”。然后轉(zhuǎn)到。然后轉(zhuǎn)到S6S4：若：若y能被能被100整除，又能被整除，又能被

17、400整除，輸出整除，輸出y“是閏是閏年年”；否則輸出；否則輸出“不是閏年不是閏年”。 然后轉(zhuǎn)到然后轉(zhuǎn)到S6S5：輸出：輸出y “不是閏年不是閏年”S6：y+1=yS7：當：當y2500時，轉(zhuǎn)時，轉(zhuǎn)S2繼續(xù)執(zhí)行，如繼續(xù)執(zhí)行，如y2500，算法，算法停止。停止。在這個算法中，采取了多次判斷。先判斷在這個算法中，采取了多次判斷。先判斷y能否被能否被4整除，如不能，則整除，如不能，則y必然不是閏年。如必然不是閏年。如y 能被能被4整除，整除，并不能馬上決定它是否閏年，還要看它能否被并不能馬上決定它是否閏年，還要看它能否被100整除。如不能被整除。如不能被100整除，則肯定是閏年整除，則肯定是閏年(例

18、如例如1996年年)。如能被。如能被100整除，還不能判斷它是否閏年，還整除，還不能判斷它是否閏年，還要被要被400整除，如果能被整除，如果能被400整除，則它是閏年，整除，則它是閏年，否則不是閏年。否則不是閏年。在這個算法中，每做一步，都分別分離出一些范圍在這個算法中，每做一步，都分別分離出一些范圍(巳能判定為閏年或非閏年巳能判定為閏年或非閏年)，逐步縮小范圍，使被，逐步縮小范圍，使被判斷的范圍愈來愈小，直至執(zhí)行判斷的范圍愈來愈小，直至執(zhí)行S5時，只可能是時，只可能是非閏年。見圖非閏年。見圖2.1示意。示意。圖圖 2.1從圖從圖2.1可以看出：可以看出：“其他其他”這一部分，包括能被這一部分

19、，包括能被4整除，又能被整除，又能被100整除，而不能被整除，而不能被400整除的那些整除的那些年份年份(如如1900年年) ，是非閏年。，是非閏年。在考慮算法時，應當仔細分析所需判斷的條件，如在考慮算法時，應當仔細分析所需判斷的條件，如何一步一步縮小被判斷的范圍。有的問題，判斷何一步一步縮小被判斷的范圍。有的問題，判斷的先后次序是無所謂的，而有的問題，判斷條件的先后次序是無所謂的，而有的問題，判斷條件的先后次序是不能任意顛倒的，讀者可根據(jù)具體的先后次序是不能任意顛倒的，讀者可根據(jù)具體問題決定其邏輯。問題決定其邏輯。例例2.4 求求1-1/2+1/3-1/4+1/99-1/100。算法可以表示

20、如下：算法可以表示如下：S1：1=signS2：1=sumS3：2=denoS4：(-1)sign=signS5：sign(1/deno)=termS6：sum+term=sumS7：deno+1=denoS8：若：若deno100返回返回S4；否則算法結(jié)束。；否則算法結(jié)束。在步驟在步驟S1中先預設(shè)中先預設(shè)sign（代表級數(shù)中各項的符號，（代表級數(shù)中各項的符號，它的值為它的值為1或或-1）。在步驟）。在步驟S2中使中使sum等于等于1 ，相當，相當于已將級數(shù)中的第一項放到了于已將級數(shù)中的第一項放到了sum中。在步驟中。在步驟S3中中使分母的值為使分母的值為2。在步驟。在步驟S4中使中使sign

21、的值變?yōu)榈闹底優(yōu)?1。在步驟在步驟S5中求出級數(shù)中第中求出級數(shù)中第2項的值項的值-1/2。在步驟。在步驟S6中將剛才求出的第二項的值中將剛才求出的第二項的值-1/2累加到累加到sum中。至中。至此，此，sum的值是的值是1-1/2。在步驟。在步驟S7中使分母中使分母deno的的值加值加1（變成（變成3）。執(zhí)行）。執(zhí)行S8步驟，由于步驟，由于deno100，故返回故返回S4步驟，步驟，sign的值改為的值改為1，在，在S5中求出中求出term的值為的值為1/3，在，在S6中將中將1/3累加到累加到sum中。然后中。然后S7再再使分母變?yōu)槭狗帜缸優(yōu)?。按此規(guī)律反復執(zhí)行。按此規(guī)律反復執(zhí)行S4到到S8

22、步驟，直步驟，直到分母大于到分母大于100為止。一共執(zhí)行了為止。一共執(zhí)行了99次循環(huán)，向次循環(huán)，向sum累加入了累加入了99個分數(shù)。個分數(shù)。sum最后的值就是級數(shù)的最后的值就是級數(shù)的值。值。例例2.5 對一個大于或等于對一個大于或等于3的正整數(shù)，判斷它是不是的正整數(shù)，判斷它是不是一個素數(shù)。一個素數(shù)。所謂素數(shù)，是指除了所謂素數(shù)，是指除了1和該數(shù)本身之外，不能被其他和該數(shù)本身之外，不能被其他任何整數(shù)整除的數(shù)。例如，任何整數(shù)整除的數(shù)。例如，13是素數(shù)，因為它不是素數(shù)，因為它不能被能被2，3，4，12整除。整除。判斷一個數(shù)判斷一個數(shù)n(n3)是否素數(shù)的方法是很簡單的：將是否素數(shù)的方法是很簡單的：將n作

23、為被除數(shù)，將作為被除數(shù)，將2到到(n-1)各個整數(shù)輪流作為除數(shù)，各個整數(shù)輪流作為除數(shù)，如果都不能被整除，則如果都不能被整除，則n為素數(shù)。為素數(shù)。算法可以表示如下：算法可以表示如下：S1：輸入：輸入n的值的值S2：2=i （i作為除數(shù)）作為除數(shù)）S3：n被被i除，得余數(shù)除，得余數(shù)rS4：如果：如果r=0，表示，表示n能被能被i整除，則打印整除，則打印n“不是素不是素數(shù)數(shù)”，算法結(jié)束；否則執(zhí)行，算法結(jié)束；否則執(zhí)行S5S5：i+1=iS6：如果：如果in-1，返回，返回S3；否則打印；否則打印 n “是素數(shù)是素數(shù)”，然后結(jié)束。然后結(jié)束。實際上實際上n不必被不必被2到到(n-1)的整數(shù)除，只需被的整數(shù)

24、除，只需被2到到n的開的開方間整數(shù)除即可，甚至只需被方間整數(shù)除即可，甚至只需被2到到n之間的整數(shù)除之間的整數(shù)除即可。例如，判斷即可。例如，判斷13是否素數(shù)，只需將是否素數(shù)，只需將13被被2、3除即可，如都除不盡，除即可，如都除不盡，n 必為素數(shù)。必為素數(shù)。S6步驟可改為：步驟可改為：S6：如果：如果in，返回，返回S2；否則算法結(jié)束。；否則算法結(jié)束。通過以上幾個例子，可以初步了解怎樣設(shè)計一個算通過以上幾個例子，可以初步了解怎樣設(shè)計一個算法。法。2.3 算法的特性算法的特性一個算法應該具有以下特點：一個算法應該具有以下特點：1.有窮性有窮性一個算法應包含有限的操作步驟，而不能是無限的。一個算法應

25、包含有限的操作步驟，而不能是無限的。事實上，事實上，“有窮性有窮性”往往指往往指“在合理的范圍之內(nèi)在合理的范圍之內(nèi)”。究竟什么算究竟什么算“合理限度合理限度”，并無嚴格標準，由人，并無嚴格標準，由人們的常識和需要而定。們的常識和需要而定。2.確定性確定性算法中的每一個步驟都應當是確定的，而不應當是算法中的每一個步驟都應當是確定的，而不應當是含糊的、模棱兩可的。含糊的、模棱兩可的。3.有零個或多個輸入有零個或多個輸入所謂輸入是指在執(zhí)行算法時需要從外界取得必要的所謂輸入是指在執(zhí)行算法時需要從外界取得必要的信息。一個算法也可以沒有輸入。信息。一個算法也可以沒有輸入。4. 有一個或多個輸出有一個或多個

26、輸出算法的目的是為了求解，算法的目的是為了求解，“解解” 就是輸出。沒有輸就是輸出。沒有輸出的算法是沒有意義的。出的算法是沒有意義的。 5. 有效性有效性算法中的每一個步驟都應當能有效地執(zhí)行，并得到算法中的每一個步驟都應當能有效地執(zhí)行，并得到確定的結(jié)果。確定的結(jié)果。對于不熟悉計算機程序設(shè)計的人來說，他們可以只對于不熟悉計算機程序設(shè)計的人來說，他們可以只使用別人已設(shè)計好的現(xiàn)成算法，只需根據(jù)算法的使用別人已設(shè)計好的現(xiàn)成算法，只需根據(jù)算法的要求給以必要的輸入，就能得到輸出的結(jié)果。對要求給以必要的輸入，就能得到輸出的結(jié)果。對他們來說，算法如同一個他們來說，算法如同一個“黑箱子黑箱子”一樣一樣 ，他們，

27、他們可以不了解可以不了解“黑箱子黑箱子”中的結(jié)構(gòu)，只是從外部特中的結(jié)構(gòu)，只是從外部特性上了解算法的作用，即可方便地使用算法。例性上了解算法的作用，即可方便地使用算法。例如，對一個如，對一個“輸入輸入3個數(shù)，求其中最大值個數(shù)，求其中最大值”的算法，的算法，可以用圖可以用圖2.2表示，只要輸入表示，只要輸入a，b，c3個數(shù)，執(zhí)行個數(shù)，執(zhí)行算法后就能得到其中最大的數(shù)。但對于程序設(shè)計算法后就能得到其中最大的數(shù)。但對于程序設(shè)計人員來說，必須會設(shè)計算法，并且根據(jù)算法編寫人員來說，必須會設(shè)計算法，并且根據(jù)算法編寫程序。程序。圖圖2.22.4 怎樣表示一個算法怎樣表示一個算法為了表示一個算法，可以用不同的方法

28、。常用的有為了表示一個算法，可以用不同的方法。常用的有自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼、自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼、PAD圖等。圖等。2.4.1 用自然語言表示算法用自然語言表示算法在在2.2節(jié)中介紹的算法是用自然語言表示的。用自然節(jié)中介紹的算法是用自然語言表示的。用自然語言表示通俗易懂，但文字冗長，語言表示通俗易懂，但文字冗長， 容易出現(xiàn)容易出現(xiàn)“歧歧義性義性”。自然語言表示的含義往往不太嚴格，要。自然語言表示的含義往往不太嚴格，要根據(jù)上下文才能判斷其正確含義。此外，用自然根據(jù)上下文才能判斷其正確含義。此外，用自然語言描述包含分支和循環(huán)的算法，不很方便語言描述包含分

29、支和循環(huán)的算法，不很方便(如例如例2.5的算法的算法)。因此，除了很簡單的問題以外，一般。因此，除了很簡單的問題以外，一般不用自然語言描述算法。不用自然語言描述算法。2.4.2 用流程圖表示算法用流程圖表示算法流程圖是用一些圖框表示各種操作。用圖形表示算流程圖是用一些圖框表示各種操作。用圖形表示算法，直觀形象，易于理解。美國國家標準化協(xié)會法，直觀形象，易于理解。美國國家標準化協(xié)會ANSI(American National Standard Institute)規(guī)定規(guī)定了一些常用的流程圖符號了一些常用的流程圖符號(見圖見圖2.3)。 圖圖2.3中菱形框的作用是對一個給定的條件進行判斷，中菱形框

30、的作用是對一個給定的條件進行判斷，根據(jù)給定的條件是否成立來決定如何執(zhí)行其后的根據(jù)給定的條件是否成立來決定如何執(zhí)行其后的操作。它有一個入口，兩個出口。見圖操作。它有一個入口，兩個出口。見圖2.4。連接點連接點(小圓圈小圓圈)是用于將畫在不同地方的流程線連接是用于將畫在不同地方的流程線連接起來。如圖起來。如圖2.5中有兩個以為標志的連接點中有兩個以為標志的連接點(在連在連接點圈中寫上接點圈中寫上“1”)，它表示這兩個點是互相連接，它表示這兩個點是互相連接在一起的。實際上它們是同一個點，只是畫不下在一起的。實際上它們是同一個點，只是畫不下才分開來畫。用連接點，可以避免流程線的交叉才分開來畫。用連接點

31、，可以避免流程線的交叉或過長，使流程圖清晰?；蜻^長，使流程圖清晰。 圖圖 2.3圖圖 2.4 圖圖 2.5下面對下面對2.2節(jié)中所舉的幾個算法例子，改用流程圖表節(jié)中所舉的幾個算法例子，改用流程圖表示。示。例例2.6 將例將例2.1求求5!的算法用流程圖表示，流程圖見圖的算法用流程圖表示，流程圖見圖2.6。菱形框兩側(cè)的菱形框兩側(cè)的“Y”和和“N”代表代表“是是”(yes)和和“否否”(no)。如果需要將最后結(jié)果打印出來，可以。如果需要將最后結(jié)果打印出來，可以在菱形框的下面再加一個輸出框，見圖在菱形框的下面再加一個輸出框，見圖2.7。例例2.7 將例將例2.2的算法用流程圖表示。將的算法用流程圖表

32、示。將50名學生中名學生中成績在成績在80分以上者的學號和成績打印出來，見圖分以上者的學號和成績打印出來，見圖2.8。在此算法中沒有包括輸入。在此算法中沒有包括輸入50個學生數(shù)據(jù)的部個學生數(shù)據(jù)的部分，如果包括這個輸入數(shù)據(jù)的部分，流程圖如圖分，如果包括這個輸入數(shù)據(jù)的部分，流程圖如圖2.9所示。所示。 圖圖2.6 圖圖2.7 圖圖2.8例例2.8 將例將例2.3判定閏年的算法用流程圖表示。判定閏年的算法用流程圖表示。見圖見圖2.10。顯然，用圖。顯然，用圖2.10表示算法要比用文字描述表示算法要比用文字描述算法邏輯清晰、易于理解。算法邏輯清晰、易于理解。請讀者考慮，如果例請讀者考慮，如果例2.3所

33、表示的算法中，所表示的算法中，S2步驟內(nèi)步驟內(nèi)沒有最后沒有最后“轉(zhuǎn)到轉(zhuǎn)到S6”這一句話，而只是這一句話，而只是S2：若：若y不能被不能被4整除，則打印整除，則打印y “不是閏年不是閏年”這樣就意味著執(zhí)行完這樣就意味著執(zhí)行完S2步驟后，不論步驟后，不論S2的執(zhí)行情況的執(zhí)行情況如何都應執(zhí)行如何都應執(zhí)行S3步驟。請讀者畫出相應的流程圖。步驟。請讀者畫出相應的流程圖。請思考這樣的算法在邏輯上有什么錯誤，從流程請思考這樣的算法在邏輯上有什么錯誤，從流程圖上是很容易發(fā)現(xiàn)其錯誤的。圖上是很容易發(fā)現(xiàn)其錯誤的。圖圖2.9 圖圖2.10例例2.9 將例將例2.4的算法用流程圖表示。見圖的算法用流程圖表示。見圖2.

34、11。例例2.10 將例將例2.5判斷素數(shù)的算法用流程圖表示，見圖判斷素數(shù)的算法用流程圖表示，見圖2.12。一個流程圖包括以下幾部分：表示相應操作的框；一個流程圖包括以下幾部分：表示相應操作的框；帶箭頭的流程線；框內(nèi)外必要的文字說明。帶箭頭的流程線；框內(nèi)外必要的文字說明。需要提醒的是流程線不要忘記畫箭頭，因為它是需要提醒的是流程線不要忘記畫箭頭，因為它是反映流程的執(zhí)行先后次序的。反映流程的執(zhí)行先后次序的。用流程圖表示算法直觀形象，比較清楚地顯示出各用流程圖表示算法直觀形象，比較清楚地顯示出各個框之間的邏輯關(guān)系。但是這種流程圖占用篇幅個框之間的邏輯關(guān)系。但是這種流程圖占用篇幅較多，尤其當算法比較

35、復雜時，畫流程圖既費時較多，尤其當算法比較復雜時，畫流程圖既費時又不方便。在結(jié)構(gòu)化程序設(shè)計方法推廣之后，許又不方便。在結(jié)構(gòu)化程序設(shè)計方法推廣之后，許多書刊已用多書刊已用 N-S結(jié)構(gòu)化流程圖代替這種傳統(tǒng)的流程結(jié)構(gòu)化流程圖代替這種傳統(tǒng)的流程圖。但是每一個程序編制人員都應當熟練掌握傳圖。但是每一個程序編制人員都應當熟練掌握傳統(tǒng)流程圖。統(tǒng)流程圖。 圖圖2.11 圖圖2.122.4.3 三種基本結(jié)構(gòu)和改進的流程圖三種基本結(jié)構(gòu)和改進的流程圖1. 傳統(tǒng)流程圖的弊端傳統(tǒng)流程圖的弊端傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流傳統(tǒng)的流程圖用流程線指出各框的執(zhí)行順序，對流程線的使用沒有嚴格限制。因此，使用者可以不

36、程線的使用沒有嚴格限制。因此，使用者可以不受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使流程圖變得受限制地使流程隨意地轉(zhuǎn)來轉(zhuǎn)去，使流程圖變得毫無規(guī)律。這種情況如圖毫無規(guī)律。這種情況如圖2.13所示。所示。這種算法難以閱讀，也難以修改，從而使算法的可這種算法難以閱讀，也難以修改，從而使算法的可靠性和可維護性難以保證。如果我們寫出的算法靠性和可維護性難以保證。如果我們寫出的算法能限制流程的無規(guī)律任意轉(zhuǎn)向，閱讀起來就很方能限制流程的無規(guī)律任意轉(zhuǎn)向，閱讀起來就很方便。便。圖圖2.13但是，算法上難免會包含一些分支和循環(huán)，而不可但是，算法上難免會包含一些分支和循環(huán)，而不可能全部由一個一個框順序組成。例如圖能全部由一個

37、一個框順序組成。例如圖2.6到圖到圖2.12都不是由各框順序進行的，都包含一些流程的都不是由各框順序進行的，都包含一些流程的向前或向后的非順序轉(zhuǎn)向。為了解決這個問題，向前或向后的非順序轉(zhuǎn)向。為了解決這個問題，人們設(shè)想，規(guī)定出幾種基本結(jié)構(gòu)，然后由這些基人們設(shè)想，規(guī)定出幾種基本結(jié)構(gòu)，然后由這些基本結(jié)構(gòu)按一定規(guī)律組成一個算法結(jié)構(gòu)本結(jié)構(gòu)按一定規(guī)律組成一個算法結(jié)構(gòu)(如同用一些如同用一些基本預制構(gòu)件來搭成房屋一樣基本預制構(gòu)件來搭成房屋一樣)，整個算法的結(jié)構(gòu)，整個算法的結(jié)構(gòu)是由上而下地將各個基本結(jié)構(gòu)順序排列起來的。是由上而下地將各個基本結(jié)構(gòu)順序排列起來的。如果能做到這一點如果能做到這一點 ，算法的質(zhì)量就能得

38、到保證和，算法的質(zhì)量就能得到保證和提高。提高。2. 三種基本結(jié)構(gòu)三種基本結(jié)構(gòu)1966年，年，Bohra和和Jacopini提出了以下三種基本結(jié)構(gòu)，提出了以下三種基本結(jié)構(gòu)，作為表示一個良好算法的基本單元。作為表示一個良好算法的基本單元。(1) 順序結(jié)構(gòu)，如圖順序結(jié)構(gòu)，如圖2.14所示，虛線框內(nèi)是一個順序所示，虛線框內(nèi)是一個順序結(jié)構(gòu)。結(jié)構(gòu)。(2) 選擇結(jié)構(gòu)，或稱選取結(jié)構(gòu)，或稱分支結(jié)構(gòu)，如圖選擇結(jié)構(gòu)，或稱選取結(jié)構(gòu)，或稱分支結(jié)構(gòu)，如圖2.15所示。所示。請注意，無論請注意，無論 p 條件是否成立，只能執(zhí)行條件是否成立，只能執(zhí)行A框或框或B框框之一，不可能既執(zhí)行之一，不可能既執(zhí)行A框又執(zhí)行框又執(zhí)行B框。

39、無論走哪一框。無論走哪一條路徑，在執(zhí)行完條路徑，在執(zhí)行完A或或B之后，都經(jīng)過之后，都經(jīng)過b點，然后點，然后脫離本選擇結(jié)構(gòu)。脫離本選擇結(jié)構(gòu)。A或或B兩個框中可以有一個是空兩個框中可以有一個是空的的 ，即不執(zhí)行任何操作，如圖，即不執(zhí)行任何操作，如圖2.16所示。所示。圖圖2.14 圖圖2.15 圖圖2.16(3) 循環(huán)結(jié)構(gòu)，它又稱重復結(jié)構(gòu)。有兩類循環(huán)結(jié)構(gòu)：循環(huán)結(jié)構(gòu)，它又稱重復結(jié)構(gòu)。有兩類循環(huán)結(jié)構(gòu)： 當型當型(While型型)循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu)見圖見圖2.17(a)。它的功能是當給定的條件。它的功能是當給定的條件p1成立時，成立時，執(zhí)行執(zhí)行A框操作，執(zhí)行完框操作，執(zhí)行完A后，再判斷條件后，再判斷條件p

40、1是否成是否成立，如果仍然成立，再執(zhí)行立，如果仍然成立，再執(zhí)行A框，如此反復執(zhí)行框，如此反復執(zhí)行A框，直到某一次框，直到某一次p1條件不成立為止，此時不執(zhí)行條件不成立為止，此時不執(zhí)行A框，而從框，而從b點脫離循環(huán)結(jié)構(gòu)。點脫離循環(huán)結(jié)構(gòu)。 直到型直到型(Until型型)循環(huán)循環(huán)見圖見圖2.17(b)。它的功能是先執(zhí)行。它的功能是先執(zhí)行A框，然后判斷給定框，然后判斷給定的的p2條件是否成立，如果條件是否成立，如果p2條件不成立，則再執(zhí)條件不成立，則再執(zhí)行行A，然后再對，然后再對p2條件作判斷，如果條件作判斷，如果p2條件仍然不條件仍然不成立，又執(zhí)行成立，又執(zhí)行A如此反復執(zhí)行如此反復執(zhí)行A，直到給定的

41、，直到給定的p2條件成立為止，此時不再執(zhí)行條件成立為止，此時不再執(zhí)行A，從，從b點脫離本點脫離本循環(huán)結(jié)構(gòu)。循環(huán)結(jié)構(gòu)。圖圖2.18是當型循環(huán)的應用例子，圖是當型循環(huán)的應用例子，圖2.19是直到型循環(huán)是直到型循環(huán)的應用例子。的應用例子。圖圖2.17 圖圖2.18 圖圖2.19圖圖2.18和圖和圖2.19的作用都是打印的作用都是打印5個數(shù)：個數(shù)：1，2，3，4，5?？梢钥吹?，?？梢钥吹剑?對同一個問題既可以用當型循環(huán)來對同一個問題既可以用當型循環(huán)來處理，也可以用直到型循環(huán)來處理。處理，也可以用直到型循環(huán)來處理。以上三種基本結(jié)構(gòu)，有以下共同特點：以上三種基本結(jié)構(gòu)，有以下共同特點：(1) 只有一個入口。

42、只有一個入口。(2) 只有一個出口。請注意，一個菱形判斷框有兩個只有一個出口。請注意，一個菱形判斷框有兩個出口，而一個選擇結(jié)構(gòu)只有一個出口。不要將菱出口，而一個選擇結(jié)構(gòu)只有一個出口。不要將菱形框的出口和選擇結(jié)構(gòu)的出口混淆。形框的出口和選擇結(jié)構(gòu)的出口混淆。(3) 結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到。對每一個結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到。對每一個框來說，都應有一條從入口到出口的路徑通過它。框來說，都應有一條從入口到出口的路徑通過它。圖圖2.20中沒有一條從入口到出口的路徑通過中沒有一條從入口到出口的路徑通過A框?？颉?4) 結(jié)構(gòu)內(nèi)不存在結(jié)構(gòu)內(nèi)不存在“死循環(huán)死循環(huán)”(無終止的循環(huán)無終止的循環(huán))。圖

43、。圖2.21就是一個死循環(huán)。就是一個死循環(huán)。圖圖2.20 圖圖2.21已經(jīng)證明，由以上三種基本結(jié)構(gòu)順序組成的算法結(jié)已經(jīng)證明，由以上三種基本結(jié)構(gòu)順序組成的算法結(jié)構(gòu)，可以解決任何復雜的問題。由基本結(jié)構(gòu)所構(gòu)構(gòu)，可以解決任何復雜的問題。由基本結(jié)構(gòu)所構(gòu)成的算法屬于成的算法屬于“結(jié)構(gòu)化結(jié)構(gòu)化”的算法，它不存在無規(guī)的算法，它不存在無規(guī)律的轉(zhuǎn)向，只在本基本結(jié)構(gòu)內(nèi)才允許存在分支和律的轉(zhuǎn)向，只在本基本結(jié)構(gòu)內(nèi)才允許存在分支和向前或向后的跳轉(zhuǎn)。向前或向后的跳轉(zhuǎn)。其實，基本結(jié)構(gòu)不一定只限于上面三種，只要具有其實，基本結(jié)構(gòu)不一定只限于上面三種，只要具有上述上述4個特點的都可以作為基本結(jié)構(gòu)。人們可以自個特點的都可以作為基本

44、結(jié)構(gòu)。人們可以自己定義基本結(jié)構(gòu)，并由這些基本結(jié)構(gòu)組成結(jié)構(gòu)化己定義基本結(jié)構(gòu)，并由這些基本結(jié)構(gòu)組成結(jié)構(gòu)化程序。例如，可以將圖程序。例如，可以將圖2.22和圖和圖2.23這樣的結(jié)構(gòu)定這樣的結(jié)構(gòu)定義為基本結(jié)構(gòu)。圖義為基本結(jié)構(gòu)。圖2.23所示的是一個多分支選擇結(jié)所示的是一個多分支選擇結(jié)構(gòu)，根據(jù)給定的表達式的值決定執(zhí)行哪一個框。構(gòu)，根據(jù)給定的表達式的值決定執(zhí)行哪一個框。圖圖2.22和圖和圖2.23虛線框內(nèi)的結(jié)構(gòu)也是一個入口和一虛線框內(nèi)的結(jié)構(gòu)也是一個入口和一個出口，并且有上述全部的個出口，并且有上述全部的4個特點。由它們構(gòu)成個特點。由它們構(gòu)成的算法結(jié)構(gòu)也是結(jié)構(gòu)化的算法。但是，可以認為的算法結(jié)構(gòu)也是結(jié)構(gòu)化的算

45、法。但是，可以認為像圖像圖2.22和圖和圖2.23那樣的結(jié)構(gòu)是由三種基本結(jié)構(gòu)派那樣的結(jié)構(gòu)是由三種基本結(jié)構(gòu)派生出來的。因此，人們都普遍認為最基本的是本生出來的。因此，人們都普遍認為最基本的是本節(jié)介紹的三種基本結(jié)構(gòu)。節(jié)介紹的三種基本結(jié)構(gòu)。圖圖2.22 圖圖2.232.4.4 用用N-S流程圖表示算法流程圖表示算法既然用基本結(jié)構(gòu)的順序組合可以表示任何復雜的算既然用基本結(jié)構(gòu)的順序組合可以表示任何復雜的算法結(jié)構(gòu)，那么基本結(jié)構(gòu)之間的流程線就屬多余的法結(jié)構(gòu)，那么基本結(jié)構(gòu)之間的流程線就屬多余的了。了。1973年美國學者年美國學者I.Nassi和和B.Shneiderman提出了一種提出了一種新的流程圖形式。在

46、這種流程圖中，完全去掉了新的流程圖形式。在這種流程圖中，完全去掉了帶箭頭的流程線。全部算法寫在一個矩形框內(nèi)，帶箭頭的流程線。全部算法寫在一個矩形框內(nèi)，在該框內(nèi)還可以包含其他的從屬于它的框，或者在該框內(nèi)還可以包含其他的從屬于它的框，或者說，由一些基本的框組成一個大的框。這種流程說，由一些基本的框組成一個大的框。這種流程圖又稱圖又稱N-S結(jié)構(gòu)化流程圖。這種流程圖適于結(jié)構(gòu)化結(jié)構(gòu)化流程圖。這種流程圖適于結(jié)構(gòu)化程序設(shè)計，因而很受歡迎。程序設(shè)計，因而很受歡迎。N-S流程圖用以下的流程圖符號：流程圖用以下的流程圖符號：(1) 順序結(jié)構(gòu)順序結(jié)構(gòu): 用圖用圖2.24形式表示。形式表示。A和和B兩個框組成兩個框組

47、成一個順序結(jié)構(gòu)。一個順序結(jié)構(gòu)。(2) 選擇結(jié)構(gòu)：用圖選擇結(jié)構(gòu)：用圖2.25表示。它與圖表示。它與圖2.15相應。當相應。當p條件成立時執(zhí)行條件成立時執(zhí)行A操作，操作，p不成立則執(zhí)行不成立則執(zhí)行B操作。操作。請注意圖請注意圖2.25是一個整體，代表一個基本結(jié)構(gòu)。是一個整體，代表一個基本結(jié)構(gòu)。圖圖2.24 圖圖2.25(3) 循環(huán)結(jié)構(gòu)：循環(huán)結(jié)構(gòu)： 當型循環(huán)結(jié)構(gòu)用圖當型循環(huán)結(jié)構(gòu)用圖2.26形式表示。形式表示。圖圖2.26表示當表示當p1條件成立時反復執(zhí)行條件成立時反復執(zhí)行A操作，直到操作，直到p1條件不成立為止。條件不成立為止。直到型循環(huán)結(jié)構(gòu)用圖直到型循環(huán)結(jié)構(gòu)用圖2.27形式表示。形式表示。用以上用

48、以上3種種N-S流程圖中的基本框，可以組成復雜的流程圖中的基本框，可以組成復雜的N-S流程圖，以表示算法。流程圖，以表示算法。應當說明，在圖應當說明，在圖2.24、圖、圖2.25、圖、圖2.26、圖、圖2.27中的中的A框或框或B框，可以是一個簡單的操作框，可以是一個簡單的操作(如讀入數(shù)據(jù)或如讀入數(shù)據(jù)或打印輸出等打印輸出等)，也可以是，也可以是3個基本結(jié)構(gòu)之一。例如，個基本結(jié)構(gòu)之一。例如，圖圖2.24所示的順序結(jié)構(gòu)，其中的所示的順序結(jié)構(gòu)，其中的A框可以又是一個框可以又是一個選擇結(jié)構(gòu)，選擇結(jié)構(gòu)，B框可以又是一個循環(huán)結(jié)構(gòu)。如圖框可以又是一個循環(huán)結(jié)構(gòu)。如圖2.28所示那樣，由所示那樣，由A和和B這兩

49、個基本結(jié)構(gòu)組成一個順序這兩個基本結(jié)構(gòu)組成一個順序結(jié)構(gòu)。結(jié)構(gòu)。圖圖2.26 圖圖2.27 圖圖2.28通過下面的幾個例子，讀者可以了解如何用通過下面的幾個例子，讀者可以了解如何用N-S流程流程圖表示算法。圖表示算法。例例2.11 將例將例2.1的求的求5!算法用算法用N-S圖表示。見圖圖表示。見圖2.29，它和圖它和圖2.7對應。對應。例例2.12 將例將例2.2的算法用的算法用N-S圖表示。將圖表示。將50名名 學生中學生中成績高于成績高于80分的學號和成績打印出來。見圖分的學號和成績打印出來。見圖2.30和和圖圖2.31，它們與圖，它們與圖2.8和圖和圖2.9對應。對應。例例2.13 將例將

50、例2.3判定閏年的算法用判定閏年的算法用N-S圖表示。見圖圖表示。見圖2.32，它和圖，它和圖2.10對應。對應。例例2.14 將例將例2.4的算法用的算法用N-S圖表示。見圖圖表示。見圖2.33，它和，它和圖圖2.11對應，只是最后加了一個對應，只是最后加了一個“打印打印sum”框?？颉＠?.15 將例將例2.5判別素數(shù)的算法用判別素數(shù)的算法用N-S流程圖表示。流程圖表示。圖圖2.29 圖圖2.30 圖圖2.31圖圖2.32 圖圖2.33由圖由圖2.12可以看出，這個流程圖不是由三種基本結(jié)可以看出，這個流程圖不是由三種基本結(jié)構(gòu)組成的。圖中間那個循環(huán)部分，有兩個出口構(gòu)組成的。圖中間那個循環(huán)部

51、分，有兩個出口(一一個從第二個菱形框下面出口，另一個在第一個菱個從第二個菱形框下面出口，另一個在第一個菱形框右邊出口形框右邊出口)，不符合基本結(jié)構(gòu)的特點。由于不，不符合基本結(jié)構(gòu)的特點。由于不能分解為三種基本結(jié)構(gòu)，就無法直接用能分解為三種基本結(jié)構(gòu)，就無法直接用N-S流程圖流程圖的三種基本結(jié)構(gòu)的符號來表示。因此，應當先對的三種基本結(jié)構(gòu)的符號來表示。因此，應當先對圖圖2.12做必要的變換。要將第一個菱形框做必要的變換。要將第一個菱形框(“r=0”)的的兩個出口匯合在一點，以解決兩個出口問題。當兩個出口匯合在一點，以解決兩個出口問題。當r=0時不直接輸出時不直接輸出n“不是素數(shù)不是素數(shù)”，而只設(shè)一個標

52、志，而只設(shè)一個標志值（變量值（變量w），它的初始狀態(tài)為），它的初始狀態(tài)為w=0。當。當r=0時時(表表示示n為非素數(shù)為非素數(shù))使使w變成變成1。如果。如果r 0則保持則保持w=0。w的作用如同一個開關(guān)，有兩個工作狀況：的作用如同一個開關(guān)，有兩個工作狀況：w=0和和w=1。w=1表示表示n為非素數(shù)。為非素數(shù)。如果最終如果最終w=0，則表示，則表示n為素數(shù)。然后將為素數(shù)。然后將“1=w”框框的出口線改為指向第二個菱形框，同時將第二個的出口線改為指向第二個菱形框，同時將第二個菱形框中的條件改為菱形框中的條件改為 “in和和w=0”，即只有當，即只有當“in”和和“w=0”兩個條件都滿足時才繼續(xù)執(zhí)行循

53、兩個條件都滿足時才繼續(xù)執(zhí)行循環(huán)。如果出現(xiàn)環(huán)。如果出現(xiàn)in或或w0之一，都不會繼續(xù)執(zhí)行循之一，都不會繼續(xù)執(zhí)行循環(huán)環(huán)(見圖見圖2.34)。如果在某一次。如果在某一次r=0，則應執(zhí)行，則應執(zhí)行1=w，然后，由第二個菱形框判斷為然后，由第二個菱形框判斷為“條件不成立條件不成立”，接著執(zhí)行圖下部的選擇結(jié)構(gòu)。此時，接著執(zhí)行圖下部的選擇結(jié)構(gòu)。此時，w0，表示，表示n不是素數(shù)，應打印出不是素數(shù)，應打印出n不是素數(shù)的信息。如果不是素數(shù)的信息。如果w=0，則表示在上面的每次循環(huán)中，則表示在上面的每次循環(huán)中，n都不能被每一個都不能被每一個i整整除，所以除，所以n是素數(shù)，故輸出是素數(shù)，故輸出n是素數(shù)的信息。是素數(shù)的信

54、息。圖圖2.34已由三種基本結(jié)構(gòu)組成，可以用已由三種基本結(jié)構(gòu)組成，可以用N-S圖表示此圖表示此算法，見圖算法，見圖2.35。注意圖。注意圖2.34直到型循環(huán)的判斷條直到型循環(huán)的判斷條件為：件為： “直到直到in或或w0”，即只要，即只要“in或或w0”之一成立，就不再繼續(xù)執(zhí)行循環(huán)。對此務請讀者之一成立，就不再繼續(xù)執(zhí)行循環(huán)。對此務請讀者弄清楚。弄清楚。通過以上例子，可以看出用通過以上例子，可以看出用N-S圖表示算法的優(yōu)點。圖表示算法的優(yōu)點。它比文字描述直觀、形象、它比文字描述直觀、形象、 易于理解；比傳統(tǒng)流易于理解；比傳統(tǒng)流程圖緊湊易畫，尤其是它廢除了流程線，整個算程圖緊湊易畫，尤其是它廢除了流

55、程線，整個算法結(jié)構(gòu)是由各個基本結(jié)構(gòu)按順序組成的。法結(jié)構(gòu)是由各個基本結(jié)構(gòu)按順序組成的。N-S流程流程圖中的上下順序就是執(zhí)行時的順序，即圖中位置圖中的上下順序就是執(zhí)行時的順序，即圖中位置在上面的先執(zhí)行，位置在下面的后執(zhí)行。寫算法在上面的先執(zhí)行，位置在下面的后執(zhí)行。寫算法和看算法只需從上到下進行就可以了，十分方便。和看算法只需從上到下進行就可以了，十分方便。用用N-S圖表示的算法都是結(jié)構(gòu)化的算法圖表示的算法都是結(jié)構(gòu)化的算法(它不可能它不可能出現(xiàn)流程無規(guī)律的跳轉(zhuǎn)，而只能自上而下地順序出現(xiàn)流程無規(guī)律的跳轉(zhuǎn)，而只能自上而下地順序執(zhí)行執(zhí)行)。 圖圖2.34 圖圖2.35歸納起來可知，一個結(jié)構(gòu)化的算法是由一些

56、基本結(jié)歸納起來可知，一個結(jié)構(gòu)化的算法是由一些基本結(jié)構(gòu)順序組成的；每個基本結(jié)構(gòu)又可以包含其他的構(gòu)順序組成的；每個基本結(jié)構(gòu)又可以包含其他的基本結(jié)構(gòu)；在基本結(jié)構(gòu)之間不存在向前或向后的基本結(jié)構(gòu)；在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個基本結(jié)構(gòu)范圍之跳轉(zhuǎn)，流程的轉(zhuǎn)移只存在于一個基本結(jié)構(gòu)范圍之內(nèi)內(nèi)(如循環(huán)中流程的跳轉(zhuǎn)如循環(huán)中流程的跳轉(zhuǎn))；一；一 個非結(jié)構(gòu)化的算法個非結(jié)構(gòu)化的算法(如圖如圖2.12)可以用一個等價的結(jié)構(gòu)化算法可以用一個等價的結(jié)構(gòu)化算法(如圖如圖2.35)代替，其功能不變。如果一個算法不能分解為若代替，其功能不變。如果一個算法不能分解為若干個基本結(jié)構(gòu)，則它必然不是一個結(jié)構(gòu)化

57、的算法。干個基本結(jié)構(gòu)，則它必然不是一個結(jié)構(gòu)化的算法。N-S圖如同一個多層的盒子，又稱盒圖圖如同一個多層的盒子，又稱盒圖(box diagram)。2.4.5 用偽代碼表示算法用偽代碼表示算法用傳統(tǒng)的流程圖和用傳統(tǒng)的流程圖和N-S圖表示算法，直觀易懂，但畫圖表示算法，直觀易懂，但畫起來比較費事。因此，流程圖適宜表示一起來比較費事。因此，流程圖適宜表示一 個算法，個算法，但在設(shè)計算法過程中使用不是很理想。為了設(shè)計但在設(shè)計算法過程中使用不是很理想。為了設(shè)計算法時方便，常用一種稱為偽代碼算法時方便，常用一種稱為偽代碼(pseudo code)的的工具。工具。偽代碼是用介于自然語言和計算機語言之間的文字

58、偽代碼是用介于自然語言和計算機語言之間的文字和符號來描述算法。它如同一篇文章，自上而下和符號來描述算法。它如同一篇文章，自上而下地寫下來。每一行地寫下來。每一行(或幾行或幾行)表示一個基本操作。它表示一個基本操作。它不用圖形符號，因此書寫方便不用圖形符號，因此書寫方便 、格式緊湊，也比、格式緊湊，也比較好懂，便于向計算機語言算法較好懂，便于向計算機語言算法(即程序即程序)過渡。過渡。例如，例如， “打印打印x的絕對值的絕對值”的算法可以用偽代碼表的算法可以用偽代碼表示如下：示如下：IF x is positive THENprint xELSEprint x它像一個英語句子一樣好懂，在國外用得

59、比較普遍。它像一個英語句子一樣好懂，在國外用得比較普遍。也可以用漢字偽代碼，如：也可以用漢字偽代碼，如：若若 x為正為正打印打印 x否則否則打印打印 x也可以中英文混用，如：也可以中英文混用，如：IF x 為正為正print xELSEprint x即計算機語言中具有的語句關(guān)鍵字用英文表示，其即計算機語言中具有的語句關(guān)鍵字用英文表示，其他的可用漢字表示?？傊?，以便于書寫和閱讀為他的可用漢字表示?？傊?，以便于書寫和閱讀為原則。用偽代碼寫算法并無固定的、嚴格的語法原則。用偽代碼寫算法并無固定的、嚴格的語法規(guī)則，只要把意思表達清楚，并且書寫的格式要規(guī)則，只要把意思表達清楚，并且書寫的格式要寫成清晰易

60、讀的形式。寫成清晰易讀的形式。將例將例2.1到例到例2.5的算法用偽代碼表示如下。的算法用偽代碼表示如下。例例2.16 求求5!。用偽代碼表示的算法如下：。用偽代碼表示的算法如下： 開始開始置置t的初值為的初值為1置置i的初值為的初值為2當當it2=iwhile iti+1=iprint tEND(算法結(jié)束算法結(jié)束)在本算法中采用當型循環(huán)（第在本算法中采用當型循環(huán)（第3行到笫行到笫5行是一個當行是一個當型循環(huán)）。型循環(huán)）。while意思為意思為“當當”， 它表示當它表示當iiwhile ii1=iwhile iiEND(算法結(jié)束算法結(jié)束)例例2.18 打印打印20002500年中的每一年是否閏