C程序設(shè)計(jì)1.第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ī)語言表示。因此，算法、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)方法和語言工具4個(gè)方面是一個(gè)程序設(shè)計(jì)人員所應(yīng)具備的知識(shí)。2.2.1算法的概念

廣義地說，為解決一個(gè)問題而采取的方法和步驟，就稱為算法(algorithm)。例如，描述太極拳動(dòng)作的圖解，就是太極拳的算法。一首歌曲的樂譜，也可以稱為該歌曲的算法，因?yàn)樗付搜葑嘣摳枨拿恳粋€(gè)步驟，按照它的規(guī)定就能演奏出預(yù)定的曲子。 對(duì)同一個(gè)問題，可以有不同的解題方法和步驟。3.2.2簡(jiǎn)單算法舉例[例2.1]求1×2×3×4×5算法1： 步驟1：先求1*2，得到結(jié)果2。 步驟2：將步驟1得到的乘積2再乘以3，得到結(jié)果6。 步驟3：將6再乘以4，得24。 步驟4：將24再乘以5，得120。4.算法2：S1：使p=1S2：使i=2S3：使p*i，乘積仍放在變量p中，可表示為p*ipS4：使i的值加1，即i+1iS5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否那么，算法結(jié)束。最后得p的值就是5！的值。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：如果gi>80，那么輸出ni和gi；否那么不輸出 S3：i+1i S4：如果i50，返回S2，繼續(xù)執(zhí)行；否那么，算法結(jié)束。6.[例2.3]判定2000-2500年中的每一年是否是閏年 閏年的條件是：(1)能被4整除，但不能被100整除的年份是閏年，如1996年、2004年；(2)能被400整除的年份是閏年，如1600年、2000年。 設(shè)y為被檢測(cè)的年份。可采用以下步驟： S1：2000y S2：假設(shè)y不能被4整除，那么輸出“y不是閏年〞。然后轉(zhuǎn)到S6 S3：假設(shè)y能被4整除，不能被100整除，那么輸出“y是閏年〞。然后轉(zhuǎn)到S6 S4：假設(shè)y能被400整除，輸出“y是閏年〞，然后轉(zhuǎn)到S6 S5：輸出“y不是閏年〞 S6：y+1y S7：當(dāng)y2500時(shí)，轉(zhuǎn)S2繼續(xù)執(zhí)行，否那么算法停止。7.[例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：假設(shè)deno100返回S4；否那么算法結(jié)束。8.[例2.5]對(duì)一個(gè)大于或等于3的正整數(shù)，判斷它是不是一個(gè)素?cái)?shù) 判斷一個(gè)數(shù)n(n≥3)是否素?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é)束。9.2.3算法的特性〔1〕有窮性。一個(gè)算法應(yīng)包含有限的操作步驟，而不能是無限的。〔2〕確定性。算法中的每一個(gè)步驟都應(yīng)當(dāng)是確定的，而不應(yīng)當(dāng)是模糊的、模棱兩可的?！?〕有零個(gè)或多個(gè)輸入。所謂輸入是指在執(zhí)行算法時(shí)需要從外界取得必要的信息?！?〕有一個(gè)或多個(gè)輸出。算法的目的是為了求解，“解〞就是輸出?！?〕有效性。算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。10.2.4怎樣表示一個(gè)算法

為了表示一個(gè)算法，可以用不同的方法。 常用的方法有： 自然語言 傳統(tǒng)流程圖

N-S流程圖

偽代碼

