秋計(jì)算機(jī)程序設(shè)計(jì)C第2章詳版課資

1、c程序設(shè)計(jì)副教授：顏兵兵email：1課堂優(yōu)質(zhì)第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ì)人員所應(yīng)具備

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

3、表示為p*ips4：使i的值加1，即i+1is5：如果i不大于5，返回重新執(zhí)行步驟s3以及其后的步驟s4和s5；否則，算法結(jié)束。最后得p的值就是5！的值。5課堂優(yōu)質(zhì)例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：1is2：如果gi80，則輸出ni和gi；否則不輸出s3：i+1is4：如果i50，返回s2，繼續(xù)執(zhí)行；否則，算法結(jié)束。6課堂優(yōu)質(zhì)例2.3判定2000-2500年中的每一年是否是閏年閏年的條件是：(1)能被4整除，但不能被100整除的年份是閏年，如1996年、2004年；(2)能被400整除的年份是閏年

4、，如1600年、2000年。設(shè)y為被檢測(cè)的年份。可采用以下步驟：s1：2000ys2：若y不能被4整除，則輸出 “y不是閏年”。然后轉(zhuǎn)到s6s3：若y能被4整除，不能被100整除，則輸出 “y是閏年”。然后轉(zhuǎn)到s6s4：若y能被400整除，輸出 “y是閏年”，然后轉(zhuǎn)到s6s5：輸出 “y不是閏年”s6：y+1ys7：當(dāng)y2500時(shí)，轉(zhuǎn)s2繼續(xù)執(zhí)行，否則算法停止。7課堂優(yōu)質(zhì)例2.4求1-1/2+1/3-1/4+1/99-1/100算法如下：s1：sign=1s2：sum=1s3：deno=2s4：sign=(-1)*signs5：term=sign*(1/deno)s6：sum=sum+term

5、s7：deno=deno+1s8：若deno100返回s4；否則算法結(jié)束。8課堂優(yōu)質(zhì)例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ù)rs4：如果r=0，表示n能被i整除，則輸出 “n不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行s5s5：i+1is6：如果in-1，返回s3；否則輸出 “n是素?cái)?shù)”，然后結(jié)束。9課堂優(yōu)質(zhì)2.3 算法的特性（1）有窮性。一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無(wú)限的。（2）確定性。算法中

6、的每一個(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é)果。10課堂優(yōu)質(zhì)2.4 怎樣表示一個(gè)算法為了表示一個(gè)算法，可以用不同的方法。常用的方法有：自然語(yǔ)言傳統(tǒng)流程圖n-s流程圖 偽代碼pad圖等。11課堂優(yōu)質(zhì)2.4.2 用流程圖表示算法12課堂優(yōu)質(zhì)例2.6將例2.1求5!的算法用流程圖表示l 算法2：l s1：使t=1l s2：使i=2l s3：使t*i，乘積仍放在變量t中，可表示為t*itl

7、 s4：使i的值加1，即i+1il s5：如果i不大于5，返回重新執(zhí)行步驟s3以及其后的步驟s4和s5；否則，算法結(jié)束。最后得t的值就是5！的值。13課堂優(yōu)質(zhì)例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ī)，算法如下：ls1：1ils2：如果gi80，則輸出ni和gi；否則不輸出ls3：i+1ils4：如果i50，返回s2，繼續(xù)執(zhí)行；否則，算法結(jié)束。14課堂優(yōu)質(zhì)例2.8將例2.3判定閏年的算法用流程圖表示s1：2000ys2：若y不能被4整除，則輸出 “y不是閏年”。然后轉(zhuǎn)到s6s3：若y能被4整除，不能被10

8、0整除，則輸出 “y是閏年”。然后轉(zhuǎn)到s6s4：若y能被400整除，輸出 “y是閏年”，然后轉(zhuǎn)到s6s5：輸出 “y不是閏年”s6：y+1ys7：當(dāng)y2500時(shí)，轉(zhuǎn)s2繼續(xù)執(zhí)行，否則算法停止。15課堂優(yōu)質(zhì)例2.9將例2.4的算法用流程圖表示。即求1-1/2+1/3-1/4+1/99-1/100算法如下：s1：sign=1s2：sum=1s3：deno=2s4：sign=(-1)*signs5：term=sign*(1/deno)s6：sum=sum+terms7：deno=deno+1s8：若deno100返回s4；否則算法結(jié)束。16課堂優(yōu)質(zhì)例2.10將例2.5判斷素?cái)?shù)的算法用流程圖表示ls1

