幻燈片-C語(yǔ)言程序設(shè)計(jì)-第2章.ppt

1、C程序設(shè)計(jì),講師：劉楠 Email: ,第2章 程序的靈魂-算法,一個(gè)程序包括以下兩個(gè)方面的內(nèi)容： (1)對(duì)數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類型和數(shù)據(jù)的組織形式，即數(shù)據(jù)結(jié)構(gòu)。 (2)對(duì)操作的描述。即操作步驟，也就是算法。 數(shù)據(jù)是操作的對(duì)象，操作的目的是對(duì)數(shù)據(jù)進(jìn)行加工處理，以得到期望的結(jié)果。作為程序設(shè)計(jì)人員，必須認(rèn)真考慮和設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)和操作步驟（即算法）。著名計(jì)算機(jī)科學(xué)家沃思提出一個(gè)公式：數(shù)據(jù)結(jié)構(gòu)+算法=程序。 實(shí)際上，一個(gè)程序除了以上兩個(gè)主要要素之外，還應(yīng)當(dāng)采用結(jié)構(gòu)化程序設(shè)計(jì)方法進(jìn)行程序設(shè)計(jì)，并且用某一種計(jì)算機(jī)語(yǔ)言表示。因此，算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)方法和語(yǔ)言工具4個(gè)方面是一個(gè)程序設(shè)計(jì)人員所應(yīng)

2、具備的知識(shí)。,2.1 算法的概念,廣義地說(shuō)，為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱為算法(algorithm)。例如，描述太極拳動(dòng)作的圖解，就是太極拳的算法。一首歌曲的樂(lè)譜，也可以稱為該歌曲的算法，因?yàn)樗付搜葑嘣摳枨拿恳粋€(gè)步驟，按照它的規(guī)定就能演奏出預(yù)定的曲子。 對(duì)同一個(gè)問(wèn)題，可以有不同的解題方法和步驟。 計(jì)算機(jī)算法可分為兩大類別： 數(shù)值運(yùn)算算法 非數(shù)值運(yùn)算算法,2.2 簡(jiǎn)單算法舉例,例2.1求12345 算法1： 步驟1：先求1*2，得到結(jié)果2。 步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6。 步驟3：將6再乘以4，得24。 步驟4：將24再乘以5，得120。,算法2： S1：使p

3、=1 S2：使i=2 S3：使p*i，乘積仍放在變量p中，可表示為p*ip S4：使i的值加1，即i+1i S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結(jié)束。最后得p的值就是5！的值。,例2.2有50個(gè)學(xué)生，要求將他們之中成績(jī)?cè)?0分以上的學(xué)號(hào)和成績(jī)輸出,ni代表第i個(gè)學(xué)生學(xué)號(hào)。gi代表第i個(gè)學(xué)生成績(jī)，算法如下： S1：1i S2：如果gi80，則輸出ni和gi；否則不輸出 S3：i+1i S4：如果i50，返回S2，繼續(xù)執(zhí)行；否則，算法結(jié)束。,例2.3判定2000-2500年中的每一年是否是閏年,閏年的條件是：(1)能被4整除，但不能被100整除的年份是閏年

4、，如1996年、2004年；(2)能被400整除的年份是閏年，如1600年、2000年。 設(shè)y為被檢測(cè)的年份?？刹捎靡韵虏襟E： S1：2000y S2：若y不能被4整除，則輸出 “y不是閏年”。然后轉(zhuǎn)到S6 S3：若y能被4整除，不能被100整除，則輸出 “y是閏年”。然后轉(zhuǎn)到S6 S4：若y能被400整除，輸出 “y是閏年”，然后轉(zhuǎn)到S6 S5：輸出 “y不是閏年” S6：y+1y S7：當(dāng)y2500時(shí)，轉(zhuǎn)S2繼續(xù)執(zhí)行，否則算法停止。,例2.4求1-1/2+1/3-1/4+1/99-1/100,算法如下： S1：sign=1 S2：sum=1 S3：deno=2 S4：sign=(-1)*s

5、ign S5：term=sign*(1/deno) S6：sum=sum+term S7：deno=deno+1 S8：若deno100返回S4；否則算法結(jié)束。,例2.5對(duì)一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù),判斷一個(gè)數(shù)n(n3)是否素?cái)?shù)的方法是將n作為被除數(shù)，將2到n-1各個(gè)整數(shù)先后作為除數(shù)，如果都不能被整除，則n為素?cái)?shù)。 算法如下： S1：輸入n的值 S2：i=2（i作為除數(shù)） S3：n被i除，得余數(shù)r S4：如果r=0，表示n能被i整除，則輸出 “n不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行S5 S5：i+1i S6：如果in-1，返回S3；否則輸出 “n是素?cái)?shù)”，然后結(jié)束。,2.3 算法

