C程序設計第2章

第2章程序的靈魂——算法2.1算法的概念2.2簡單算法舉例2.3算法的特性2.4怎樣表示一個算法2.5結(jié)構(gòu)化程序設計方法一個程序應包括以下兩方面內(nèi)容:（1）對數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)(datastructure)。（2）對操作的描述。即操作步驟，也就是算法(algorithm)。數(shù)據(jù)是操作的對象，操作的目的是對數(shù)據(jù)進行加工處理，以得到期望的結(jié)果。著名計算機科學家沃思(NikiklausWirth)提出一個公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序?qū)嶋H上，一個程序除了以上兩個主要要素之外，還應當采用結(jié)構(gòu)化程序設計方法進行程序設計，并且用某一種計算機語言表示。因此，可以這樣表示：

在這4個方面中，算法是靈魂，數(shù)據(jù)結(jié)構(gòu)是加工對象，語言是工具，編程需要采用合適的方法。算法是解決“做什么”和“怎么做”的問題。程序中的操作語句，實際上就是算法的體現(xiàn)。程序

=算法

+數(shù)據(jù)結(jié)構(gòu)

+程序設計方法

+語言工具和環(huán)境2.1

算法的概念從事各種工作和活動，都必須事先想好進行的步驟，然后按部就班地進行，才能避免產(chǎn)生錯亂。不要認為只有“計算”的問題才有算法。廣義地說，為解決一個問題而采取的方法和步驟，就稱為“算法”。對于同一個問題，可以有不同的解決方法和步驟例如求1+2+3+……+100的問題有人是：1+2，再+3，再+4，……+100

有人是：100+（1+99）+（2+98）

+…+(49+51)+50=100+49*100+50=5050

還有其他方法方法有優(yōu)劣之分，希望采用的方法簡單、運算步驟少的方法，我們所關心的只是計算機算法。計算機算法可分為兩大類別：數(shù)值算法和非數(shù)值算法。數(shù)值運算的目的是求數(shù)值解，此種算法比較成熟（庫函數(shù)）。非數(shù)值運算包括的面十分廣泛，最常見的是用于事務管理領域，此種算法種類繁多。2.2簡單算法舉例【例2.1】求1×2×3×4×5。可以用最原始的方法進行。步驟1：先求1×2，得到結(jié)果2。步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。這就是最后的結(jié)果。這樣的算法雖然是正確的，但太繁瑣。若求1*2*……*1000怎么辦？可以設兩個變量，一個變量代表被乘數(shù)，一個變量代表乘數(shù)。不另設變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。今設p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結(jié)果。可以將算法改寫如下：

S1：使p=1S2：使i=2S3：使p×i，乘積仍放在變量p中，可表示為p×i=>pS4：使i的值加1，即i+1=>iS5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結(jié)束。最后得到p的值就是5!的值。如果題目改為求1×3×5×7×9×11。算法只需作很少的改動即可：

S1：1=>pS2：3=>iS3：p×i=>pS4：i+2=>iS5：若i≤11，返回S3；否則，結(jié)束?？梢钥闯?，用這種方法表示的算法具有通用性、靈活性。【例2.2】有50個學生，要求將他們之中成績在80分以上的學號和成績輸出。用n表示學生學號，n1代表第一個學生學號，ni代表第i個學生學號。用g代表學生成績，gi代表第i個學生成績，算法可表示如下。

S1：1=>iS2：如果gi≥80，則輸出ni和gi，否則不輸出

S3：i+1=>iS4：如果i≤50，返回S2，繼續(xù)執(zhí)行；否則，算法結(jié)束。本例中，變量i作為下標，用它來控制序號(第幾個學生，第幾個成績)。當i超過50時，表示已對50個學生的成績處理完畢，算法結(jié)束?！纠?.3】判定2000—2500年中的每一年是否閏年，將結(jié)果輸出。閏年的條件是：①能被4整除，但不能被100整除的年份都是閏年，如1996年，2004年是閏年；②能被100整除，又能被400整除的年份是閏年。如1600年、2000年是閏年。不符合這兩個條件的年份不是閏年。算法可表示如下：設y為被檢測的年份。可采取以下步驟：

