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

1、1譚浩強(qiáng)譚浩強(qiáng) 著著清華大學(xué)出版社清華大學(xué)出版社2一個(gè)程序應(yīng)包括：一個(gè)程序應(yīng)包括： 對(duì)數(shù)據(jù)的描述對(duì)數(shù)據(jù)的描述 ：數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)對(duì)操作的描述對(duì)操作的描述 ：算法：算法數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+ +算法算法= =程序程序 程序程序= =算法算法+ +數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)+ +程序設(shè)計(jì)方法程序設(shè)計(jì)方法+ +語(yǔ)言工具和環(huán)境語(yǔ)言工具和環(huán)境 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法3l 算法的概念算法的概念 l 簡(jiǎn)單算法舉例簡(jiǎn)單算法舉例 l 算法的特性算法的特性 l 怎樣表示一個(gè)算法怎樣表示一個(gè)算法 l 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈

2、魂算法程序的靈魂算法4計(jì)算機(jī)算法：計(jì)算機(jī)能夠執(zhí)行的算法。計(jì)算機(jī)算法：計(jì)算機(jī)能夠執(zhí)行的算法。 計(jì)算機(jī)算法計(jì)算機(jī)算法的分類：的分類： 數(shù)值運(yùn)算算法：求解數(shù)值；數(shù)值運(yùn)算算法：求解數(shù)值； 非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域非數(shù)值運(yùn)算算法：事務(wù)管理領(lǐng)域。 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法算法算法 ：為解決一個(gè)問(wèn)題而采取的方法和步驟為解決一個(gè)問(wèn)題而采取的方法和步驟5 例2.1 求12345 改進(jìn)算法：改進(jìn)算法：S1: S1: 使使t=1t=1S2: S2: 使使i=2i=2S3: S3: 使使t ti,i,乘積仍然放在變量乘積仍然放在變量 t t中，可表示為中，可表示為t ti

3、 it tS4: S4: 使使i i的值的值+1+1，即，即i+1i+1i iS5: S5: 如果如果i5, i5, 返回重新執(zhí)行返回重新執(zhí)行 步驟步驟S3S3以及其后的以及其后的S4S4和和S5S5； 否則，算法結(jié)束。否則，算法結(jié)束。 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法原始方法：原始方法：步驟步驟1 1：先求：先求1 12 2， 得到結(jié)果得到結(jié)果2 2。步驟步驟2 2：將步驟：將步驟1 1得到的乘得到的乘 積積2 2乘以乘以3 3，得到，得到 結(jié)果結(jié)果6 6。步驟步驟3 3：將：將6 6再乘以再乘以4 4，得，得2424。步驟步驟4 4：將：將2424再乘以再

4、乘以5 5，得，得 120120。 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法i：第個(gè)學(xué)生學(xué)號(hào)：第個(gè)學(xué)生學(xué)號(hào)i：第個(gè)學(xué)生成績(jī)：第個(gè)學(xué)生成績(jī)S1: 1iS2: 如果如果gi80，則打印，則打印ni和和gi，否則不打印，否則不打印S3: i+1iS4: 若若i50, 返回返回S2，否則，結(jié)束。，否則，結(jié)束。閏年的條件：閏年的條件：能被能被4整除，但不能被整除，但不能被100整除的年份；整除的年份；能被能被100整除，又能被整除，又能被400整除的年份；整除的年份； C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法S1: 2000yS2: 若若y不能被不能被

5、4整除，則輸出整除，則輸出y“不是閏年不是閏年”， 然然 后轉(zhuǎn)到后轉(zhuǎn)到S6S3: 若若y能被能被4整除，不能被整除，不能被100整除，則輸整除，則輸 出出y“是閏年是閏年”，然后轉(zhuǎn)到，然后轉(zhuǎn)到S6S4: 若若y能被能被100整除，又能被整除，又能被400整除，輸整除，輸 出出y“是閏年是閏年” 否則輸出否則輸出y“不是閏年不是閏年”， 然后轉(zhuǎn)到然后轉(zhuǎn)到S6S5: 輸出輸出y“不是閏年不是閏年”。S6: y+1yS7: 當(dāng)當(dāng)y2500時(shí)時(shí), 返回返回S2繼續(xù)執(zhí)行，否則，繼續(xù)執(zhí)行，否則， 結(jié)束。結(jié)束。 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二

