与循环结构相关的经典算法之一

1、循环结构的经典算法之一循环结构的经典算法之一 程序设计举例程序设计举例 教教 学目学目 的的 ： 1、灵活运用循环语句、灵活运用循环语句 2、编写一些基本算法程序、编写一些基本算法程序 教学重点和难点：教学重点和难点：重点：判断素数，求最大公约数、最小公倍数，重点：判断素数，求最大公约数、最小公倍数， 几何图形的输出，数列的部分和。几何图形的输出，数列的部分和。难点：循环的嵌套难点：循环的嵌套 程序设计举例程序设计举例 一一. 循环语句的选择循环语句的选择 while语句、语句、do-while语句用于条件循环语句用于条件循环, for语句用于计数语句用于计数循环。循环。while语句、语句、

2、for语句是先判断循环条件语句是先判断循环条件, 后执行循环体后执行循环体, 如如果循环的条件一开始就不成立果循环的条件一开始就不成立, 循环一次都不执行。循环一次都不执行。do -while语语句是先执行循环体句是先执行循环体, 后判断循环条件后判断循环条件, 循环至少执行一次。循环至少执行一次。 知道循环的次数选用知道循环的次数选用for语句实现循环语句实现循环; 不知道循环的次数不知道循环的次数选用选用while语句、语句、do-while语句语句实现循环实现循环; 保证循环至少执行一次保证循环至少执行一次, 选用选用do-while语句实现循环。语句实现循环。 (1) while语句的

3、语句的for语句形式语句形式: for（; 条件表达式条件表达式; ）语句）语句(2) do-while语句语句for语句形式语句形式: 语句语句 for（; 条件表达式条件表达式; ）语句）语句(3) for语句的语句的while语句形式语句形式: 表达式表达式1; while（条件表达式（条件表达式2） 语句语句 表达式表达式3; 程序设计举例程序设计举例 for语句更简单、灵活语句更简单、灵活二二. 循环条件的设计循环条件的设计 从从循环条件循环条件与与退出循环退出循环的条件正反两方面加以综合考虑。的条件正反两方面加以综合考虑。有些问题循环条件是隐含的有些问题循环条件是隐含的, 甚至需要

4、人为地去构造。甚至需要人为地去构造。 通常将通常将一些非处理范围的数据一些非处理范围的数据, 一般是一些特殊的数据作为循环条件一般是一些特殊的数据作为循环条件构造的基础构造的基础, 这样构造的条件称为这样构造的条件称为“伪条件伪条件”。 例如：求一些数的和是一个累加问题例如：求一些数的和是一个累加问题, 需要循环完成需要循环完成, 但循但循环条件并没给出。我们可用一个很小的数，比如环条件并没给出。我们可用一个很小的数，比如-1E20, 或一或一个很大的数个很大的数, 比如比如1E20, 来构造来构造循环条件循环条件: 数大于数大于-1E20或数小或数小于于1E20。注意：注意：循环体外的语句不

5、要放至循环体中循环体外的语句不要放至循环体中, 循环体中的语句不循环体中的语句不要放至循环体外。要放至循环体外。 程序设计举例程序设计举例 5.9 循环应用举例【例【例1】、】、 几何图形的输出：几何图形的输出： 请编程输出如下的空心图形，请编程输出如下的空心图形， 要求用循环结构实现。要求用循环结构实现。#include main( ) int i,j; for(i=0;i=5;i+) /*前前6行行*/printf(n); for(j=0;j=10;j+) if( j=10-2*i |j=10) printf(*); else printf( ); for(i=0;i=4;i+) /*后后

6、5行行*/printf(n); for(j=0;j=10;j+) if( j=2*(i+1) | j=10) printf(*); else printf( ); printf(n);竖列竖列11个个*共共11行，行，11列列i：控制行；：控制行；j：控制列；：控制列；【例【例2】判断】判断m是否为素数。是否为素数。 素数是指大于素数是指大于1的整数，并且除了的整数，并且除了1和它本身和它本身m之外，之外， 不能被不能被2(m-1)之间的任何整数所整除。之间的任何整数所整除。 【算法一【算法一】用用2，3，4，5m-1逐个去除逐个去除m，若，若m被其中一个数除尽，被其中一个数除尽， 则则m不是

7、素数，否则不是素数，否则m是素数。是素数。5.9 循环应用举例m#includemain() int i,m; scanf(%d,&m); for(i=2;m%i;i+); if(i=m)printf(%d is a prime numbern,m); elseprintf(%d is not a prime numbern,m);【例【例2】判断】判断m是否为素数。是否为素数。【算法二【算法二】当当m较大时，除的次数会很多，较大时，除的次数会很多，可以用可以用2，3，m/2去除，也可以用去除，也可以用2，3， 去除去除,若除不尽，则若除不尽，则m是素数。是素数。（教材上的算法）（教材

