程序设计中常用思维方法(循环).ppt

Monday, May 13, 2019,扬州大学信息学院,迭代、归纳与循环 思维,Monday, May 13, 2019,扬州大学信息学院,分析： 解决该问题的N-S图如右：,例1：用牛顿迭代法求x的平方根。牛顿迭代公式为：,迭代变量 S1,s2,Monday, May 13, 2019,扬州大学信息学院,#include #include main() float x,s1=1;s2,err; scanf(“%f”, ,（1）err=s2-s1;,（2）s1=s2,（3）s2=0.5*(s1+x/s1),Monday, May 13, 2019,扬州大学信息学院,例2：统计输入的行数、单词的个数（设单词是一个不包含任何空白字符的字符序列）以及输入的总的字符个数。,分析： （1）要表示输入的行数、单词的个数和输入的总字符数，可设以下三个变量nl、nw、nc，初值均为0； （2）对于nl，每输入一个n增1，对于nc，每输入一个字符，增1，而对于nw，只有当输入的字符为非空白字符、非回车且前一个字符为空或回车时才增1； （3）设计变量inword，当其值0时，表示当前字符的前一字符为空白或回车，当其值为1时，表示当前字符的前一字符非空或回车，此当前字符仍为该单词中的内容； （4）inword的初始值为0； （5）故nw增1的条件是：当前字符非空白或回车且inword=0;,Monday, May 13, 2019,扬州大学信息学院,#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); ,Monday, May 13, 2019,扬州大学信息学院,归纳法与循环,（1）归纳法，是从大量的特殊性中总结出规律性或一般性的结论。 （2）归纳，在程序设计上主要表现为递归和迭代。我们常常用递归和迭代的方式把一个复杂的计算过程化为简单过程的多次重复，这种重复很容易用循环来实现； （3）归纳法的另一重要用途是用于数列和级数求和；,Monday, May 13, 2019,扬州大学信息学院,例3：猴子第一天摘下若干桃子，当即吃了一半，还不过瘾，又多吃了一个。第二天早上又将剩下的桃子吃掉了一半，又多吃了一个，以后每天早上都吃了前一天剩下的一半零一个。到第10天早上再想吃时，发现只剩下一个桃子了。求第一天共摘多少个桃子。,Monday, May 13, 2019,扬州大学信息学院,Sn=(Sn+1+1)*2 程序如下： main() int s, i; s=1; for (i=1;i=9;i+) ？; printf(“s=%dn”,s); ,Monday, May 13, 2019,扬州大学信息学院,例4：有一张足够大的纸，厚0.09毫米，问将它对折多少次后可以达到珠穆朗玛峰的高度（8848米）？,Monday, May 13, 2019,扬州大学信息学院,分析： （1）采用归纳法； （2）设a为高度，初值为910 -5米； （3）对折后，高度为前一次高度的2倍，每次乘2后判断乘积是否已超过8848米。若已超过，则记下乘2的次数就是对折的次数； （4）请读者自己编程；,Monday, May 13, 2019,扬州大学信息学院,*枚举法： 就是逐一列举出可能解的各个元素，并加以判断，直到求得所需要的解。 常用在排列、组合、数据分类、信息检索、多解方程的求解上；,枚举法与循环 思维,Monday, May 13, 2019,扬州大学信息学院,使用枚举法，必须掌握两条原则： 确定搜索的范围（这个范围必须是有限的）； 选择枚举的策略（按照一条什么样的路径来逐一枚举）； 这两条原则使用得好坏，对程序的工作量有巨大的影响。,Monday, May 13, 2019,扬州大学信息学院,例5：对于-5x11；-10y9；-6z18，求方程：x3+y3+z3=3的全部整数解。,Monday, May 13, 2019,扬州大学信息学院,程序如下： #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,Monday, May 13, 2019,扬州大学信息学院,例6：百钱百鸡问题。用100元钱买100只鸡，每只公鸡5元，每只母鸡3元，每3只小鸡1元，要求每种鸡至少买一只，且必须是整只的，问各种鸡各买多少只？,Monday, May 13, 2019,扬州大学信息学院,分析： （1）这是一个组合问题，归根到底是求三元一次方程的一组解； （2）设 i，j，k分别表示公鸡、母鸡和小鸡的只数。为了确定i，j，k的取值范围，可以有不同方法。不同的方法，程序的计算量相差甚远； （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；,Monday, May 13, 2019,扬州大学信息学院,main() int i,j,k; for(i=1;i=20;i+) 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,Monday, May 13, 2019,扬州大学信息学院,例7：求整数a和b的最小公倍数。,Monday, May 13, 2019,扬州大学信息学院,分析： （1）如果 i 是a 和b的最小公倍数，则 i 必能被 a 和 b 整除，同时 i 必须是自然数，所以其取值范围是； （2）方法一：i 从1开始，依次增加，直到第一个能被a和b整除为止，这个 i 就是a和b的最小公倍数； （3）方法二：令从i 从a开始，并使 i 每次增加a而不是增加1，这就保证了 i 总是a的倍数。故每次只要判断 i 能否被b整除就可以了。一旦判断成立，i 就是a和b的最小公倍数；,Monday, May 13, 2019,扬州大学信息学院,程序一： #include main( ) int a,b, i; scanf(“%d%d”, ,Monday, May 13, 2019,扬州大学信息学院,程序二： #include main( ) int a,b, i; scanf(“%d%d”, ,Monday, May 13, 2019,扬州大学信息学院,例8：用循环语句打印下列图案： * * * * * *,Monday, May 13, 2019,扬州大学信息学院,程序如下： main( ) int i , j; for (i=1; i=6; i+) for (j=1; j=20-i ; j+) printf(“ ”); for (j=1; j=2*i-1;j+) printf(“*”); printf(“n”); ,Monday, May 13, 2019,扬州大学信息学院,例：用循环语句打印下列图案： * * * * * * *,Monday, May 13, 2019,扬州大学信息学院,分析： （1）将该图案分成上下两部分处理； （2）定行、定行中的字符个数、定每行打印的起始位置。,Monday, May 13, 2019,扬州大学信息学院,几种循环的比较,P.114 自