程序設(shè)計(jì)中常用思維方法ppt課件

1、迭代、歸納與循環(huán) 思想61110 )(21nnnnnsssxss要求近似值滿足TF輸入x,初始化s1x=1.0e-6 s1=s2 s2=0.5*(s1+x/s1) e=s2-s1輸出s2 分析：處理該問(wèn)題的N-S圖如右：例1：用牛頓迭代法求x的平方根。牛頓迭代公式為：迭代變量S1,s2#include #include main() float x,s1=1;s2,err; scanf(“%f,&x); if(x=1.0e-6) 2; 3; err=s2-s1; printf(“nsqrt(%f)=%fn,x,s2); 1err=s2-s1;2s1=s23s2=0.5*(s1+x/s1

2、)例2：統(tǒng)計(jì)輸入的行數(shù)、單詞的個(gè)數(shù)設(shè)單詞是一個(gè)不包含任何空白字符的字符序列以及輸入的總的字符個(gè)數(shù)。分析：1要表示輸入的行數(shù)、單詞的個(gè)數(shù)和輸入的總字符數(shù)，可設(shè)以下三個(gè)變量nl、nw、nc，初值均為0；2對(duì)于nl，每輸入一個(gè)n增1，對(duì)于nc，每輸入一個(gè)字符，增1，而對(duì)于nw，只需當(dāng)輸入的字符為非空白字符、非回車且前一個(gè)字符為空或回車時(shí)才增1；3設(shè)計(jì)變量inword，當(dāng)其值0時(shí)，表示當(dāng)前字符的前一字符為空白或回車，當(dāng)其值為1時(shí)，表示當(dāng)前字符的前一字符非空或回車，此當(dāng)前字符仍為該單詞中的內(nèi)容；4inword的初始值為0；5故nw增1的條件是：當(dāng)前字符非空白或回車且inword=0;#define YE

3、S 1；#define NO 0；#include main() int c, nl, nw, nc, inword; inword=NO; nl=nw=nc=0;while (c=getchar()!=#) + nc; if (c=n) +nl; if (c= = |c= =n | c= =t) inword=NO； else if (inword= =NO) inword=YES; +nw； printf(“nl=%d nw=%d nc=%dn,nl,nw,nc);歸納法與循環(huán)1歸納法，是從大量的特殊性中總結(jié)出規(guī)律性或普通性的結(jié)論。2歸納，在程序設(shè)計(jì)上主要表現(xiàn)為遞歸和迭代。我們經(jīng)常用遞歸和

4、迭代的方式把一個(gè)復(fù)雜的計(jì)算過(guò)程化為簡(jiǎn)單過(guò)程的多次反復(fù)，這種反復(fù)很容易用循環(huán)來(lái)實(shí)現(xiàn)；3歸納法的另一重要用途是用于數(shù)列和級(jí)數(shù)求和；例3：猴子第一天摘下假設(shè)干桃子，當(dāng)即吃了一半，還不過(guò)癮，又多吃了一個(gè)。第二天早上又將剩下的桃子吃掉了一半，又多吃了一個(gè)，以后每天早上都吃了前一天剩下的一半零一個(gè)。到第10天早上再想吃時(shí)，發(fā)現(xiàn)只剩下一個(gè)桃子了。求第一天共摘多少個(gè)桃子。n Sn=(Sn+1+1)*2n程序如下：nmain()n int s, i;n s=1;n for (i=1;i=9;i+)n ？; n printf(“s=%dn,s);n例4：有一張足夠大的紙，厚0.09毫米，問(wèn)將它對(duì)折多少次后可以到達(dá)

