《第七讲+循环结构的经典算法之一》由会员分享，可在线阅读，更多相关《第七讲+循环结构的经典算法之一（22页珍藏版）》请在金锄头文库上搜索。
1、第七讲第七讲 循环结构的经典算法之一循环结构的经典算法之一 程序设计举例程序设计举例 教教学目学目的的：1、灵活运用循环语句、灵活运用循环语句2、编写一些根本算法程序、编写一些根本算法程序教学重点和难点：教学重点和难点：重点：判断素数，求最大公约数、最小公倍数，重点：判断素数，求最大公约数、最小公倍数，几何图形的输出，数列的局部和。几何图形的输出，数列的局部和。难点：循环的嵌套难点：循环的嵌套 程序设计举例程序设计举例 一一. 循环语句的选择循环语句的选择 while语语句句、do-while语语句句用用于于条条件件循循环环, for语语句句用用于于计计数数循循环环。while语语句句、for
2、语语句句是是先先判判断断循循环环条条件件, 后后执执行行循循环环体体, 如如果果循循环环的的条条件件一一开开始始就就不不成成立立, 循循环环一一次次都都不不执执行行。do -while语语句句是是先先执执行行循循环环体体, 后后判判断断循循环环条条件件, 循循环环至至少少执执行行一一次次。 知知道道循循环环的的次次数数选选用用for语语句句实实现现循循环环; 不不知知道道循循环环的的次次数数选选用用while语语句句、do-while语语句句实实现现循循环环; 保保证证循循环环至至少少执执行行一一次次, 选用选用do-while语句实现循环。语句实现循环。 (1) while语句的语句的for
3、语句形式语句形式: for; 条件表达式条件表达式; 语句语句(2) do-while语句语句for语句形式语句形式: 语句语句 for; 条件表达式条件表达式; 语句语句(3) for语句的语句的while语句形式语句形式: 表达式表达式1; while条件表达式条件表达式2 语句语句 表达式表达式3; 程序设计举例程序设计举例 二二. 循环条件的设计循环条件的设计 从从循循环环条条件件与与退退出出循循环环的的条条件件正正反反两两方方面面加加以以综综合合考考虑虑。有有些些问问题题循循环环条条件件是是隐隐含含的的, 甚甚至至需需要要人人为为地地去去构构造造。 通通常常将将一一些些非非处处理理范
4、范围围的的数数据据, 一一般般是是一一些些特特殊殊的的数数据据作作为为循循环环条条件构造的根底件构造的根底, 这样构造的条件称为这样构造的条件称为“伪条件。伪条件。 如如求求一一些些数数的的和和是是一一个个累累加加问问题题, 需需要要循循环环完完成成, 但但循循环环条条件件并并没没给给出出。我我们们可可用用一一个个很很小小的的数数，比比方方-1E20, 或或一一个个很很大大的的数数, 比比方方1E20, 来来构构造造循循环环条条件件: 数数大大于于-1E20或或数数小小于于1E20, 只要处理的一些数不比只要处理的一些数不比-1E20小或比小或比1E20大。大。注注意意：循循环环体体外外的的语
5、语句句不不要要放放至至循循环环体体中中, 循循环环体体中中的的语语句句不不要放至循环体外。要放至循环体外。 程序设计举例程序设计举例 5.9 循环应用举例【例【例1】编程显示如下几何图形：【参考例】编程显示如下几何图形：【参考例5-18】P95请编程输出如下的空心图形，要求用循环结构实现。请编程输出如下的空心图形，要求用循环结构实现。下部下部下部下部上部上部上部上部上部：共上部：共上部：共上部：共6 6行，每行共行，每行共行，每行共行，每行共1111个字符。其中，个字符。其中，个字符。其中，个字符。其中，第一行：第第一行：第第一行：第第一行：第1111位为位为位为位为“*“*号，其余为空格号，
6、其余为空格号，其余为空格号，其余为空格第二行：第第二行：第第二行：第第二行：第9 9位和第位和第位和第位和第1111位为位为位为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格第三行：第第三行：第第三行：第第三行：第7 7位和第位和第位和第位和第1111位为位为位为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格第四行：第第四行：第第四行：第第四行：第5 5位和第位和第位和第位和第1111位为位为位为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格第五行：第第五行：第第五行：第第五行：第3 3位和第位和第位和第位和第1111位为位为位
7、为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格第六行：第第六行：第第六行：第第六行：第1 1位和第位和第位和第位和第1111位为位为位为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格下部：共下部：共下部：共下部：共5 5行，每行共行，每行共行，每行共行，每行共1111个字符。其中，个字符。其中，个字符。其中，个字符。其中，第一行：第第一行：第第一行：第第一行：第3 3位和第位和第位和第位和第1111位为位为位为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格第二行：第第二行：第第二行：第第二行：第5 5位和第位和第位和第位和第1
8、111位为位为位为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格第三行：第第三行：第第三行：第第三行：第7 7位和第位和第位和第位和第1111位为位为位为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格第四行：第第四行：第第四行：第第四行：第9 9位和第位和第位和第位和第1111位为位为位为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格第五行：第第五行：第第五行：第第五行：第1111位为位为位为位为“*“*号，其余为空格号，其余为空格号，其余为空格号，其余为空格For(i=11; i=1; i=i-2)For(j=1; j=11;
9、 j+) if(j=i | j=11) printf(“*”); else printf(“ “); For(i=3; i=11; i=i+2)5.9 循环应用举例【例【例1】编程，显示几何图形。】编程，显示几何图形。#includemain()inti,j;for(i=11;i=1;i=i-2)/* /*显示上部图形显示上部图形显示上部图形显示上部图形*/*/printf(n);for(j=1;j=11;j+)if(j=i|j=11)printf(*);elseprintf();for(i=3;i=11;i=i+2)/* /*显示下部图形显示下部图形显示下部图形显示下部图形 */ */pri
10、ntf(n);for(j=1;j=11;j+)if(j=i|j=11)printf(*);elseprintf();printf(n);【例【例2】判断】判断m是否为素数。是否为素数。 【参考例【参考例5-20】 P96 所谓素数，是指大于所谓素数，是指大于1的整数，并且除了的整数，并且除了1和它本身之外不和它本身之外不能被任何整数所整除。能被任何整数所整除。 【算法】【算法】 用用2，3，4，5m-1逐个去除逐个去除m，假设，假设m被其中一个整被其中一个整数，那么数，那么m不是素数，否那么不是素数，否那么m是素数。是素数。 算法优化：当算法优化：当m较大时，除的次数会很多，很费时。较大时，除
11、的次数会很多，很费时。1可以用可以用2，3， ，小于或等于，小于或等于m/2的整数去除，假设的整数去除，假设均不能整除，那么均不能整除，那么m是素数；是素数；2也可以用也可以用2，3，小于或等于，小于或等于 的整数去除的整数去除, 假设均不能整除，那么假设均不能整除，那么m是素数。是素数。5.9 循环应用举例【例【例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(“%
12、d 是一个素数！n,m); elseprintf(“%d 不是一个素数！n,m);相当于For(i = 2; i = k; i+) if(m % i = 0) break;5.9 循环应用举例【例【例3】编写程序】编写程序,计算出计算出2000到到9000之间所有能同时被之间所有能同时被3、5和和7整除的整数的平方根的和，保存整除的整数的平方根的和，保存3位小数。位小数。#include#includemain()inti;doublesum=0;for(i=2000;i=9000;i+)if(i%3=0 & i%5=0 & i%7=0) sum+=sqrt(i);printf(%.3f,su
13、m);5.9 循环应用举例与例与例2、3同类的采用穷举法进行验证的题目有：同类的采用穷举法进行验证的题目有：实验实验6第第4题题编程输出编程输出3300之间的素数。之间的素数。实验实验6第第5题题三色球问题三色球问题:袋中有袋中有12个球，其中红、白、黑分别为个球，其中红、白、黑分别为3、3、6个。问从中任取个。问从中任取8个球，共有多少种不同的取法。个球，共有多少种不同的取法。实验实验6第第6题题输出输出“水仙花数：三位整数水仙花数：三位整数abc并满足并满足a3+b3+c3=abc。例。例:407=43+03+73。实验实验6第第7题题编程输出编程输出10500之间的同构数。之间的同构数。
14、实验实验6第第8题题百鸡问题。百鸡问题。实验实验5第第7题题显示显示500600之间同时被之间同时被5和和7整除的数。整除的数。5.9 循环应用举例【例【例4】求两个整数】求两个整数m和和n的最小公倍数，最大公约数。【参考的最小公倍数，最大公约数。【参考例例5-5】 P82所谓两个整数的最小公倍数，是指能够被两个整数同时整除的所谓两个整数的最小公倍数，是指能够被两个整数同时整除的最小整数。所谓两个整数的最大公约数，是指能够整除这两个最小整数。所谓两个整数的最大公约数，是指能够整除这两个数的最大整数。数的最大整数。可采用穷举法：求m与n的最小公倍数： for(i=n; ; i+) if(i%m=
15、0 & i%m=0) break; printf(“最小公倍数是：%i,i); 求m与n的最大公约数： for(i=n; ; i-) if(m%i=0 & n%i=0) break; printf(“最大公约数是：%i,i); 5.9 循环应用举例【例【例4】求两个整数】求两个整数m和和n的最小公倍数，最大公约数。【参考的最小公倍数，最大公约数。【参考例例5-5】 P82展转相除法：先用m除以n求得余数r，当r0时，再用除数做被除数、余数做除数再求余数，如此反复，直至r0，除数即为所求的最大公约数。p(=m*n)除以最大公约数即为m和n的最小公倍数R0=m, R1=n , R 2 , R3,
16、, Rn=Rn-2/Rn-1, .while(1) r=m % n; if(r!=0) m=n; n=r; else break;/*这时m中即为最大公约数 */while(n!=0) r= m % n; m =n; n=r;5.9 循环应用举例/*求求m,n的最大公约数与最小公倍数的最大公约数与最小公倍数*/#includemain()intp,r,n,m;printf(请输入两个正整数请输入两个正整数:n);scanf(%d,%d,&n,&m);p=n*m;while(n!=0)r=m%n;m=n;n=r;printf(最大公约数是最大公约数是%dn最小公倍数是最小公倍数是%dn,m,p/
17、m);【例【例4】求整数】求整数m和和n的最小公倍数，最大公约数。【参考例的最小公倍数，最大公约数。【参考例5-5】 P825.9 循环应用举例【例【例5】Fibonacci斐波纳契数列的计算方法【参考例斐波纳契数列的计算方法【参考例5-11】P88问题原型：从前有一对长寿兔子，从出生后第问题原型：从前有一对长寿兔子，从出生后第3个月起每个月都生一对兔子。新个月起每个月都生一对兔子。新生的小兔子长到第生的小兔子长到第3个月后每个月又都生一对兔子，这样一代一代生下去，假个月后每个月又都生一对兔子，这样一代一代生下去，假设所有兔子都不死，求兔子增长数量的数列即每个月的兔子总对数。设所有兔子都不死，
18、求兔子增长数量的数列即每个月的兔子总对数。第几个第几个月月小兔子小兔子对对数数中兔子中兔子对对数数老兔子老兔子对对数数兔子兔子总总对对数数00000110012010131012411135212563238Fibonacci斐波纳契数列定义：斐波纳契数列定义：a0= 0a1= 1a2= a0+a1 = 1a3= a1+a2 = 2a4= a2+a3 = 3a5= a3+a4 = 5an= an-2 + an-15.9 循环应用举例#includemain()inta0,a1,a2,k;a0=0;a1=1;printf(%6d%6d,a0,a1);for(k=2;k0.235时求时求和终止并输
19、出和终止并输出S。结果取。结果取3位小数。位小数。1/(1*2*3),1/(2*3*4),1/(3*4*5),1/(n*(n+1)*(n+2),#includemain()floats=0,j,n;for(n=1;n+)j=1/(n*(n+1)*(n+2);s=s+j;if(s0.235)break;printf(%.3f,s);#includemain()floats=0,n;for(n=1;s0.235;n+)s=s+1/(n*(n+1)*(n+2);printf(%.3f,s);简化5.9 循环应用举例【例【例7】编写程序】编写程序,计算并输出下面数列前计算并输出下面数列前n项的和项的和
20、(设设n=20,x=0.5),要求结要求结果保存果保存3位小数。位小数。sin(x)/x,sin(2x)/2x,sin(3x)/3x,sin(n*x)/(n*x),其中其中,sin(x)为正弦函数为正弦函数#include#includemain()intn;doublesum=0,x=0.5;for(n=1;n=20;n+)sum=sum+sin(n*x)/(n*x);printf(%.3fn,sum);5.9 循环应用举例【例【例8】编写程序】编写程序,计算并输出以下数列的和计算并输出以下数列的和,当某项当某项(即即(-1)(n-1)/(2*n+1),该项不参与求和该项不参与求和)的绝对值
21、小于的绝对值小于0.001时求和终止并输出计算结果时求和终止并输出计算结果,要求结果要求结果保存保存3位小数。位小数。1,-1/3,1/5,-1/7,1/9,(-1)(n-1)/(2*n-1)(其中其中,表示幂运算表示幂运算)#include#includemain()intsign=1;doublesum=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);5.9 循环应用举例与例与例6、7、8类似的问题有：类似的问题有：实验实验5 5第第5 5题题求数列求数列1/2,2/3,3/4,4/5,.前前20项的和。项的和。实验实验5 5第第1010题题求求1!+2!+3!+10!的值。的值。实验实验5 5第第1111题题求求1X2X3+3X4X5+99X100X101的值。的值。课堂小结课堂小结1、循环实现几何图形的输出、循环实现几何图形的输出;2、常用算法的思想如：判断素数，求最大公约数、最小公倍数。、常用算法的思想如：判断素数，求最大公约数、最小公倍数。3、会求数列的局部和；、会求数列的局部和；4、注意循环嵌套的层次。注意循环嵌套的层次。