S1：2000=>yS2：y不能被4整除，則輸出y“不是閏年”。然后轉(zhuǎn)到S6

S3：若y能被4整除，不能被100整除，則輸出y“是閏年”。然后轉(zhuǎn)到S6S4：若y能被100整除，又能被400整除，輸出y“是閏年”；否則輸出“不是閏年”。然后轉(zhuǎn)到S6S5：輸出y“不是閏年”

S6：y+1=>yS7：當y≤2500時，轉(zhuǎn)S2繼續(xù)執(zhí)行，如y＞2500，算法停止。在例2.3的算法中，采取了多次判斷，每做一步，都分別分離出一些范圍(已能判定為閏年或非閏年)，逐步縮小范圍，使被判斷的范圍愈來愈小，直至執(zhí)行S5時，只可能是非閏年。見圖2.1示意。圖2.1【例2.4】求1-1/2+1/3-1/4+…+1/99-1/100。算法可以表示如下：

S1：1=>signS2：1=>sumS3：2=>denoS4：(-1)×sign=>signS5：sign×(1/deno)=>termS6：sum+term=>sumS7：deno+1=>denoS8：若deno≤100返回S4；否則算法結(jié)束。在步驟S1中先預設sign（代表多項式中各項的符號，它的值為1或-1）。在步驟S2中使sum等于1，相當于已將多項式中的第一項放到了sum中。在步驟S3中使分母的值為2。在步驟S4中使sign的值變?yōu)?1。在步驟S5中求出多項式中第2項的值-1/2。在步驟S6中將剛才求出的第二項的值-1/2累加到sum中。至此，sum的值是1-1/2。在步驟S7中使分母deno的值加1（變成3）。執(zhí)行S8步驟，由于deno≤100，故返回S4步驟，sign的值改為1，在S5中求出term的值為1/3，在S6中將1/3累加到sum中。然后S7再使分母變?yōu)?。按此規(guī)律反復執(zhí)行S4到S8步驟，直到分母大于100為止。一共執(zhí)行了99次循環(huán)，向sum累加入了99個分數(shù)。sum最后的值就是多項式的值。【例2.5】對一個大于或等于3的正整數(shù)，判斷它是不是一個素數(shù)。判斷一個數(shù)n(n≥3)是否素數(shù)的方法是很簡單的：將n作為被除數(shù)，將2到(n-1)各個整數(shù)輪流作為除數(shù)，如果都不能被整除，則n為素數(shù)。算法可以表示如下：

S1：輸入n的值

S2：2=>i（i作為除數(shù)）

S3：n被i除，得余數(shù)rS4：如果r=0，表示n能被i整除，則打印n“不是素數(shù)”，算法結(jié)束；否則執(zhí)行S5S5：i+1=>iS6：如果i≤n-1，返回S3；否則打印n“是素數(shù)”，然后結(jié)束?？芍怀絥/22.3算法的特性一個算法應該具有以下特點：有窮性一個算法應包含有限的操作步驟，而不能是無限的。確定性算法中的每一個步驟都應當是確定的，而不應當是含糊的、模棱兩可的。有零個或多個輸入所謂輸入是指在執(zhí)行算法時需要從外界取得必要的信息。一個算法也可以沒有輸入。有一個或多個輸出算法的目的是為了求解，“解”就是輸出。沒有輸出的算法是沒有意義的。有效性算法中的每一個步驟都應當能有效地執(zhí)行，并得到確定的結(jié)果。不能b=0時，求a/b等2.4怎樣表示一個算法常用方法：自然語言、傳統(tǒng)流程圖、結(jié)構(gòu)化流程圖、偽代碼、PAD圖等2.4.1