5、珠穆朗瑪峰的高度8848米？分析：1采用歸納法；2設(shè)a為高度，初值為910 -5米；3對(duì)折后，高度為前一次高度的2倍，每次乘2后判別乘積能否已超越8848米。假設(shè)已超越，那么記下乘2的次數(shù)就是對(duì)折的次數(shù)；4請(qǐng)讀者本人編程；*枚舉法：就是逐一列舉出能夠解的各個(gè)元素，并加以判別，直到求得所需求的解。常用在陳列、組合、數(shù)據(jù)分類、信息檢索、多解方程的求解上；枚舉法與循環(huán)思想運(yùn)用枚舉法，必需掌握兩條原那么： 確定搜索的范圍這個(gè)范圍必需是有限的； 選擇枚舉的戰(zhàn)略按照一條什么樣的途徑來(lái)逐一枚舉；這兩條原那么運(yùn)用得好壞，對(duì)程序的任務(wù)量有宏大的影響。例5：對(duì)于-5x11；-10y9；-6z18，求方程：x3+y

6、3+z3=3的全部整數(shù)解。程序如下：#include main() int x, y, z; for(x= -5; x12; x+) for(y=-10; y10; y+) for(z=-6; z19; z+) if (？) printf(“%5d，%5d，%5dn,x,y,z);x*x*x+y*y*y+z*z*z= =3例6：百錢百雞問(wèn)題。用100元錢買100只雞，每只公雞5元，每只母雞3元，每3只小雞1元，要求每種雞至少買一只，且必需是整只的，問(wèn)各種雞各買多少只？分析：1這是一個(gè)組合問(wèn)題，歸根究竟是求三元一次方程的一組解；2設(shè) i，j，k分別表示公雞、母雞和小雞的只數(shù)。為了確定i，j，k的

7、取值范圍，可以有不同方法。不同的方法，程序的計(jì)算量相差甚遠(yuǎn)；3方法一：i ：1 20；j：1 33；k：1100；4方法二：i ：1 18；j：1 31；k：100ij；5方法三：由i +j+k=100及5i +3j+k/3=100得14i+8j=200，由此可得： i ：1 13；j：1 23；k=100ij；6方法四：由方法三中的14i+8j=200得7i+4j=100可得： i ：1 13；j=100 7 i)/4；k=100ij；main() int i,j,k; for(i=1;i=20;i+) for(j=1;j=33;j+) k:=100-i-j; if(？) printf(“k

8、=%d,j+%d,i=%dn,k,j,i); i*5+j*3+k/3=100例7：求整數(shù)a和b的最小公倍數(shù)。分析：1假設(shè) i 是a 和b的最小公倍數(shù)，那么 i 必能被 a 和 b 整除，同時(shí) i 必需是自然數(shù)，所以其取值范圍是；2方法一：i 從1開場(chǎng)，依次添加，直到第一個(gè)能被a和b整除為止，這個(gè) i 就是a和b的最小公倍數(shù)；3方法二：令從i 從a開場(chǎng)，并使 i 每次添加a而不是添加1，這就保證了 i 總是a的倍數(shù)。故每次只需判別 i 能否被b整除就可以了。一旦判別成立，i 就是a和b的最小公倍數(shù)；程序一：#include main( ) int a,b, i; scanf(“%d%d,&

9、;a,&b); i=0; while(1) i+; if (i%a= =0) if (i%b= =0)printf(“%dn, i); break; 程序二：#include main( ) int a,b, i; scanf(“%d%d,&a,&b); i=0; while(1) i+=a; if (i%b= =0) printf(“%dn, i); break; 例8：用循環(huán)語(yǔ)句打印以下圖案：*程序如下：main( ) int i , j; for (i=1; i=6; i+) for (j=1; j=20-i ; j+) printf(“ ); for (j=1;

10、 j=2*i-1;j+) printf(“*); printf(“n); 例：用循環(huán)語(yǔ)句打印以下圖案：*分析：1將該圖案分成上下兩部分處置；2定行、定行中的字符個(gè)數(shù)、定每行打印的起始位置。幾種循環(huán)的比較nP.114 自學(xué)寫出以下程序運(yùn)轉(zhuǎn)結(jié)果y);x,n%dy%d,xprintf(7);(i while;iy y ;ii;xx 0)(i%2! if i; do0;yxiy;x,i, int()mainx=1,y=12 );#printf( :2 case break;i);,n*dprintf(*% :1 case 0; case (i/j) switch )ij;*2ij;(ifor 4;ji,int ()main完善程序*