C程序設計第二章

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

2、魂算法程序的靈魂算法4計算機算法：計算機能夠執(zhí)行的算法。計算機算法：計算機能夠執(zhí)行的算法。 計算機算法計算機算法的分類：的分類： 數(shù)值運算算法：求解數(shù)值；數(shù)值運算算法：求解數(shù)值； 非數(shù)值運算算法：事務管理領域非數(shù)值運算算法：事務管理領域。 C C程序設計程序設計 第二章第二章 程序的靈魂算法程序的靈魂算法算法算法 ：為解決一個問題而采取的方法和步驟為解決一個問題而采取的方法和步驟5 例2.1 求12345 改進算法：改進算法：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程序設計程序設計 第二章第二章 程序的靈魂算法程序的靈魂算法原始方法：原始方法：步驟步驟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程序設計程序設計 第二章第二章 程序的靈魂算法程序的靈魂算法i：第個學生學號：第個學生學號i：第個學生成績：第個學生成績S1: 1iS2: 如果如果gi80，則打印，則打印ni和和gi，否則不打印，否則不打印S3: i+1iS4: 若若i50, 返回返回S2，否則，結(jié)束。，否則，結(jié)束。閏年的條件：閏年的條件：能被能被4整除，但不能被整除，但不能被100整除的年份；整除的年份；能被能被100整除，又能被整除，又能被400整除的年份；整除的年份； C C程序設計程序設計 第二章第二章 程序的靈魂算法程序的靈魂算法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: 當當y2500時時, 返回返回S2繼續(xù)執(zhí)行，否則，繼續(xù)執(zhí)行，否則， 結(jié)束。結(jié)束。 C C程序設計程序設計 第二章第二章 程序的靈魂算法程序的靈魂算法 C C程序設計程序設計 第二

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程序設計程序設計 第二章第二章 程序的靈魂算法程序的靈魂算法S1: 輸入輸入n的值的值S2: i=2S3: n被被i除，得余數(shù)除，得余數(shù)rS4:如果如果r=0，表示，表示n能被能被i整除，則打印整除，則打印n“不是素數(shù)不是素數(shù)”，算法結(jié)束；否則執(zhí)行，算

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

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

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

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

11、9例2.10用計算機語言表示算法用計算機語言表示算法 C C程序設計程序設計 第二章第二章 程序的靈魂算法程序的靈魂算法main()int i,t; t=1; i=2; while(i=5)t=t*i;i=i+1; printf(“%d”,t); C C程序設計程序設計 第二章第二章 程序的靈魂算法程序的靈魂算法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、下 逐步細化逐步細化 模塊化設計模塊化設計 結(jié)構(gòu)化編碼結(jié)構(gòu)化編碼 C C程序設計程序設計 第二章第二章 程序的靈魂算法程序的靈魂算法31 結(jié)構(gòu)化程序設計強調(diào)程序設計風格和程序結(jié)構(gòu)結(jié)構(gòu)化程序設計強調(diào)程序設計風格和程序結(jié)構(gòu)的規(guī)范化，提倡清晰的結(jié)構(gòu)。如果面臨一個復的規(guī)范化，提倡清晰的結(jié)構(gòu)。如果面臨一個復雜的問題，是難以一下子寫出一個層次分明、雜的問題，是難以一下子寫出一個層次分明、結(jié)構(gòu)清晰、算法正確的程序的。結(jié)構(gòu)化程序設結(jié)構(gòu)清晰、算法正確的程序的。結(jié)構(gòu)化程序設計方法的基本思路是，把一個復雜問題的求解計方法的基本思路是，把一個復雜問題的求解過程分階段進行，每個階段處理的問題都控制過程分階段進行，每個階

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

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

15、著名數(shù)學家。他采取的方法是 ，在一張紙上寫上1到1000全部整數(shù)，然后逐個判斷它們是否素數(shù)，找出一個非素數(shù)，就把它挖掉，最后剩下的就是素數(shù)，見圖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挖掉(因為1不是素數(shù))。(2) 用2去除它后面的各個數(shù)，把能被2整除的數(shù)挖掉，即把2的倍數(shù)挖掉。(3) 用3去除它后面各數(shù)

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

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