9、：輸入n的值ls2：i=2（i作為除數(shù)）ls3：n被i除，得余數(shù)rls4：如果r=0，表示n能被i整除，則輸出 “n不是素?cái)?shù)”，算法結(jié)束；否則執(zhí)行s5ls5：i+1ils6：如果in-1，返回s3；否則輸出 “n是素?cái)?shù)”，然后結(jié)束。17課堂優(yōu)質(zhì)2.4.3 三種基本結(jié)構(gòu)（1）順序結(jié)構(gòu)18課堂優(yōu)質(zhì)（2）選擇結(jié)構(gòu)19課堂優(yōu)質(zhì)（3）循環(huán)結(jié)構(gòu) 當(dāng)型循環(huán) 直到型循環(huán)20課堂優(yōu)質(zhì)2.4.4 用n-s流程圖表示算法n-s流程圖用以下的流程圖符號(hào)：(1)順序結(jié)構(gòu)：a和b兩個(gè)框組成一個(gè)順序結(jié)構(gòu)。ab21課堂優(yōu)質(zhì)(2)選擇結(jié)構(gòu)：當(dāng)條件p成立時(shí)執(zhí)行操作a ，條件p不成立則執(zhí)行操作b。22課堂優(yōu)質(zhì)(3)循環(huán)結(jié)構(gòu)：當(dāng)型循

10、環(huán)結(jié)構(gòu)下，圖符表示先判斷后執(zhí)行，當(dāng)條件p成立時(shí)反復(fù)執(zhí)行操作a ，直到條件p不成立為止。直到型循環(huán)結(jié)構(gòu)下，圖符表示先執(zhí)行后判斷，當(dāng)條件p不成立時(shí)反復(fù)執(zhí)行a操作，直到p條件成立為止。a當(dāng)p1a直到p223課堂優(yōu)質(zhì)例2.11將例2.1的求5！算法用n-s圖表示24課堂優(yōu)質(zhì)例2.12將例2.2的算法用n-s圖表示。將50名學(xué)生中成績(jī)高于80分的學(xué)號(hào)和成績(jī)打印出來(lái)25課堂優(yōu)質(zhì)例2.13將例2.3判定閏年的算法用n-s圖表示 26課堂優(yōu)質(zhì)例2.14將例2.4的算法用n-s圖表示。求1-1/2+1/3+1/99-1/10027課堂優(yōu)質(zhì)例2.15將例2.5判斷素?cái)?shù)的算法用n-s流程圖表示28課堂優(yōu)質(zhì)2.4.6

11、 用計(jì)算機(jī)語(yǔ)言表示算法例2.16將例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); 29課堂優(yōu)質(zhì)例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);30課堂優(yōu)質(zhì)2.5

12、結(jié)構(gòu)化程序設(shè)計(jì)方法l自頂向下l逐步細(xì)化l模塊化設(shè)計(jì)l結(jié)構(gòu)化編碼31課堂優(yōu)質(zhì)習(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í)根32課堂優(yōu)質(zhì)習(xí)題1l有兩個(gè)瓶子a和b，分別盛放醋和醬油，要求將它們互換#include stdafx.hin

13、t main(int argc, char* argv)int a;int b;a=1;b=2;printf(a=%d b=%dn, a, b);int c;c=a;a=b;b=c;printf(a=%d b=%dn, a, b);return 0;33課堂優(yōu)質(zhì)習(xí)題2l依次將10個(gè)數(shù)輸入，要求將其中最大的數(shù)輸出#include stdafx.hint main(int argc, char* argv)int a;int max;scanf(%d, &a);max=a;for(int i=2; i max)max=a;printf(max=%dn, max);return 0;34課堂

14、優(yōu)質(zhì)習(xí)題3l有3個(gè)數(shù)a、b、c，要求按大小順序把它們輸出#include stdafx.hint main(int argc, char* argv)int a, b, c;int temp;scanf(a=%d b=%d c=%d, &a, &b, &c);if(ab)temp=a;a=b;b=temp;if(bc)temp=b;b=c;c=temp;if(ab)temp=a;a=b;b=temp;printf(a=%d b=%d c=%dn, a, b, c);return 0;35課堂優(yōu)質(zhì)習(xí)題4l求1+2+3+100#include stdafx.hint mai

15、n(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;36課堂優(yōu)質(zhì)習(xí)題5l判斷一個(gè)數(shù)n能否同時(shí)被3和5整除#include int main(int argc, char * argv)int n;scanf(n=%d, &n);if(n%3=0 & n%5=0)printf(%d能夠被能夠被3和和5同時(shí)整除同時(shí)整除n, n);elseprintf(%d不能夠被不能夠被3和和5同時(shí)整除同時(shí)整除n, n);return

16、0; 37課堂優(yōu)質(zhì)習(xí)題6l將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);elseprintf(%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;38課堂優(yōu)質(zhì)習(xí)題7l求兩個(gè)數(shù)m和n的最大公約數(shù)#include int main(int argc, char * argv)int m, n;int min;scanf(%d %d, &m, &n);if(m=1; i-)if(m%i=0 & n%i=0) printf(%d是%d和%d的最大公約數(shù)n, i, m, n); break;return 0;39課堂優(yōu)質(zhì)習(xí)題8：求方程式ax2+bx+c=0的根。分別考慮：有兩個(gè)不等的實(shí)根；有兩個(gè)相等的實(shí)根#include #include int main(