6、的特性,（1）有窮性。一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無(wú)限的。 （2）確定性。算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是含糊的、模棱兩可的。 （3）有零個(gè)或多個(gè)輸入。所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息。 （4）有一個(gè)或多個(gè)輸出。算法的目的是為了求解，“解”就是輸出。 （5）有效性。算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。,2.4 怎樣表示一個(gè)算法,為了表示一個(gè)算法，可以用不同的方法。 常用的方法有： 自然語(yǔ)言 傳統(tǒng)流程圖 N-S流程圖 偽代碼 PAD圖等。,2.4.2 用流程圖表示算法,例2.6將例2.1求5!的算法用流程圖表示,例2.7將例2.2的算法用

7、流程圖表示。將50名學(xué)生中成績(jī)?cè)?0分以上者的學(xué)號(hào)和成績(jī)輸出,例2.8將例2.3判定閏年的算法用流程圖表示,例2.9將例2.4的算法用流程圖表示。即求1-1/2+1/3-1/4+1/99-1/100,例2.10將例2.5判斷素?cái)?shù)的算法用流程圖表示,2.4.3 三種基本結(jié)構(gòu),（1）順序結(jié)構(gòu),（2）選擇結(jié)構(gòu),（3）循環(huán)結(jié)構(gòu) 當(dāng)型循環(huán) 直到型循環(huán),2.4.4 用N-S流程圖表示算法,N-S流程圖用以下的流程圖符號(hào)： (1)順序結(jié)構(gòu)：A和B兩個(gè)框組成一個(gè)順序結(jié)構(gòu)。,(2)選擇結(jié)構(gòu)：當(dāng)條件p成立時(shí)執(zhí)行操作A ，條件p不成立則執(zhí)行操作B。,(3)循環(huán)結(jié)構(gòu)： 當(dāng)型循環(huán)結(jié)構(gòu)下，圖符表示先判斷后執(zhí)行，當(dāng)條件p成

8、立時(shí)反復(fù)執(zhí)行操作A ，直到條件p不成立為止。 直到型循環(huán)結(jié)構(gòu)下，圖符表示先執(zhí)行后判斷，當(dāng)條件p不成立時(shí)反復(fù)執(zhí)行A操作，直到p條件成立為止。,例2.11將例2.1的求5！算法用N-S圖表示,例2.12將例2.2的算法用N-S圖表示。將50名學(xué)生中成績(jī)高于80分的學(xué)號(hào)和成績(jī)打印出來(lái),例2.13將例2.3判定閏年的算法用N-S圖表示,例2.14將例2.4的算法用N-S圖表示。求1-1/2+1/3+1/99-1/100,例2.15將例2.5判斷素?cái)?shù)的算法用N-S流程圖表示,2.4.5 用偽代碼表示算法,例2.16用偽代碼表示算法(求5!) 開(kāi)始 置t的初值為1 置i的初值為2 當(dāng)i=5，執(zhí)行下面操作：

9、 使t=t*i 使i=i+1 循環(huán)體到此結(jié)束 輸出t的值 結(jié)束,例2.16用偽代碼表示算法(求5!)也可以寫成,begin i=t 2=I while it i+1=i print t end,例2.17輸出50個(gè)學(xué)生中成績(jī)高于80分的學(xué)號(hào)和成績(jī) begin 1=i while ii 1=i while i=80 print ni and gi i+1=i end,例2.18輸出2000-2500年每一年是否閏年 begin 2000=y while yy end,例2.19求1-1/2+1/3-1/4+1/99-1/100 begin 1=sum 2=deno 1=sign while de

10、nosign sign*1/deno =term sum+term =sum deno+1 =deno print sum end,2.4.6 用計(jì)算機(jī)語(yǔ)言表示算法,例2.20將例2.11表示的算法(求5!)用C語(yǔ)言表示,#include main() int i, t; t=1; i=2; while(i=5) t=t*i; i=i+1; printf(%d, t); ,例2.21求例2.14表示的算法(求級(jí)數(shù)的值)用C語(yǔ)言表示,#include main() int sign=1; float deno=2.0, sum=1.0, term; while(deno=100) sign=-s

11、ign; term=sign/deno; sum=sum+term; deno=deno+1; printf(%f, sum); ,2.5 結(jié)構(gòu)化程序設(shè)計(jì)方法,自頂向下 逐步細(xì)化 模塊化設(shè)計(jì) 結(jié)構(gòu)化編碼,習(xí)題,2.4 用傳統(tǒng)流程圖表示求解以下問(wèn)題的算法 (1)有兩個(gè)瓶子A和B，分別盛放醋和醬油，要求將它們互換。 (2)依次將10個(gè)數(shù)輸入，要求將其中最大的數(shù)輸出 (3)有3個(gè)數(shù)a、b、c，要求按大小順序把它們輸出 (4)求1+2+3+100 (5)判斷一個(gè)數(shù)n能否同時(shí)被3和5整除 (6)將100-200之間的素?cái)?shù)輸出 (7)求兩個(gè)數(shù)m和n的最大公約數(shù) (8)求方程式ax2+bx+c=0的根。分別考慮：有兩個(gè)不等的實(shí)根；有兩個(gè)相等的實(shí)根,(1)有兩個(gè)瓶子A和B，分別盛放醋和醬