程序設(shè)計(jì)中常用思維方法(循環(huán))課件

1、迭代、歸納與循環(huán) 思維61110 )(21nnnnnsssxss要求近似值滿足TF輸入x,初始化s1x=1.0e-6 s1=s2 s2=0.5*(s1+x/s1) e=s2-s1輸出s2 分析：解決該問題的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); （1）err=s2-s1;（2）s1=s2（3）s2=

2、0.5*(s1+x/s1)例2：統(tǒng)計(jì)輸入的行數(shù)、單詞的個(gè)數(shù)（設(shè)單詞是一個(gè)不包含任何空白字符的字符序列）以及輸入的總的字符個(gè)數(shù)。分析：（1）要表示輸入的行數(shù)、單詞的個(gè)數(shù)和輸入的總字符數(shù)，可設(shè)以下三個(gè)變量nl、nw、nc，初值均為0；（2）對于nl，每輸入一個(gè)n增1，對于nc，每輸入一個(gè)字符，增1，而對于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)容；（4）inword的初始值為0；（5）故nw增1的條件是：當(dāng)前字符非空

3、白或回車且inword=0;#define YES 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

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

5、厚0.09毫米，問將它對折多少次后可以達(dá)到珠穆朗瑪峰的高度（8848米）？分析：（1）采用歸納法；（2）設(shè)a為高度，初值為910 -5米；（3）對折后，高度為前一次高度的2倍，每次乘2后判斷乘積是否已超過8848米。若已超過，則記下乘2的次數(shù)就是對折的次數(shù)；（4）請讀者自己編程；*枚舉法：就是逐一列舉出可能解的各個(gè)元素，并加以判斷，直到求得所需要的解。常用在排列、組合、數(shù)據(jù)分類、信息檢索、多解方程的求解上；枚舉法與循環(huán)思維使用枚舉法，必須掌握兩條原則： 確定搜索的范圍（這個(gè)范圍必須是有限的）； 選擇枚舉的策略（按照一條什么樣的路徑來逐一枚舉）；這兩條原則使用得好壞，對程序的工作量有巨大的影響。

6、例5：對于-5x11；-10y9；-6z18，求方程：x3+y3+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：百錢百雞問題。用100元錢買100只雞，每只公雞5元，每只母雞3元，每3只小雞1元，要求每種雞至少買一只，且必須是整只的，問各種雞各買多少只？分析：（1）這是一個(gè)組合問題，歸根到底是求三元一次方程的一組解；

7、（2）設(shè) i，j，k分別表示公雞、母雞和小雞的只數(shù)。為了確定i，j，k的取值范圍，可以有不同方法。不同的方法，程序的計(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+)

8、 for(j=1;j=33;j+) k:=100-i-j; if(？) printf(“k=%d,j+%d,i=%dn”,k,j,i); i*5+j*3+k/3=100例7：求整數(shù)a和b的最小公倍數(shù)。分析：（1）如果 i 是a 和b的最小公倍數(shù)，則 i 必能被 a 和 b 整除，同時(shí) i 必須是自然數(shù)，所以其取值范圍是；（2）方法一：i 從1開始，依次增加，直到第一個(gè)能被a和b整除為止，這個(gè) i 就是a和b的最小公倍數(shù)；（3）方法二：令從i 從a開始，并使 i 每次增加a而不是增加1，這就保證了 i 總是a的倍數(shù)。故每次只要判斷 i 能否被b整除就可以了。一旦判斷成立，i 就是a和b的最小公倍

9、數(shù)；程序一：#include main( ) int a,b, i; scanf(“%d%d”,&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)語句打印下列圖案：*程序如下：main( ) int i , j; for (i=1

10、; i=6; i+) for (j=1; j=20-i ; j+) printf(“ ”); for (j=1; j=2*i-1;j+) printf(“*”); printf(“n”); 例：用循環(huán)語句打印下列圖案：*分析：（1）將該圖案分成上下兩部分處理；（2）定行、定行中的字符個(gè)數(shù)、定每行打印的起始位置。幾種循環(huán)的比較nP.114 自學(xué)寫出下列程序運(yù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完善