第七讲-循环结构经典算法之一课件.ppt

1、第七讲第七讲 循环结构的经典算法之一循环结构的经典算法之一 程序设计举例程序设计举例 教 学目 的：1、灵活运用循环语句 2、编写一些基本算法程序 教学重点和难点：重点：判断素数，求最大公约数、最小公倍数，几何图形的输出，数列的部分和。难点：循环的嵌套 程序设计举例 一.循环语句的选择 while语句、do-while语句用于条件循环,for语句用于计数循环。while语句、for语句是先判断循环条件,后执行循环体,如果循环的条件一开始就不成立,循环一次都不执行。do-while语句是先执行循环体,后判断循环条件,循环至少执行一次。知道循环的次数选用for语句实现循环;不知道循环的次数选用wh

2、ile语句、do-while语句实现循环;保证循环至少执行一次,选用do-while语句实现循环。(1)while语句的for语句形式:for（;条件表达式;）语句(2)do-while语句for语句形式:语句 for（;条件表达式;）语句(3)for语句的while语句形式:表达式1;while（条件表达式2）语句 表达式3;程序设计举例 二.循环条件的设计 从循环条件与退出循环的条件正反两方面加以综合考虑。有些问题循环条件是隐含的,甚至需要人为地去构造。通常将一些非处理范围的数据,一般是一些特殊的数据作为循环条件构造的基础,这样构造的条件称为“伪条件”。如求一些数的和是一个累加问题,需要循

3、环完成,但循环条件并没给出。我们可用一个很小的数，比如-1E20,或一个很大的数,比如1E20,来构造循环条件:数大于-1E20或数小于1E20,只要处理的一些数不比-1E20小或比1E20大。注意：循环体外的语句不要放至循环体中,循环体中的语句不要放至循环体外。程序设计举例 5.9 循环应用举例【例【例1】编程显示如下几何图形：】编程显示如下几何图形：请编程输出如下的空心图形，要求用循环结构实现。请编程输出如下的空心图形，要求用循环结构实现。上部：共6行，每行共11个字符。其中，第一行：第11位为“*”号，其余为空格 第二行：第9位和第11位为“*”号，其余为空格 第三行：第7位和第11位为

4、“*”号，其余为空格 第四行：第5位和第11位为“*”号，其余为空格 第五行：第3位和第11位为“*”号，其余为空格 第六行：第1位和第11位为“*”号，其余为空格下部：共5行，每行共11个字符。其中，第一行：第3位和第11位为“*”号，其余为空格 第二行：第5位和第11位为“*”号，其余为空格 第三行：第7位和第11位为“*”号，其余为空格 第四行：第9位和第11位为“*”号，其余为空格 第五行：第11位为“*”号，其余为空格 For(i=11;i=1;i=i-2)For(j=1;j=11;j+)if(j=i|j=11)printf(“*”);else printf(“);For(i=3;i

5、=11;i=i+2)5.9 循环应用举例【例【例1】编程，显示几何图形。】编程，显示几何图形。#include main()int i,j;for(i=11;i=1;i=i-2)/*显示上部图形*/printf(n);for(j=1;j=11;j+)if(j=i|j=11)printf(*);else printf();for(i=3;i=11;i=i+2)/*显示下部图形*/printf(n);for(j=1;j=11;j+)if(j=i|j=11)printf(*);else printf();printf(n);【例2】判断m是否为素数。所谓素数，是指大于1的整数，并且除了1和它本身之外

6、不能被任何整数所整除。【算法】用2，3，4，5m-1逐个去除m，若m被其中一个整数，则m不是素数，否则m是素数。算法优化：当m较大时，除的次数会很多，很费时。（1）可以用2，3，小于或等于m/2的整数去除，若均不能整除，则m是素数；（2）也可以用2，3，小于或等于 的整数去除,若均不能整除，则m是素数。5.9 循环应用举例m【例2】判断m是否为素数。【参考例5-20】（P96）5.9 循环应用举例#include#includemain()int m,i;double k;scanf(%d,&m);k=sqrt(m);for(i=2;i k)printf(“%d 是一个素数！n,m);else

7、printf(“%d 不是一个素数！n,m);相当于For(i=2;i=k;i+)if(m%i=0)break;5.9 循环应用举例【例3】编写程序,计算出2000到9000之间所有能同时被 3、5和7整除的整数的平方根的和，保留3位小数。#include#include main()int i;double sum=0;for(i=2000;i=9000;i+)if(i%3=0&i%5=0&i%7=0)sum+=sqrt(i);printf(%.3f,sum);5.9 循环应用举例与例与例2、3同类的采用同类的采用穷举法穷举法进行验证的题目有：进行验证的题目有：u编程输出编程输出3300之间