用自然語言表示算法在2.2節(jié)中介紹的算法是用自然語言表示的。用自然語言表示通俗易懂，但文字冗長，容易出現(xiàn)“歧義性”。自然語言表示的含義往往不太嚴格，要根據(jù)上下文才能判斷其正確含義。此外，用自然語言描述包含分支和循環(huán)的算法，不很方便(如例2.5的算法)。因此，除了很簡單的問題以外，一般不用自然語言描述算法。2.4.2用流程圖表示算法流程圖是用一些圖框表示各種操作，已通用。用圖形表示算法，直觀形象，易于理解。美國國家標準化協(xié)會ANSI(AmericanNationalStandardInstitute)規(guī)定了一些常用的流程圖符號(見圖2.3)。圖2.3圖2.3中菱形框的作用是對一個給定的條件進行判斷，根據(jù)給定的條件是否成立來決定如何執(zhí)行其后的操作。它有一個入口，兩個出口。見圖2.4。連接點(小圓圈)是用于將畫在不同地方的流程線連接起來。如圖2.5中有兩個以○為標志的連接點(在連接點圈中寫上“1”)，它表示這兩個點是互相連接在一起的。實際上它們是同一個點，只是畫不下才分開來畫。用連接點，可以避免流程線的交叉或過長，使流程圖清晰。圖2.4圖2.5【例2.6】將例2.1求5!的算法用流程圖表示，流程圖見圖2.6。菱形框兩側(cè)的“Y”和“N”代表“是”(yes)和“否”(no)。如果需要將最后結(jié)果打印出來，可以在菱形框的下面再加一個輸出框，見圖2.7。圖2.6圖2.7【例2.7】將例2.2的算法用流程圖表示。將50名學生中成績在80分以上者的學號和成績打印出來。在此算法中沒有包括輸入50個學生數(shù)據(jù)的部分，如果包括這個輸入數(shù)據(jù)的部分，流程圖如圖2.9所示。圖2.9【例2.8】將例2.4的算法用流程圖表示。見圖2.11?！纠?.9】將例2.5判斷素數(shù)的算法用流程圖表示，見圖2.12。圖2.11圖2.12一個流程圖包括以下幾部分：

①表示相應操作的框；

②帶箭頭的流程線；

③框內(nèi)外必要的文字說明。需要提醒的是流程線不要忘記畫箭頭，因為它是反映流程的執(zhí)行先后次序的。用流程圖表示算法直觀形象，比較清楚地顯示出各個框之間的邏輯關系。但是這種流程圖占用篇幅較多，尤其當算法比較復雜時，畫流程圖既費時又不方便。在結(jié)構(gòu)化程序設計方法推廣之后，許多書刊已用N-S結(jié)構(gòu)化流程圖代替這種傳統(tǒng)的流程圖。2.4.3三種基本結(jié)構(gòu)和改進的流程圖1.傳統(tǒng)流程圖的弊端只規(guī)定了幾種基本結(jié)構(gòu)這些結(jié)構(gòu)是方便面式的2.三種基本結(jié)構(gòu)（1）順序結(jié)構(gòu)，如圖2.14所示，虛線框內(nèi)是一個順序結(jié)構(gòu)。（2）選擇結(jié)構(gòu)，或稱選取結(jié)構(gòu)，或稱分支結(jié)構(gòu)，如圖2.15所示。圖2.14圖2.15（3）循環(huán)結(jié)構(gòu)，它又稱重復結(jié)構(gòu)。有兩類循環(huán)結(jié)構(gòu)：

