1、C程序設(shè)計(jì),副教授：顏兵兵 Email：,第2章 程序的靈魂-算法,一個(gè)程序包括以下兩個(gè)方面的內(nèi)容： (1)對(duì)數(shù)據(jù)的描述。在程序中要指定數(shù)據(jù)的類(lèi)型和數(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ì)人員所

2、應(yīng)具備的知識(shí)。,2.1 算法的概念,廣義地說(shuō)，為解決一個(gè)問(wèn)題而采取的方法和步驟，就稱(chēng)為算法(algorithm)。例如，描述太極拳動(dòng)作的圖解，就是太極拳的算法。一首歌曲的樂(lè)譜，也可以稱(chēng)為該歌曲的算法，因?yàn)樗付搜葑嘣摳枨拿恳粋€(gè)步驟，按照它的規(guī)定就能演奏出預(yù)定的曲子。 對(duì)同一個(gè)問(wè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=1 S2：使i=2 S3：使p*i，乘積仍放在變量p中

3、，可表示為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整除的年份是閏年，如1996年、2004年；(2)能被400整除的年份是

4、閏年，如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)*sign S5：term=sign*(1/deno) S6

5、：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 算法的特性,（1）有窮性。一個(gè)算法應(yīng)包含有限的操作步驟，而不

6、能是無(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： S1：使t=1 S2：使i=2 S3：使t*i，乘積仍放在變量t中，可表

7、示為t*it S4：使i的值加1，即i+1i S5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否則，算法結(jié)束。最后得t的值就是5！的值。,例2.7將例2.2的算用流程圖表示。將50名學(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.8將例2.3判定閏年的算法用流程圖表示,S1：2000y S2：若y不能被4整除，則輸出 “y不是閏年”。然后轉(zhuǎn)到S6 S3：若y能被4整除，不能被100整

8、除，則輸出 “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.9將例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)*sign S5：term=sign*(1/deno) S6：sum=sum+term S7：deno=deno+1 S8：若deno100返回S4；否則算法結(jié)束。,例2.10將例2.5判斷素?cái)?shù)的算法用流程圖表示,S

9、1：輸入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.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成立時(shí)反復(fù)執(zhí)行

10、操作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.6 用計(jì)算機(jī)語(yǔ)言表示算法,例2.16將例2.11表示的算法(求5!)用C語(yǔ)言表示 #include main() int i, t;

11、t=1; i=2; while(i=5) t=t*i; i=i+1; printf(“%d”, t); ,例2.17求例2.14表示的算法(求級(jí)數(shù)的值)用C語(yǔ)言表示,#include main() int sign=1; float deno=2.0, sum=1.0, term; while(deno=100) sign=-sign; 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è)

12、瓶子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í)根,習(xí)題1,有兩個(gè)瓶子A和B，分別盛放醋和醬油，要求將它們互換,#include stdafx.h int main(int argc, char* argv) int A; int B; A=1; B=2; printf(A=

13、%d B=%dn, A, B); int C; C=A; A=B; B=C; printf(A=%d B=%dn, A, B); return 0; ,習(xí)題2,依次將10個(gè)數(shù)輸入，要求將其中最大的數(shù)輸出,#include stdafx.h int main(int argc, char* argv) int a; int max; scanf(%d, ,習(xí)題3,有3個(gè)數(shù)a、b、c，要求按大小順序把它們輸出,#include stdafx.h int main(int argc, char* argv) int a, b, c; int temp; scanf(a=%d b=%d c=%d, ,

14、習(xí)題4,求1+2+3+100,#include stdafx.h int main(int argc, char* argv) int sum; sum=0; for(int i=1; i=100; i+) sum=sum+i; printf(1+2+3+.+100=%dn, sum); return 0; ,習(xí)題5,判斷一個(gè)數(shù)n能否同時(shí)被3和5整除,#include int main(int argc, char * argv) int n; scanf(n=%d, ,習(xí)題6,將100-200之間的素?cái)?shù)輸出,int main(int argc, char * argv) int n; for(n=100; n=200; n+) if(judge(n) = 0) printf(%d是素?cái)?shù)n, n); else printf(%d不是素?cái)?shù)n, n); return 0; ,#include #include int judge(int n) int w; w=0; for(int i=2; i=sqrt(n); i+) int r; r=n%i; if(r=0) w=1; break; return w; ,習(xí)題7,求兩個(gè)數(shù)m和n的最大公約