8、的素数。之间的素数。u三色球问题三色球问题:袋中有袋中有12个球，其中红、白、黑分别为个球，其中红、白、黑分别为3、3、6个。问从中任取个。问从中任取8个球，共有多少种不同的取法。个球，共有多少种不同的取法。u输出输出“水仙花数水仙花数”：三位整数：三位整数abc并满足并满足a3+b3+c3=abc。例。例:407=43+03+73。u编程输出编程输出1010500500之间的同构数。之间的同构数。u百鸡问题。百鸡问题。u显示显示500600500600之间同时被之间同时被5 5和和7 7整除的数。整除的数。5.9 循环应用举例【例4】求两个整数m和n的最小公倍数，最大公约数。所谓两个整数的最

9、小公倍数，是指能够被两个整数同时整除的最小整数。所谓两个整数的最大公约数，是指能够整除这两个数的最大整数。可采用穷举法：求m与n的最小公倍数：for(i=n;i+)if(m%i=0&n%i=0)break;printf(“最小公倍数是：%i”,i);求m与n的最大公约数：for(i=n;i-)if(i%m=0&i%n=0)break;printf(“最大公约数是：%i”,i);5.9 循环应用举例【例4】求两个整数m和n的最小公倍数，最大公约数。展转相除法：先用m除以n求得余数r，当r0时，再用除数做被除数、余数做除数再求余数，如此反复，直至r0，除数即为所求的最大公约数。p(=m*n)除以最

10、大公约数即为m和n的最小公倍数R0=m,R1=n,R 2,R3,Rn=Rn-2/Rn-1,.while(1)r=m%n;if(r!=0)m=n;n=r;else break;/*这时n中即为最大公约数*/while(n!=0)r=m%n;m=n;n=r;/*这时m中即为最大公约数*/5.9 循环应用举例/*求m,n的最大公约数与最小公倍数*/#includemain()int p,r,n,m;printf(请输入两个正整数:n);scanf(%d,%d,&n,&m);p=n*m;while(n!=0)r=m%n;m=n;n=r;/最大公约数在m中 printf(最大公约数是%dn最小公倍数是%

11、dn,m,p/m);【例4】求整数m和n的最小公倍数，最大公约数。5.9 循环应用举例【例【例5】Fibonacci（斐波纳契数列）的计算方法（斐波纳契数列）的计算方法问题原型：从前有一对长寿兔子，从出生后第问题原型：从前有一对长寿兔子，从出生后第3个月起每个月都生一对兔子。个月起每个月都生一对兔子。新生的小兔子长到第新生的小兔子长到第3个月后每个月又都生一对兔子，这样一代一代生下去，个月后每个月又都生一对兔子，这样一代一代生下去，假设所有兔子都不死，求兔子增长数量的数列（即每个月的兔子总对数）。假设所有兔子都不死，求兔子增长数量的数列（即每个月的兔子总对数）。第几个第几个月月小兔子小兔子对数

12、对数中兔子中兔子对数对数老兔子老兔子对数对数兔子总兔子总对数对数00000110012010131012411135212563238Fibonacci（斐波纳契数列）定义：a0=0a1=1a2=a0+a1=1a3=a1+a2=2a4=a2+a3=3a5=a3+a4=5an=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),#in

13、clude main()float s=0,j,n;for(n=1;n+)j=1/(n*(n+1)*(n+2);s=s+j;if(s0.235)break;printf(%.3f,s);1)2)(1(1nnnns#include main()float s=0,n;for(n=1;s0.235;n+)s=s+1/(n*(n+1)*(n+2);printf(%.3f,s);简化5.9 循环应用举例【例7】编写程序,计算并输出下面数列前n项的和(设n=20,x=0.5),要求结果保留3位小数。sin(x)/x,sin(2x)/2x,sin(3x)/3x,sin(n*x)/(n*x),（其中,sin

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

15、t sign=1;double sum=1,j=1,i;for(i=2;i=20;i+)sign=sign*(-1);j=sign*1/(2*i-1);if(fabs(j)0.001)break;sum=sum+j;printf(%.3f,sum);1112)1(nnnsum5.9 循环应用举例与例与例6、7、8类似的问题有：类似的问题有：求数列求数列1/2,2/3,3/4,4/5,.前前20项的和。项的和。求求1!+2!+3!+10!的值。的值。求求1X2X3+3X4X5+99X100X101的值。的值。课堂小结课堂小结1、循环实现几何图形的输出、循环实现几何图形的输出;2、常用算法的思想如：判断素数，求最大公约数、最小公倍数。、常用算法的思想如：判断素数，求最大公约数、最小公倍数。3、会求数列的部分和；、会求数列的部分和；4、注意循环嵌套的层次。注意循环嵌套的层次。