①當型(While型)循環(huán)結(jié)構(gòu)，見圖2.17(a)。②直到型(Until型)循環(huán)，見圖2.17(b)。圖2.17以上三種基本結(jié)構(gòu)，有以下共同特點：（1）只有一個入口。（2）只有一個出口。（3）結(jié)構(gòu)內(nèi)的每一部分都有機會被執(zhí)行到。（4）結(jié)構(gòu)內(nèi)不存在“死循環(huán)”(無終止的循環(huán))?；窘Y(jié)構(gòu)不一定只限于上面三種，只要具有上述4個特點的都可以作為基本結(jié)構(gòu)。人們可以自己定義基本結(jié)構(gòu)，并由這些基本結(jié)構(gòu)組成結(jié)構(gòu)化程序。一個好的算法只能由3種基本結(jié)構(gòu)相互嵌套而成2.4.4用N-S流程圖表示算法1973年I.Nassi和B.Shneiderman提出了一種新的流程圖形式，省去流線，成為N-S結(jié)構(gòu)化流程圖N-S流程圖用以下的流程圖符號：（1）順序結(jié)構(gòu):用圖2.24形式表示。A和B兩個框組成一個順序結(jié)構(gòu)。（2）選擇結(jié)構(gòu)：用圖2.25表示。它與圖2.15相應。當p條件成立時執(zhí)行A操作，p不成立則執(zhí)行B操作。圖2.24圖2.25（3）循環(huán)結(jié)構(gòu)：當型循環(huán)結(jié)構(gòu)用圖2.26形式表示。圖2.26表示當p1條件成立時反復執(zhí)行A操作，直到p1條件不成立為止。直到型循環(huán)結(jié)構(gòu)用圖2.27形式表示。圖2.26圖2.27同樣，三種基本結(jié)構(gòu)可以相互嵌套例如：YP>=100Nr=0.08r=0.06n<=10P*(1+r)=>p【例2.11】將例2.1的求5!算法用N-S圖表示。見圖2.29?！纠?.12】將例2.2的算法用N-S圖表示。將50名學生中成績高于80分的學號和成績打印出來。見圖2.31。圖2.29圖2.31【例2.13】將例2.3判定閏年的算法用N-S圖表示。見圖2.32?！纠?.14】將例2.4的算法用N-S圖表示。見圖2.33。圖2.32圖2.33【例2.15】將例2.5判別素數(shù)的算法用N-S流程圖表示。流程圖表示見圖2.34，N-S圖表示見圖2.35。圖2.35圖2.34通過以上例子，可以看出用N-S圖表示算法的優(yōu)點。它比文字描述直觀、形象、易于理解；比傳統(tǒng)流程圖緊湊易畫，尤其是它廢除了流程線，整個算法結(jié)構(gòu)是由各個基本結(jié)構(gòu)按順序組成的。N-S流程圖中的上下順序就是執(zhí)行時的順序，即圖中位置在上面的先執(zhí)行，位置在下面的后執(zhí)行。用N-S圖表示的算法都是結(jié)構(gòu)化的算法(它不可能出現(xiàn)流程無規(guī)律的跳轉(zhuǎn)，而只能自上而下地順序執(zhí)行)。N-S圖如同一個多層的盒子，又稱盒圖(boxdiagram)。2.4.5用偽代碼表示算法偽代碼(pseudocode)是用介于自然語言和計算機語言之間的文字和符號來描述算法?！纠?.16】求5!。用偽代碼表示的算法如下：開始置t的初值為1

置i的初值為2

當i<=5，執(zhí)行下面操作：使t=t×i

使i=i+1(循環(huán)體到此結(jié)束)

打印t的值結(jié)束begin/*算法開始*/1=>t2=>iwhilei<=5{t×i=>ti+1=>i}printtend/*算法結(jié)束*/【例2.17】輸出50個學生中成績高于80分者的學號和成績。用偽代碼表示算法如下：

begin/*算法開始*/ 1=>i whilei<=50 {inputniandgi i+1=>i} 1=>i whilei<=50 {ifgi≥80printniandgi i+1=>i}end/*算法結(jié)束*/【例2.18】輸出2000—2500年中的每一年是否閏年。begin/*算法開始*/2000=>ywhiley<=2500{ify能被4整除

ify不能被100整除

printy;“是閏年”

elseify被400整除

printy；“閏年”

elseprinty；“非閏年”

endifendifelseprinty;“非閏年”

endify+1=>y}end/*算法結(jié)束*/【例2.19】求1-1/2+1/3-1/4+…+1/99-1/100。用偽代碼表示的算法如下：

begin/*算法開始*/ 1=>sum2=>deno 1=>sign whiledeno<=100 {(-1)×sign=>sign sign×1/deno=>term sum