6、章第二章 程序的靈魂算法程序的靈魂算法10019914131211S1: sigh=1S2: sum=1S3: deno=2S4: sigh=(-1)sigh S5: term= sigh(1/deno )S6: sum=sum+termS7: deno= deno +1S8:若若deno100，返回，返回S4；否則，結(jié)束。；否則，結(jié)束。 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法S1: 輸入輸入n的值的值S2: i=2S3: n被被i除，得余數(shù)除，得余數(shù)rS4:如果如果r=0，表示，表示n能被能被i整除，則打印整除，則打印n“不是素?cái)?shù)不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行，算

7、法結(jié)束；否則執(zhí)行S5S5: i+1i S6:如果如果in-1，返回，返回S3；否則打??；否則打印n“是素是素?cái)?shù)數(shù)”；然后算法結(jié)束。；然后算法結(jié)束。改進(jìn)： S6:如果i ,返回S3；否則打印n“是素?cái)?shù)”;然后算法結(jié)束。 n11有窮性：一個(gè)算法應(yīng)包含有限的操作步有窮性：一個(gè)算法應(yīng)包含有限的操作步驟而不能是無(wú)限的。驟而不能是無(wú)限的。確定性：算法中每一個(gè)步驟應(yīng)當(dāng)是確定確定性：算法中每一個(gè)步驟應(yīng)當(dāng)是確定的，而不能應(yīng)當(dāng)是含糊的、模棱兩可的。的，而不能應(yīng)當(dāng)是含糊的、模棱兩可的。 有零個(gè)或多個(gè)輸入。有零個(gè)或多個(gè)輸入。 有一個(gè)或多個(gè)輸出。有一個(gè)或多個(gè)輸出。 有效性：算法中每一個(gè)步驟應(yīng)當(dāng)能有效有效性：算法中每一個(gè)

8、步驟應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。地執(zhí)行，并得到確定的結(jié)果。 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法12 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法例2.6例2.7例2.8用自然語(yǔ)言表示算法用自然語(yǔ)言表示算法 用流程圖表示算法用流程圖表示算法 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法三種基本結(jié)構(gòu)和改進(jìn)的流程圖三種基本結(jié)構(gòu)和改進(jìn)的流程圖 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序

9、的靈魂算法程序的靈魂算法順序結(jié)構(gòu)循環(huán)結(jié)構(gòu)選擇結(jié)構(gòu)三種基本結(jié)構(gòu)的共同特點(diǎn)：三種基本結(jié)構(gòu)的共同特點(diǎn)： 只有一個(gè)入口；只有一個(gè)入口； 只有一個(gè)出口；只有一個(gè)出口； 結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到；結(jié)構(gòu)內(nèi)的每一部分都有機(jī)會(huì)被執(zhí)行到； 結(jié)構(gòu)內(nèi)不存在結(jié)構(gòu)內(nèi)不存在“死循環(huán)死循環(huán)”。 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)用用N-SN-S流程圖表示算法流程圖表示算法 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法用偽代碼表示算法用偽代碼表示算法 用傳統(tǒng)流程圖、N-S圖表示算法，直觀易懂，但繪制比較麻煩，流程圖適合表示算法，但在設(shè)計(jì)算法過(guò)