8、上的算法）5.9 循环应用举例m#include#includemain() int m,i, k; scanf(%d,&m); k=sqrt(m); for(i=2;ik)printf(%d is a prime numbern,m); elseprintf(%d is not a prime numbern,m);sqrt(m):平方根后的值是平方根后的值是double型，型， 这里会先转这里会先转换为换为int型，再赋值给型，再赋值给k注意：此注意：此for语句的语句的循环体为循环体为空语句。空语句。思考：运算符的优先级思考：运算符的优先级#includemain() int p

9、,r, m, n,temp; printf (请输入两个正整数请输入两个正整数:n); scanf (%d,%d,&m,&n); if(mn) temp=m; m=n; n=temp; p=m*n; r=m%n; while(r!=0) m=n; n=r; r=m%n; printf(最大公约数是最大公约数是%dn最小公倍数是最小公倍数是%dn,n,p/n); 5.9 循环应用举例【例【例3】求最大公约数，求最大公约数，最小公倍数。最小公倍数。最小公倍数最小公倍数=两原数乘积两原数乘积除以除以最大公约数最大公约数 用用辗转相除法辗转相除法求最大公约数：求最大公约数：m:存放被除

10、数；存放被除数；n：存放除数；：存放除数；r：存放余数，：存放余数，r！=0时，用除时，用除数做被除数，用余数做除数再数做被除数，用余数做除数再求余数，如此反复，直到求余数，如此反复，直到r=0.除数除数n即为最大公约数。即为最大公约数。使使m是两个数中是两个数中最大的数最大的数求最大公约数，并赋值给求最大公约数，并赋值给n求最小公倍数是求最小公倍数是p/n5.9 循环应用举例【例【例4】 Fibonacci（斐波纳契数列）的计算方法（斐波纳契数列）的计算方法问题原型：从前有一对长寿兔子，兔子在出生两个月后，就有繁殖能力，从出生后第问题原型：从前有一对长寿兔子，兔子在出生两个月后，就有繁殖能力

11、，从出生后第3个月每个月都生一对兔子。新生的小兔子长到第个月每个月都生一对兔子。新生的小兔子长到第3个月每个月又都生一对兔子，这样个月每个月又都生一对兔子，这样一代一代生下去，假设所有兔子都不死，求兔子增长数量的数列（即每个月的兔子一代一代生下去，假设所有兔子都不死，求兔子增长数量的数列（即每个月的兔子总对数）。总对数）。第几个月第几个月小兔子对数小兔子对数中兔子对数中兔子对数老兔子对数老兔子对数兔子总对数兔子总对数00000110012010131012411135212563238Fibonacci（斐波纳契数列）定义：（斐波纳契数列）定义：a0=0a1=1a2=a0+a1=1a3=a1+

12、a2=2a4=a2+a3=3an=an-2+an-15.9 循环应用举例#include main() int a0,a1,a2,k; a0=0; a1=1; printf(%6d%6d,a0,a1); for(k=2;k0.235时求和终止并输出时求和终止并输出S。结果取。结果取3位小数。位小数。 1/(1*2*3),1/(2*3*4),1/(3*4*5),1/(n*(n+1)*(n+2),#include main() double s=0,j,n; for(n=1;n+) j=1/(n*(n+1)*(n+2); s=s+j; if(s0.235) break; printf(%.3lf,

13、s); 5.9 循环应用举例【例【例5-12】#includemain() float s,t; int n;s=1.0;for(n=1;n=19;n+)t=1.0/(n*(n+1);s+=t;if(t1e-2)break;printf(n=%d,t=%f,sum=%fn,n,t,s);注意：注意：“组建组建”时该行时该行会会 有一个警告！有一个警告！请思考：为什么？请思考：为什么？5.9 循环应用举例【例【例6】编写程序】编写程序,计算并输出下面数列前计算并输出下面数列前n项的和项的和(设设n=20,x=0.5),要求结要求结果保留果保留3位小数。位小数。 sin(x)/x,sin(2x)/

14、2x,sin(3x)/3x, ,sin(n*x)/(n*x) ,（其中（其中,sin(x)为正弦函数）为正弦函数）#include #include main()int n; double sum=0,x=0.5, j; for(n=1;n=20;n+) j=sin(n*x)/(n*x); sum=sum+j; printf(%.3fn,sum); 5.9 循环应用举例【例【例7】编写程序】编写程序,计算并输出下列数列的和计算并输出下列数列的和,当某项当某项(即即(-1)(n-1)/(2*n-1),该该项不参与求和项不参与求和)的绝对值小于的绝对值小于0.001时求和终止并输出计算结果时求和终

15、止并输出计算结果,要求结果保要求结果保留留3位小数。位小数。 1,-1/3,1/5,-1/7,1/9,(-1)(n-1)/(2*n-1) (其中其中, 表示幂运算表示幂运算)#include #include main() int sign=1; /*符号位符号位*/ double sum=1,j=1,i; for(i=2;i+) sign=sign*(-1); j=sign*1/(2*i-1); if(fabs(j)0.001) break; sum=sum+j; printf(%.3f,sum); 5.9 循环应用举例【例【例8】编写程序】编写程序,计算出计算出2000到到9000之间所有能同时被之间所有能同时被 3、5和和7整除的整数的平方根的和，保留整除的整数的平方根的和，保留3位小数。位小数。#include #include main() int