PAD圖等。11.2.4.2用流程圖表示算法12.[例2.6]將例2.1求5!的算法用流程圖表示算法2：S1：使t=1S2：使i=2S3：使t*i，乘積仍放在變量t中，可表示為t*itS4：使i的值加1，即i+1iS5：如果i不大于5，返回重新執(zhí)行步驟S3以及其后的步驟S4和S5；否那么，算法結(jié)束。最后得t的值就是5！的值。13.[例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：1iS2：如果gi>80，那么輸出ni和gi；否那么不輸出S3：i+1iS4：如果i50，返回S2，繼續(xù)執(zhí)行；否那么，算法結(jié)束。14.[例2.8]將例2.3判定閏年的算法用流程圖表示S1：2000yS2：假設(shè)y不能被4整除，那么輸出“y不是閏年〞。然后轉(zhuǎn)到S6S3：假設(shè)y能被4整除，不能被100整除，那么輸出“y是閏年〞。然后轉(zhuǎn)到S6S4：假設(shè)y能被400整除，輸出“y是閏年〞，然后轉(zhuǎn)到S6S5：輸出“y不是閏年〞S6：y+1yS7：當(dāng)y2500時(shí)，轉(zhuǎn)S2繼續(xù)執(zhí)行，否那么算法停止。15.[例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：假設(shè)deno100返回S4；否那么算法結(jié)束。16.[例2.10]將例2.5判斷素?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é)束。17.2.4.3三種根本結(jié)構(gòu)〔1〕順序結(jié)構(gòu)18.〔2〕選擇結(jié)構(gòu)19.〔3〕循環(huán)結(jié)構(gòu)當(dāng)型循環(huán) 直到型循環(huán)20.2.4.4用N-S流程圖表示算法 N-S流程圖用以下的流程圖符號(hào)：

(1)順序結(jié)構(gòu)：A和B兩個(gè)框組成一個(gè)順序結(jié)構(gòu)。21.(2)選擇結(jié)構(gòu)：當(dāng)條件p成立時(shí)執(zhí)行操作A，條件p不成立那么執(zhí)行操作B。22.(3)循環(huán)結(jié)構(gòu)： 當(dāng)型循環(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條件成立為止。23.[例2.11]將例2.1的求5！算法用N-S圖表示24.[例2.12]將例2.2的算法用N-S圖表示。將50名學(xué)生中成績(jī)高于80分的學(xué)號(hào)和成績(jī)打印出來25.[例2.13]將例2.3判定閏年的算法用N-S圖表示

26.[例2.14]將例2.4的算法用N-S圖表示。

求1-1/2+1/3+…+1/99-1/10027.[例2.15]將例2.5判斷素?cái)?shù)的算法用N-S流程圖表示28.2.4.6用計(jì)算機(jī)語言表示算法[例2.16]將例2.11表示的算法(求5!)用C語言表示 #include<stdio.h> main() { inti,t; t=1; i=2; while(i<=5) { t=t*i; i=i+1; } printf(“%d〞,t); }29.[例2.17]求例2.14表示的算法(求級(jí)數(shù)的值)

用C語言表示#include<stdio.h>main(){ intsign=1; floatdeno=2.0,sum=1.0,term; while(deno<=100) { sign=-sign; term=sign/deno; sum=sum+term; deno=deno+1; } printf(“%f〞,sum);}30.2.5結(jié)構(gòu)化程序設(shè)計(jì)方法自頂向下逐步細(xì)化模塊化設(shè)計(jì)結(jié)構(gòu)化編碼31.習(xí)題2.4用傳統(tǒng)流程圖表示求解以下問題的算法(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.習(xí)題1有兩個(gè)瓶子A和B，分別盛放醋和醬油，要求將它們互換#include"stdafx.h"intmain(intargc,char*argv[]){ intA; intB; A=1; B=2; printf("A=%dB=%d\n",A,B); intC; C=A; A=B; B=C; printf("A=%dB=%d\n",A,B); return0;}33.習(xí)題2依次將10個(gè)數(shù)輸入，要求將其中最大的數(shù)輸出#include"stdafx.h"intmain(intargc,char*argv[]){ inta; intmax; scanf("%d",&a); max=a; for(inti=2;i<=10;i++) { scanf("%d",&a); if(a>max) { max=a; } } printf("max=%d\n",max); return0;}34.習(xí)題3有3個(gè)數(shù)a、b、c，要求按大小順序把它們輸出#include"stdafx.h"intmain(intargc,char*argv[]){ inta,b,c; inttemp; scanf("a=%db=%dc=%d",&a,&b,&c); if(a>b) { temp=a; a=b; b=temp; } if(b>c) { temp=b; b=c; c=temp; } if(a>b) { temp=a; a=b; b=temp; } printf("a=%db=%dc=%d\n",a,b,c); return0;}35.習(xí)題4求1+2+3+……+100#include"stdafx.h"intmain(intargc,char*argv[]){ intsum; sum=0; for(inti=1;i<=100;i++) { sum=sum+i; } printf("1+2+3+...+100=%d\n",sum); return0;}36.習(xí)題5判斷一個(gè)數(shù)n能否同時(shí)被3和5整除#include<stdafx.h>intmain(intargc,char*argv[]){ intn; scanf("n=%d",&n); if(n%3==0&&n%5==0) { printf("%d能夠被3和5同時(shí)整除\n",n); } else { printf("%d不能夠被3和5同時(shí)整除\n",n); } return0;}37.習(xí)題6將100-200之間的素?cái)?shù)輸出intmain(intargc,char*argv[]){ intn; 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); } } return0;}#include<stdafx.h>#include<math.h>intjudge(intn){intw;w=0;for(inti=2;i<=sqrt(n);i++){ intr; r=n%i; if(r==0) { w=1; break; }}returnw;}38.習(xí)題7求兩個(gè)數(shù)m和n的最大公約數(shù)#include<stdafx.h>intmain(intargc,char*argv[]){ intm,n