10、程中使用不是很理想。偽代碼是用介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)來(lái)描述算法。偽代碼不用圖形符號(hào)，書(shū)寫(xiě)方便，格式緊湊，便于向計(jì)算機(jī)語(yǔ)言算法過(guò)渡25求求5!。用偽代碼表示的算法如下：。用偽代碼表示的算法如下： 開(kāi)始開(kāi)始置置t的初值為的初值為1置置i的初值為的初值為2當(dāng)當(dāng)it2=iwhile iti+1=iprint tEND(算法結(jié)束算法結(jié)束) 在本算法中采用當(dāng)型循環(huán)（第在本算法中采用當(dāng)型循環(huán)（第3行到笫行到笫5行是一個(gè)行是一個(gè)當(dāng)型循環(huán)）。當(dāng)型循環(huán)）。while意思為意思為“當(dāng)當(dāng)”， 它表示當(dāng)它表示當(dāng)i=5時(shí)執(zhí)行循環(huán)體（大括弧中的兩行）的操作。時(shí)執(zhí)行循環(huán)體（大括弧中的兩行）的操作。27例2.

11、9例2.10用計(jì)算機(jī)語(yǔ)言表示算法用計(jì)算機(jī)語(yǔ)言表示算法 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法main()int i,t; t=1; i=2; while(i=5)t=t*i;i=i+1; printf(“%d”,t); C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法main()int sigh=1;float deno=2.0,sum=1.0,term;while(deno=100) sigh= -sigh; term= sigh/ deno;sum=sum+term;deno=deno+1; printf(“%f”,sum);30自頂向下自頂向

12、下 逐步細(xì)化逐步細(xì)化 模塊化設(shè)計(jì)模塊化設(shè)計(jì) 結(jié)構(gòu)化編碼結(jié)構(gòu)化編碼 C C程序設(shè)計(jì)程序設(shè)計(jì) 第二章第二章 程序的靈魂算法程序的靈魂算法31 結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)結(jié)構(gòu)化程序設(shè)計(jì)強(qiáng)調(diào)程序設(shè)計(jì)風(fēng)格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。如果面臨一個(gè)復(fù)的規(guī)范化，提倡清晰的結(jié)構(gòu)。如果面臨一個(gè)復(fù)雜的問(wèn)題，是難以一下子寫(xiě)出一個(gè)層次分明、雜的問(wèn)題，是難以一下子寫(xiě)出一個(gè)層次分明、結(jié)構(gòu)清晰、算法正確的程序的。結(jié)構(gòu)化程序設(shè)結(jié)構(gòu)清晰、算法正確的程序的。結(jié)構(gòu)化程序設(shè)計(jì)方法的基本思路是，把一個(gè)復(fù)雜問(wèn)題的求解計(jì)方法的基本思路是，把一個(gè)復(fù)雜問(wèn)題的求解過(guò)程分階段進(jìn)行，每個(gè)階段處理的問(wèn)題都控制過(guò)程分階段進(jìn)行，每個(gè)階

13、段處理的問(wèn)題都控制在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。具體說(shuō)，采在人們?nèi)菀桌斫夂吞幚淼姆秶鷥?nèi)。具體說(shuō)，采取以下方法保證得到結(jié)構(gòu)化的程序。取以下方法保證得到結(jié)構(gòu)化的程序。32l自頂向下；(2) 逐步細(xì)化；l(3) 模塊化設(shè)計(jì)；(4) 結(jié)構(gòu)化編碼。 在接受一個(gè)任務(wù)后應(yīng)怎樣著手進(jìn)行呢?有兩種不同的方法：一種是自頂向下，逐步細(xì)化；一種是自下而上，逐步積累。以寫(xiě)文章為例來(lái)說(shuō)明這個(gè)問(wèn)題。有的人胸有全局，先設(shè)想好整個(gè)文章分成哪幾個(gè)部分，然后再進(jìn)一步考慮每一部分分成哪幾節(jié)，每一節(jié)分成哪幾段，每一段應(yīng)包含什么內(nèi)容，如圖2.36示意。 用這種方法逐步分解，直到作者認(rèn)為可以直接將各小段表達(dá)為文字語(yǔ)句為止。這種方法就叫 做

