C程序設(shè)計(jì)第2章

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

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

=算法

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

+程序設(shè)計(jì)方法

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

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

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

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

還有其他方法方法有優(yōu)劣之分，希望采用的方法簡(jiǎn)單、運(yùn)算步驟少的方法，我們所關(guān)心的只是計(jì)算機(jī)算法。計(jì)算機(jī)算法可分為兩大類別：數(shù)值算法和非數(shù)值算法。數(shù)值運(yùn)算的目的是求數(shù)值解，此種算法比較成熟（庫(kù)函數(shù)）。非數(shù)值運(yùn)算包括的面十分廣泛，最常見的是用于事務(wù)管理領(lǐng)域，此種算法種類繁多。2.2簡(jiǎn)單算法舉例【例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怎么辦？可以設(shè)兩個(gè)變量，一個(gè)變量代表被乘數(shù)，一個(gè)變量代表乘數(shù)。不另設(shè)變量存放乘積結(jié)果，而直接將每一步驟的乘積放在被乘數(shù)變量中。今設(shè)p為被乘數(shù)，i為乘數(shù)。用循環(huán)算法來求結(jié)果?？梢詫⑺惴ǜ膶懭缦拢?/p>

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。算法只需作很少的改動(dòng)即可：

S1：1=>pS2：3=>iS3：p×i=>pS4：i+2=>iS5：若i≤11，返回S3；否則，結(jié)束。可以看出，用這種方法表示的算法具有通用性、靈活性?！纠?.2】有50個(gè)學(xué)生，要求將他們之中成績(jī)?cè)?0分以上的學(xué)號(hào)和成績(jī)輸出。用n表示學(xué)生學(xué)號(hào)，n1代表第一個(gè)學(xué)生學(xué)號(hào)，ni代表第i個(gè)學(xué)生學(xué)號(hào)。用g代表學(xué)生成績(jī)，gi代表第i個(gè)學(xué)生成績(jī)，算法可表示如下。

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

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

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：當(dāng)y≤2500時(shí)，轉(zhuǎn)S2繼續(xù)執(zhí)行，如y＞2500，算法停止。在例2.3的算法中，采取了多次判斷，每做一步，都分別分離出一些范圍(已能判定為閏年或非閏年)，逐步縮小范圍，使被判斷的范圍愈來愈小，直至執(zhí)行S5時(shí)，只可能是非閏年。見圖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中先預(yù)設(shè)sign（代表多項(xiàng)式中各項(xiàng)的符號(hào)，它的值為1或-1）。在步驟S2中使sum等于1，相當(dāng)于已將多項(xiàng)式中的第一項(xiàng)放到了sum中。在步驟S3中使分母的值為2。在步驟S4中使sign的值變?yōu)?1。在步驟S5中求出多項(xiàng)式中第2項(xiàng)的值-1/2。在步驟S6中將剛才求出的第二項(xiàng)的值-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ī)律反復(fù)執(zhí)行S4到S8步驟，直到分母大于100為止。一共執(zhí)行了99次循環(huán)，向sum累加入了99個(gè)分?jǐn)?shù)。sum最后的值就是多項(xiàng)式的值?！纠?.5】對(duì)一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù)。判斷一個(gè)數(shù)n(n≥3)是否素?cái)?shù)的方法是很簡(jiǎn)單的：將n作為被除數(shù)，將2到(n-1)各個(gè)整數(shù)輪流作為除數(shù)，如果都不能被整除，則n為素?cái)?shù)。算法可以表示如下：

S1：輸入n的值

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

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

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

①表示相應(yīng)操作的框；

②帶箭頭的流程線；

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

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

置i的初值為2

當(dāng)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個(gè)學(xué)生中成績(jī)高于80分者的學(xué)號(hào)和成績(jī)。用偽代碼表示算法如下：

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