C++第六讲

高级语言程序设计第四章循环结构程序设计–循环结构典型算法第五章数组–数组的概念例8判断一个数n是否是素数。•素数只能被1和它本身整除的数。•判断的方法{1,2,…,n}之中n的因子的个数n只有两个因子：1和n，则n是素数统计:输入n当j=n时n%j==0真gs++假j=1gs=0gs==2真yes假no#includeiostream.h{intn,j,gs=0;while(j=n){if(n%j==0)gs++;j++;}if(gs==2)coutn”yes”;elsecoutn”no”;}cout”Inputn:”;cinn;j=1;gs=0;循环结构典型算法voidmain()j++例8判断一个数n是否是素数。•如何判断{2,3,…,n-1}之中的数都不是n的因子分析：如果n是素数，那么它只有两个因子：1和n验证:输入n当j=k时n%j!=0真j++假breakj=2k=sqrt(n)j==k+1真yes假no#includemath.h#includeiostream.h{intn,j,k;while(j=k){if(n%j!=0)j++;elsebreak;}if(j==k+1)coutn”yes”;elsecoutn”no”;}cout”Inputn:”;cinn;sqrt(n)j=2,k=sqrt(n);•退出循环时j取值j=k+1–执行break退出j=k循环结构典型算法n是素数n不是素数voidmain()–表达式j=k为假例8判断一个数n是否是素数。设变量f，其值作为判断结果的标志f=1n是素数f=0n不是素数输入n当j=k时n%j!=0真j++假f=0breakj=2f=1f==1真yes假no#includemath.h#includeiostream.hvoidmain(){intn,j,k,f=1;coutInputn:;cinn;j=2,k=sqrt(n),f=1;while(j=k)if(n%j!=0)j++;else{f=0;break;}if(f==1)coutnyes;elsecoutnno;}循环结构典型算法k=sqrt(n)例9找出所有的水仙花数。若m是水仙花数,则:(2)b:m的百位数(1)是三位数s:m的十位数g:m的个位数m等于b3+s3+g3如何分解数?设m=273b=m/100s=m/10-b*10g=m%10#includestdio.hvoidmain(){intm,b,s,g;for(m=100;m1000;m++){b=m/100;s=m/10-b*10;g=m%10;if(b*b*b+s*s*s+g*g*g==m)printf(“%6d”,m);}}循环结构典型算法例9找出所有的水仙花数。若m是水仙花数,则:(2)b:m的百位数(1)是三位数s:m的十位数g:m的个位数m等于b3+s3+g3如何组合数?设m=b*100+s*10+g#includeiostream.hvoidmain(){intm,b,s,g;for(b=1;b=9;b++)for(s=0;s=9;s++)for(g=0;g=9;g++){m=b*100+s*10+g;if(b*b*b+s*s*s+g*g*g==m)coutm;}}循环结构典型算法取值范围：1~9取值范围：0~9取值范围：0~9循环结构典型算法P75第6题找最大公约数可用辗转相除的算法首先把两个数中大的那个数作为被除数，两数相除得一余数。将除数作为被除数，余数作为除数再作除法，得到一个新的余数。不断重复这一过程直到余数为零，这时的除数就是两个数的最大公约数。1r=m%n2若r=0,最大公约数为n否则：m=n,n=r,转到1设两数为m、nr=m%nm=nn=r公约数是n当r!=0时r=m%n算法的文字描述算法的N-S图实例mnr1324542454234230第一个数max循环结构典型算法例10从任意n个数中找出最大的数。1.假设第一个数最大2.第二个数与max比较3.第三个数与max比较n.第n个数与max比较读入amax=a读入aamax真max=afori=2ton读入n输出假大数max大数max大数max读数比较n-1次#includestdio.hvoidmain(){inta,max,i,n;max=a;for(i=2;i=n;i++){scanf(“%d”,&a);max=amax?a:max;}printf(“max=%d”,max);}printf(“\nInputn,a:”);scanf(“%d,%d”,&n,&a);循环结构典型算法#include“stdio.h”voidmain(){charc;while((c=getchar())!=‘\n’)putchar(c);}It’saholiday!It’saholiday!例11读程序写运行结果。#include“stdio.h”voidmain(){charc;while((c=getchar())!=‘\n’){if(c=‘a’&&c=‘z’)}{c-=30;if(c’Z’&&c=‘Z’+2)c-=26;}printf(“%c”,c);}例12读程序写运行结果。aCbDxZyAzB……小写字母变化，其他字符不变aY02+yzkCY02+ABM例13输入一行字符，统计出其中英文字母、空格、其它字符的个数。#includestdio.hvoidmain(){charc;intzm,kg,qt;zm=kg=qt=0;while((c=getchar())!=‘\n’){if(c=‘a’&&c=‘z’||c=‘A’&&c=‘Z’)zm++;elseif(c==‘’)kg++;elseqt++;}printf(“zm=%d,kg=%d,qt=%d”,zm,kg,qt);}循环结构典型算法01x2x3x25•算法概述设方程为f(x)=0，......!2)x(f)xx()x(f)xx()x(f)x(f0200000)x(f)xx()x(f)x(f000设0)x(f0则其解为（记为x1）：)x(f/)x(fxx0001再把f(x)在x1点附近展开成泰勒级数，得：)x(f/)x(fxx1112)x(f/)x(fxxnnn1n,将f(x)在x0=1.5附近展开成泰勒级数：•算法收敛的条件,xxn1n为无穷小程序举例例9用牛顿迭代法计算方程在1.5附近的根。•几何意义1在f(x)上找到f(x0);)x(f)xx()x(fy0003求此切线方程和x轴的交点x1同理可得x2、x3、......等。yxf(x)f(x0)x1f(x1)x2x02过f(x0)做f(x)的切线，交x轴于x1,)x(f)x(fxx0001•框图及程序读入x1x0=x1求f(x0)f’(x0)计算x1当|x0-x1|10-5输出x0程序举例1x2x3x1f25记2x6x52f4记#includemath.h#includestdio.hvoidmain(){floatx0,x1,f1,f2;printf(“\n请输入初值x0:”);scanf(“%f”,&x1);do{x0=x1;f1=pow(x0,5)-3*x0*x0+2*x0+1;f2=5*pow(x0,4)-6*x0+2;x1=x0-f1/f2;}while(fabs(x0-x1)1e-5);printf(“方程的根是:%.5f”,x0);}程序举例读入x1x0=x1求f(x0)f’(x0)计算x1当|x0-x1|10-5输出x0例10求2x3-4x2+3x-6=0在(-10,10)之间的根•二分法1.取两点x1,x2,使区间(x1,x2)包含f(x)的根yxf(x)f2f1输入x1,x2求f1,f2当f1*f20f1*f00真x2=x0假当fabs(f0)1e-5x0=(x1+x2)/2求f0x2x1x0f0x1=x0程序举例适用于单调函数2.用x1,x2的中点x0分割(x1,x2)为(x1,x0)和(x0,x2)选取包含根的区间作为新的(x1,x2),舍弃另一区间3.重复2,直至(x1,x2)很小为止f2=f0f1=f0#includemath.h#includestdio.h{floatx0,x1,x2,f0,f1,f2;do{scanf(“%f,%f”,&x1,&x2);f1=x1*((2*x1-4)*x1+3)-6;f2=x2*((2*x2-4)*x2+3)-6;}while(f1*f20);do{x0=(x1+x2)/2;f0=x0*((2*x0-4)*x0+3)-6;if(f0*f10)x2=x0,f2=f0;elsex1=x0,f1=f0;}while(fabs(f0)1e-5);printf(“root=%f”,x0);程序举例}2x3-4x2+3x-6=0voidmain()输入x1,x2求f1,f2当f1*f20f1*f00真x2=x0假当fabs(f0)1e-5x0=(x1+x2)/2求f0x1=x0f2=f0f1=f0数组的基本概念用基本数据类型能解决所有问题吗？30名？概念的引入例如：对某班学生的成绩按由高到低的次序进行排序。3名？数组是具有一定顺序的一组相同类型变量的集合体–数组的概念组成数组的变量称为该数组的元素如：整型数组a，包含十个变量，分别是a[0],a[1],a[2],a[3]……a[9]–数组的维一维数组：数组元素只有一个下标二维数组：数组元素有两个下标例如：b数组,实型,12个变量:b[0][0],b[0][1],b[0][2],b[0][3],b[1][0],……,b[2][3]先定义，后使用–使用原则名字类型大小维