14、“自頂向下，逐步細(xì)化”。33圖2.3634另有些人寫(xiě)文章時(shí)不擬提綱，如同寫(xiě)信一樣提起筆就寫(xiě)，想到哪里就寫(xiě)到哪里，直到他認(rèn)為把想寫(xiě)的內(nèi)容都寫(xiě)出來(lái)了為止。這種方法叫做“自下而上，逐步積累”。顯然，用第一種方法考慮周全，結(jié)構(gòu)清晰，層次分明，作者容易寫(xiě)，讀者容易看。如果發(fā)現(xiàn)某一部分中有一段內(nèi)容不妥，需要修改，只需找出該部分，修改有關(guān)段落即可，與其他部分無(wú)關(guān)。我們提倡用這種方法設(shè)計(jì)程序。這就是用工程的方法設(shè)計(jì)程序。35例2.22 將1到1000之間的素?cái)?shù)打印出來(lái)。我們已在本章中討論過(guò)判別素?cái)?shù)的方法，現(xiàn)在采用“篩法”來(lái)求素?cái)?shù)表。所謂“篩法”指的是“埃拉托色尼(Eratosthenes)篩法”。他是古希臘的

15、著名數(shù)學(xué)家。他采取的方法是 ，在一張紙上寫(xiě)上1到1000全部整數(shù)，然后逐個(gè)判斷它們是否素?cái)?shù)，找出一個(gè)非素?cái)?shù)，就把它挖掉，最后剩下的就是素?cái)?shù)，見(jiàn)圖2.37。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50圖2.37具體做法如下： 36(1) 先將1挖掉(因?yàn)?不是素?cái)?shù))。(2) 用2去除它后面的各個(gè)數(shù)，把能被2整除的數(shù)挖掉，即把2的倍數(shù)挖掉。(3) 用3去除它后面各數(shù)

16、，把3的倍數(shù)挖掉。(4) 分別用4、5各數(shù)作為除數(shù)去除這些數(shù)以后的各數(shù)。這個(gè)過(guò)程一直進(jìn)行到在除數(shù)后面的數(shù)已全被挖掉為止。例如在圖2.37中找150的素?cái)?shù)，要一直進(jìn)行到除數(shù)為47為止。(事實(shí)上，可以簡(jiǎn)化，如果需要找1n范圍內(nèi)素?cái)?shù)表，只需進(jìn)行到除數(shù)為n開(kāi)方(取其整數(shù)) 即可。例如對(duì)150，只需進(jìn)行到將7(50開(kāi)方)作為除數(shù)即可。)上面的算法可表示為：37(1) 挖去1；(2) 用下一個(gè)未被挖去的數(shù)p去除p后面各數(shù)，把p的倍數(shù)挖掉；(3) 檢查p是否小于n的整數(shù)部分(如果n=1000，則檢查p31?) ，如果是，則返回(2) 繼續(xù)執(zhí)行，否則就結(jié)束；(4) 紙上剩下的數(shù)就是素?cái)?shù)。解題的基本思路有了，但

17、要變成計(jì)算機(jī)的操作，還要做進(jìn)一步的分析，如怎樣判斷一個(gè)數(shù)是否已被“挖掉”，怎樣找出某一個(gè)數(shù)p的倍數(shù)，怎樣打印出未被挖掉的數(shù)。38用自頂向下逐步細(xì)化的方法來(lái)處理這個(gè)問(wèn)題，先進(jìn)行“頂層設(shè)計(jì)”，見(jiàn)圖2.38。也可以用流程圖進(jìn)行逐步細(xì)化。流程圖2.39表示流程的粗略情況，把要做的三部分工作分別用A、B、C表示。圖2.38 圖2.39 39這三部分還不夠具體，要進(jìn)一步細(xì)化。A部分可以細(xì)化為圖2.40。先輸入n，然后將1輸入給x1，2輸入給x2，1000輸入給x1000。B部分可以細(xì)化為圖2.41。圖2.40 圖2.4140圖2.41中的B1與B2不能再分了。B1處理的方法是：使x1=0，即哪個(gè)數(shù)不是素?cái)?shù)， 就使它等于0，以后把不等于零的數(shù)打印出來(lái)就是所求的素?cái)?shù)表。B3中的循環(huán)體內(nèi)以D標(biāo)志的部分還要進(jìn)一步細(xì)化，對(duì)D