《CNOIP竞赛实用实用教案》由会员分享,可在线阅读,更多相关《CNOIP竞赛实用实用教案(53页珍藏版)》请在金锄头文库上搜索。
1、第一节for语句(yj)一、语句(yj)(yj)格式格式1 1说明:语句说明:语句1 1是是forfor循环循环(xnhun)(xnhun)语句的循环语句的循环(xnhun)(xnhun)体,它将在满足条件的情体,它将在满足条件的情况下被重复执行。况下被重复执行。格式格式2 2说明:循环体部分由多个语句构成,应由一对花括号括起来,构成一个语句块的形式。程序风格提示:写for循环语句时,循环体的语句相对于for缩进两格。第1页/共52页第一页,共53页。第一节for语句(yj)二、语句执行过程for语句的执行过程可由以下4步来描述。(1)执行“控制变量初始化语句”,使控制变量获得一个初值。(2)
2、判断控制变量是否满足“条件表达式”,若满足条件则执行一遍循环(xnhun)体,否则结束整个for语句,继续执行for循环(xnhun)下面的句子。(3)根据增量表达式,计算出控制变量所得到的新值(4)自动转到第(2)步。第2页/共52页第二页,共53页。第一节for语句(yj)三、语句格式举例 (1) (1)将控制变量从1 1变到100100,增量为1 1 for(i=1;i=100;+i) for(i=1;i=1;- -i) for(i=100;i=1;- -i) (3) (3)控制变量从7 7变到7777,增量为7 7 for(i=7;i=77;i+=7) for(i=7;i=2 for(
3、int i=20;i=2;i-=2)i-=2) (5) (5)按所示数列改变控制变量值:9999、8888、7777、6666、5555、4444、3333、2222、1111、0 0,增量为-11-11 for(int j=99;j=0;j-=11) for(int j=99;j=0;j-=11) (6) (6)控制变量i i和j j共同进行循环控制,i i从1 1变到9999,j j从2 2变到100100,增量均为2 2。 for for(int i=1,j=2;i=99&j=100int i=1,j=2;i=99&j=100;i+=2,j+=2i+=2,j+=2)需要说明的是:可以在f
4、orfor循环“ “ 控制变量初始化语句”中声明变量(如上面最后3 3个例子),这些变量只在forfor循环结构中有效,离开(l ki)(l ki)了该forfor结构,变量就无效了。 第3页/共52页第三页,共53页。第一节for语句(yj)例4.1 4.1 输出11001100之间所有偶数。#include #include using namespace std;using namespace std;int main ()int main () for (int i=2; i=100 ; i+=2) for (int i=2; i=100 ; i+=2) cout i ; cout i
5、 ;return 0;return 0; 例4.2 4.2 利用forfor循环(xnhun),(xnhun),计算输出1+2+1001+2+100的和#include using namespace std;#include using namespace std;int main ()int main () int sum=0; int sum=0; for (int i=1; i=100 ; +i) for (int i=1; i=100 ; +i) sum+=i; sum+=i; cout sum; cout sum; return 0; return 0; 第4页/共52页第四页,共
6、53页。第一节for语句(yj)例4.3 4.3 利用forfor循环计算n n!的值。分析:n n!1*2*3*n1*2*3*n#include #include using namespace std;using namespace std;int main ()int main () long long s; /Noip2010 long long s; /Noip2010开始C+C+语言(yyn)(yyn)中long longlong long类型允许使用 int n; /n int n; /n不能定义为long longlong long,否则forfor语句死循环 s=1; s=1
7、; scanf(%d,&n); scanf(%d,&n); for (int i=1; i=n ; +i) / for (int i=1; i=13n=13时,s s值超过了intint类型的表示范围。还有一种比intint更大的类型,称为long longlong long,它的表示范围是-263-263263-1263-1,比-1019-101910191019略窄,而我们一直使用的intint范围是-231-231231-1,231-1,只比-2*109-2*1092*1092*109略宽。 输入输出long longlong long也可以借助于printfprintf和scanfsc
8、anf语句,但对应的占位符却是和平台与编译器相关的:在linuxlinux中,g+g+很统一的用%lld%lld;在windowswindows中,MinGWMinGW的g+g+和VC6VC6可用%I64d%I64d;高版本编译器下的windowswindows可以试用%lld%lld。第5页/共52页第五页,共53页。第一节for语句(yj)例4.4 4.4 利用forfor循环, ,分别计算11001100中奇数的和、偶数的和。#include #include using namespace std;using namespace std;int main ( )int main ( )
9、 int jssum=0; int jssum=0; int ossum=0; int ossum=0; for (int js=1,os=2;js=99&os=100;js+=2 ,os+=2 ) for (int js=1,os=2;js=99&os=100;js+=2 ,os+=2 ) jssum+=js; jssum+=js; ossum+=os; ossum+=os; cout the sum of odd numbers 1 cout the sum of odd numbers 1 toto 100 is : jssumendl; 100 is : jssumendl; cout
10、 the sum of even numbers 1 cout the sum of even numbers 1 toto 100 is : ossumendl; 100 is : ossumendl; return 0; return 0; 说明: 我们也可以在forfor循环初始化或增值表达式部分中放一条(y tio)(y tio)以上的语句,中间用逗号隔开。第6页/共52页第六页,共53页。【上机练习(linx)4.1】1、求12+22+32+10022、求s=1+1/2+1/3+1/1003、计算100之内所有的奇数之和。4、求10个数中的最大值和最小值。5、按字母(zm)表的顺序,
11、从字母(zm)A到Z顺序打印输出。6、求菲波拉契数列a0,a1,a2,a20。a0=0,a1=1,a2=a1+a0,a3=a2+a1,an=an-1+an-2;如0,1,1,2,3,5,8,13,21,第7页/共52页第七页,共53页。第二节while语句(yj)一、语句(yj)(yj)格式格式1 1 说明:循环体部分由多个语句构成,应由一对花括号说明:循环体部分由多个语句构成,应由一对花括号(kuho)(kuho)括起来,构成一个语句块的形式。括起来,构成一个语句块的形式。程序风格提示:写程序风格提示:写whilewhile循环语句时,循环体的语句相对于循环语句时,循环体的语句相对于whil
12、ewhile缩进两格。缩进两格。说明:语句1是while循环语句的循环体,它将在满足条件的情况下被重复执行。格式2第8页/共52页第八页,共53页。第二节while语句(yj)二、语句执行过程(1)(1)计算作为循环控制条件表达式的值,得到逻辑真或假,假定用M M表示。(2)(2)若M M为真,则执行了一遍循环体,否则离开循环,结束整个whilewhile语句的执行。(3)(3)循环体的所有语句执行结束后,自动转向第(1)(1)步执行。(4)(4)在循环体中应有使循环趋向于结束的语句。如果无此语句,则i i的值始终(shzhng)(shzhng)不改变,循环永不结束。三、格式举例(1) i=0
13、;(1) i=0; while (i10) while (ix;(2) cinx; while while(x0xx; cinx;功能:当输入的数据小于0 0时,重复读数据。第9页/共52页第九页,共53页。第二节while语句(yj)例4.5 4.5 求s=1 +2 +3+ns=1 +2 +3+n,当加到第几项时,s s的值会超过10001000?程序(chngx)(chngx)如下: #include #include using namespace std;using namespace std;int main ()int main () int n=0,s=0; int n=0,s=
14、0; while (s=1000) while (s=1000) +n; +n; s+=n; s+=n; coutn; coutn; return 0; return 0; 第10页/共52页第十页,共53页。第二节while语句(yj)例4.6 4.6 求两个正整数,的最大公约数。分析:求两个整数的最大公约数可以采用辗转相除法。以下是辗转相除法的算法:分别用m m,n n,r r表示(biosh)(biosh)被除数、除数、余数;1)1)求m m除以n n的余数r r;2)2)当r!=0,r!=0,执行第3)3)步;若r=0r=0,则n n为最大公约数, ,算法结束。3)3)将n n的值赋给
15、m m,将r r的值赋给n n;再求m m除以n n的余数r r。4)4)转到第2)2)步#include #include using namespace std;using namespace std;int main ()int main () int m,n,r; int m,n,r; cinmn; cinmn; r =m % n; r =m % n; while (r!=0) / while (r!=0) /也可以使用 while (r),c+ while (r),c+中 非0 0即真 m=n; m=n; n=r; n=r; r=m % n; r=m % n; cout cout最大
16、公约数=nendl;=n=51+ 1/2 + 1/3 +1/n =5的最小n n值。分析:此题不等式的左边是一个求和的算式,该和式中的数据项个数是未知的,也正是要求出的。对于和式中的每个数据项,对应的通式为1/i1/i,i=1i=1,2 2,nn。所以可采用循环累加的方法来计算出它的值。设循环变量为i i,它应从1 1开始取值,每次增加1 1,直到和式的值不小于5 5为止,此时的i i值就是所求的n n。设累加变量为s s,在循环体内把1/i1/i的值累加到s s上。根据以上(yshng)(yshng)分析,采用whilewhile循环编写出程序如下:#include #include usi
17、ng namespace std;using namespace std;int main ()int main () int i=0; int i=0; float s=0; float s=0; while(s5) / while(s5) /当s s的值还未超过5 5时 +i; +i; s+=1.0/i; s+=1.0/i; couti; couti; return 0; return 0; 若采用forfor循环(xnhun)(xnhun)来写,则如下所示:#include #include using namespace std;using namespace std;int main
18、 ()int main () int i; int i; float s=0; float s=0; for(i=1;s5;+i) for(i=1;s5;+i) s+=1.0/i; s+=1.0/i; couti-1; couti-1; return 0; return 0; 第12页/共52页第十二页,共53页。第二节while语句(yj)例4.8 4.8 数据统计 输入一些整数,求出它们的最小值、最大值和平均值(保留3 3位小数)。输入保证这些数都是不超过(chogu)1000(chogu)1000的整数。 样例输入:2 8 3 5 1 7 3 62 8 3 5 1 7 3 6 样例输出:
19、1 8 4.3751 8 4.375【参考程序】#include#includeint main()int main() int x,n=0,min,max,s=0; int x,n=0,min,max,s=0; while (scanf(%d,&x)=1) while (scanf(%d,&x)=1) s+=x; s+=x; if (xmin) min=x; if (xmax) max=x; if (xmax) max=x; +n; +n; printf(“%d %d %.3lfn”,min,max,(double)s/n);/ printf(“%d %d %.3lfn”,min,max,(
20、double)s/n);/将s s转换成doubledouble类型 return 0; return 0; 第13页/共52页第十三页,共53页。第二节while语句(yj) 整数的个数是不确定的,所以不能用for循环。scanf函数有返回值?它返回的是成功输入的变量个数,当输入结束时,scanf无法再次读取x,将返回EOF。 在windows下,输入结束完毕后先按enter键,再按ctrl+z键,最后再按enter键,即可结束输入。 这个程序的运行结果每次是不确定的,不难验证下面的结论:变量max在一开始就等于一个大数值,自然无法更新为比它小的值8。变量在未赋值之前是不确定的,特别地,它不
21、一定等于0。 解决的方法就很清楚了:在使用之前赋初值。由于min保存的最小值,他的初值应该是一个很大的数;反过来,max的初值应该是一个很小的数。一种方法是定义一个很大的常数。如INF=1000000000,然后让max=-INF,而min=INF。而另一种方法就是先读取第一个整数x,然后max=min=x。这样的好处是避免(bmin)了认为的假想无穷大值,程序更加优美。第14页/共52页第十四页,共53页。第二节while语句(yj)【优化程序】#include#defineINF100000000intmain()intx,n=0,min=INF,max=-INF,s=0;while(sc
22、anf(%d,&x)=1)/scanf(%d,&x)!=EOF,如果(rgu)没数据可读,scanf返回EOFs+=x;if(xmax)max=x;+n;printf(%d%d%.3lfn,min,max,(double)s/n);return0;第15页/共52页第十五页,共53页。第二节while语句(yj) 最后,我们来更仔细地研究一下输入输出。研究对象就是经典的“A+B”“A+B”问题:输入若干对整数(zhngsh)(zhngsh),输出每对之和。假设每个整数(zhngsh)(zhngsh)不超过109109,一共不超过106106个数对。 第1 1种方法是: #include #in
23、clude int main() int main() int a,b; int a,b; while(scanf(%d%d,&a,&b)=2) while(scanf(%d%d,&a,&b)=2) printf(%dn,a+b); printf(%dn,a+b); return 0; return 0; 第2 2种方法也许更加(gnji)(gnji)常用(你再也不用记住%d%d、%lf%lf等恼人的占位符了): #include #include using namespace std; using namespace std; int main() int main() int a,b;
24、int a,b; while(cin a b ) while(cin a b ) cout a+b endl; cout a+b endl; return 0; return 0; 第16页/共52页第十六页,共53页。【上机练习(linx)4.2】1、用while循环完成如下3题:求s=1+2+3+4+10求s=1+1/2+1/3+1/100计算n!,其中(qzhng)n由键盘输入。2、输入任意的自然数A,B,求A,B的最小公倍数。3、小球从100高处自由落下,着地后又弹回高度的一半再落下。求第20次着地时,小球共通过多少路程?4、Faibonacci数列前几项为:0,1,1,2,3,5,8
25、,其规律是从第三项起,每项均等于前两项之和。求前30项,并以每行5个数的格式输出。第17页/共52页第十七页,共53页。第三节do-while语句(yj)一、语句(yj)(yj)格式格式1 1说明(shumng)(shumng):语句1 1是do-whiledo-while的循环体。格式2 2说明:循环体部分由多个语句构成,应由一对花括号括起来,构成一个语句块的形式。第18页/共52页第十八页,共53页。二、语句执行过程(1)执行一遍循环(xnhun)体。(2)求出作为循环(xnhun)条件的“条件表达式”的值,若为逻辑值真则自动转向第(1)步,否则结束do循环(xnhun)的执行过程,继续执
26、行其后面的语句。在do语句的循环(xnhun)体中也可以使用break语句,用它来非正常结束循环(xnhun)的执行。第19页/共52页第十九页,共53页。第三节do-while语句(yj)三、实例例4.9 4.9 对于求两个正整数,的最大公约数可以用dowhiledowhile实现。代码如下(rxi)(rxi),请完善: #include #include using namespace std;using namespace std;int main ()int main () int m int m,n n,r;r; cinmn; cinmn; do / do /辗转相除法 r =m %
27、 n; r =m % n; m=_; m=_; n=_; n=_; while ( _ ); while ( _ ); coutthe greatest common divisor is:_; coutthe greatest common divisor is:_; return 0; return 0; 第20页/共52页第二十页,共53页。第三节do-while语句(yj)例4.10 4.10 求19921992个19921992的乘积的末两位数是多少(dusho)(dusho)?【分析】积的个位与十位数只与被乘数与乘数的个位与十位数字有关,所以本题相当于求19921992个9292相
28、乘,而且本次的乘积是下一次相乘的被乘数,因此也只需取末两位参与运算就可以了。 #include#includeusing namespace std;using namespace std;int main()int main() int a=1,t=0; int a=1,t=0; do do +t; +t; a=(a*92)%100; a=(a*92)%100; while (t!=1992); while (t!=1992); coutaendl; coutaendl; return 0; return 0; 第21页/共52页第二十一页,共53页。第三节do-while语句(yj)例4.
29、11 4.11 校体操队到操场集合, ,排成每行2 2人, ,最后多出1 1人; ;排成每行3 3人, ,也多出1 1人; ;分别按每行排4,5,64,5,6人, ,都多出1 1人; ;当排成每行7 7人时, ,正好不多。求校体操队至少多少人? ?【分析】设校体操队为x x人, ,根据题意x x应是7 7的倍数, ,因此x x的初值为7,7,以后用x+=7)x+=7)改变x x值; 为了控制循环, , 用逻辑变量yesyes为真(true) (true) 使循环结束; 如果诸条件中有一个不满足, yes , yes 的值就会为假(false)(false),就继续循环。 #include#in
30、cludeusing namespace std;using namespace std;int main()int main() bool yes; bool yes; int x=0; int x=0; do do yes=true; yes=true; x+=7; x+=7; if (x%2!=1) yes=false; if (x%2!=1) yes=false; if (x%3!=1) yes=false; if (x%3!=1) yes=false; if (x%4!=1) yes=false; if (x%4!=1) yes=false; if (x%5!=1) yes=fals
31、e; if (x%5!=1) yes=false; if (x%6!=1) yes=false; if (x%6!=1) yes=false; while (yes=false); / while (yes=false); / 直到(zhdo)yes(zhdo)yes的值为真 coutAll=x; coutAll=x; return 0; return 0; 程序中对每个x x值,都先给yes yes 赋真值,只有在循环体各句对x x进行判断时,都得到“通过”(此处不赋假值)才能保持真值。第22页/共52页第二十二页,共53页。【上机练习(linx)4.3】1 1、用do-whiledo-wh
32、ile循环完成如下3 3题:求s=1+2+3+4+10s=1+2+3+4+10求s=1+1/2+1/3+1/100s=1+1/2+1/3+1/100计算n n!,其中n n由键盘输入。2 2、读一组实数, ,遇零终止, ,打印其中正、负数的个数及各自的总和。3 3、用辗转相除法求两个自然数的最大公约数。4 4、找出被2 2、3 3、5 5除时余数(ysh)(ysh)为1 1的最小的十个数。5 5、将一根长为369cm369cm的钢管截成长为69cm69cm和39cm39cm两种规格的短料。在这两种规格的短料至少各截一根的前提下, , 如何截才能余料最少?第23页/共52页第二十三页,共53页。
33、(1) while( )while( )(4) while( )dowhile( );(2) dodo while( );while( );(5) for(; ;)while( ) (3) for(;)for(; ;)(6) dofor (; ;) while( );第四节 循环(xnhun)嵌套第24页/共52页第二十四页,共53页。第四节循环(xnhun)嵌套 例例4.12 4.12 求求 S=1!+2!+3!+.+10! S=1!+2!+3!+.+10! 分析分析(fnx)(fnx):这个问题是求:这个问题是求1010以内自然数的阶乘之和,可以用以内自然数的阶乘之和,可以用forfor循
34、环来实现。程序结构如下:循环来实现。程序结构如下: for(i=1;i=10;+i) for(i=1;i=10;+i) (1)i (1)i阶乘的值存到阶乘的值存到t t; /t=i! /t=i! (2) (2)累加累加t t到到s s中;中; /s+=t /s+=t 显然根据以上结构,通过显然根据以上结构,通过1010次的循环可以求出次的循环可以求出1 1!,!,2 2!,!,10!,10!,并不断累加起来,求出并不断累加起来,求出s s。而求。而求t=i!,t=i!,又可以用一个又可以用一个forfor循环来实现:循环来实现: t=1; t=1; for (j=1;j=i;+j) for (
35、j=1;j=i;+j) t*=j; t*=j;第25页/共52页第二十五页,共53页。因此整个程序为:#include #include using namespace std;using namespace std;int main ()int main () int t,s; int t,s; s=0; s=0; for(int i=1;i=10;+i) for(int i=1;i=10;+i) t=1; t=1; for (int j=1;j=i;+j) / for (int j=1;j=i;+j) /求i!i! t*=j; t*=j; s+=t; / s+=t; /累加i!i! cou
36、ts; couts; return 0; return 0; 以上程序是一个forfor循环的嵌套。这种方法是比较容易想到(xin do)(xin do)的,但实际上对于求i i!,我们可以根据求出的(i-1i-1)!乘上i i即可得到,而无需重新从1 1再累乘到i i。第四节 循环(xnhun)嵌套第26页/共52页第二十六页,共53页。第四节循环(xnhun)嵌套因此(ync)(ync)程序可改为: :#include #include using namespace std;using namespace std;int main ()int main () int t=1,s=0; i
37、nt t=1,s=0; for(int i=1;i=10;+i) for(int i=1;i=10;+i) t*=i; /t t*=i; /t为上一个数的i-1i-1的阶乘值,再乘以i i即为i!i! s+=t; / s+=t; /累加i!i! couts; couts; return 0; return 0; 显然第二个程序的效率要比第一个高得多。第一个程序要进行1+2+3+10=551+2+3+10=55次循环,而第二程序进行1010次循环。若题目中求的是1 1!+2+2!+1000+1000!,则两个程序的效率区别更明显。第27页/共52页第二十七页,共53页。第四节循环(xnhun)嵌
38、套例4.13 4.13 一个炊事员上街采购,用500500元钱买了9090只鸡,其中母鸡一只1515元, ,公鸡一只1010元,小鸡一只5 5元,正好把钱买完。问母鸡,公鸡,小鸡各买了多少只?【分析】设母鸡i i只, ,公鸡j j只, ,则小鸡为90-i-j90-i-j只, ,则15*i+ 10* j+(90-i-j)*5=500,15*i+ 10* j+(90-i-j)*5=500,显然一个方程求两个(lin )(lin )未知数是不能直接求解。必须组合出所有可能的i,ji,j值,看是否满足条件。这里i i的值可以是0 0到3333,j j的值可以0 0到5050。源程序如下:#includ
39、e #include using namespace std;using namespace std;int main ()int main () int k; int k; for (int i=0;i=33;+i) for (int i=0;i=33;+i) / /枚举母鸡的数量 for (int j=0;j=50;+j) / for (int j=0;j=50;+j) /枚举公鸡的数量 k=90-i-j; k=90-i-j; if (15*i+10*j+k*5=500) if (15*i+10*j+k*5=500) cout cout母鸡有ii只,公鸡有jj只,小鸡有kk只 endl;e
40、ndl; return 0; return 0; 第28页/共52页第二十八页,共53页。第四节循环(xnhun)嵌套例例4.14 4.14 利用利用(lyng)for(lyng)for循环语句输出图循环语句输出图4-14-1中的三角形。中的三角形。* *图图4-14-1#include #include using namespace std;using namespace std;int main ()int main () for (int i=1; i=5; +i) / for (int i=1; i=5; +i) /控制(kngzh)(kngzh)行数 for (int j=1; j
41、=i; +j) / for (int j=1; j=i; +j) /输出一行中的* *数 cout*; cout*; coutendl; / coutendl; /换行 return 0; return 0; 第29页/共52页第二十九页,共53页。第四节循环(xnhun)嵌套例4.15 4.15 求100100999999中的水仙花数。若三位数ABCABC,ABC=A3+B3+C3ABC=A3+B3+C3,则称ABCABC为水仙花数。例如153153,13+53+33=1+125+27=15313+53+33=1+125+27=153,则153153是水仙花数。【分析】 根据题意(t y)(
42、t y),采用三重循环来求解。由于循环次数一定,用forfor循环最为简单。程序如下:#include#include#include /#include /调用setwsetw函数需注明使用该库using namespace std;using namespace std;int main()int main() for (int a=1; a=9; +a) for (int a=1; a=9; +a) for (int b=0; b=9; +b) for (int b=0; b=9; +b) for (int c=0; c=9; +c) for (int c=0; c=9; +c) if
43、(a*a*a+b*b*b+c*c*c=a*100+b*10+c) if (a*a*a+b*b*b+c*c*c=a*100+b*10+c) coutsetw(6)a*100+b*10+c; /setw coutsetw(6)a*100+b*10+c; /setw函数控制输出场宽 return 0; return 0; 运行结果:153153370370371371407407第30页/共52页第三十页,共53页。第四节循环(xnhun)嵌套同时也可以采用一个for循环来求解,表面(biomin)上看好像优于三重循环,实际上却比上面的程序效率低,请同学们自己分析。程序如下:#include#inc
44、ludeusing namespace std;int main() int a,b,c; for (int m=100; m=999; +m) a=m/100; /m的百位 b=(m%100)/10; /m的十位 c=m%10; /m的个位 if (a*a*a+b*b*b+c*c*c=m) coutsetw(6)m; return 0;第31页/共52页第三十一页,共53页。第四节循环(xnhun)嵌套例4.16 4.16 输出100200100200中所有的素数。分析:我们可对100-200100-200之间的每一个整数进行判断(pndun)(pndun),若它是为素数,则输出。而对于任意
45、整数i i,根据素数定义,我们从2 2开始,到sqrtsqrt(i i),找i i的第一个约数,若找到第一个约数,则i i必然不是素数。程序如下:#include #include #include /#include /在Dev C+Dev C+中可调用数学函数库cmathcmathusing namespace std;using namespace std;int main ()int main () int x; int x; for (int i=100;i=200;+i) for (int i=100;i=200;+i) x=2; x=2; while(x=floor(sqrt(i
46、)&(i%x!=0) /floor while(xfloor(sqrt(i) if ( xfloor(sqrt(i) coutit; coutit; return 0; return 0; 第32页/共52页第三十二页,共53页。第四节循环(xnhun)嵌套例4.17 4.17 输出所有形如aabbaabb的四位完全平方数(即前两位数字相等,后两位数字也相等)。【分析】分支和循环结合在一起时威力特别强大:我们枚举所有可能(knng)(knng)的aabbaabb,然后判断它们是否为完全平方数。注意,a a的范围是1 19 9,b b可以是0 0。主程序如下: for (a=1; a=9; a+
47、) for (a=1; a=9; a+) for (b=0; b=9; b+) for (b=0; b=9; b+) if (aabb if (aabb是完全平方数) printf(%dn,aabb);) printf(%dn,aabb);另一个思路是枚举平方根x x,参考程序如下:#include#includeint main()int main() int n=0,hi,lo;int n=0,hi,lo;for (int x=32 ;x100; +x) /for (int x=32 ;x100; +x) /可以直接从x=32x=32开始枚举 n=x*x;n=x*x; hi = n/100
48、;hi = n/100;lo = n%100;lo = n%100;if (hi/10 = hi%10 & lo/10 = lo%10) printf(%dn,n);if (hi/10 = hi%10 & lo/10 = lo%10) printf(%dn,n); return 0;return 0; 第33页/共52页第三十三页,共53页。第四节循环(xnhun)嵌套例4.18 4.18 阶乘之和 输入n n,计算S=1! + 2! + 3! + + n!S=1! + 2! + 3! + + n!的末6 6位( (不含前导0)0)。n=106n=106, n! n!表示前n n个正整数之积。
49、 样例输入:1010 样例输出:3791337913【分析】 这个任务并不难,引入累加变量S S之后,核心(hxn)(hxn)算法只有一句话:for (i=1;i=n;i+) S+=i!for (i=1;i=n;i+) S+=i!。不过C+C+语言并没有阶乘运算符,所以这句话只是伪代码,而不是真正的代码。事实上,我们还需要一次循环来计算i!i!:for (j=1;j=i;+j) factorial*=j;for (j=1;j=i;+j) factorial*=j;。代码如下:#include#includeint main()int main() int n,s=0;int n,s=0;sca
50、nf(%d,&n);scanf(%d,&n);for (int i=1;i=n;+i)for (int i=1;i=n;+i) int factorial=1;int factorial=1;for (int j=1;j=i;+j)for (int j=1;j=i;+j) factorial*=j; factorial*=j;s+=factorial;s+=factorial; printf(%dn,s%1000000);printf(%dn,s%1000000);return 0;return 0; 注意累乘器factorial(factorial(英文“阶乘”的意思) )定义在循环里面。换
51、句话说,每执行一次循环体,都要重新声明一次factorialfactorial,并初始化为1(1(想一想,为什么不是0)0)。因为只要末6 6位,所以输出时对106106取模。第34页/共52页第三十四页,共53页。第四节循环(xnhun)嵌套 当n=100n=100时,输出-961703-961703,直觉告诉我们:乘法溢出了。这个直觉很容易通过“输出中间变量”法得到验证,但若要解决这个问题,还需要一点数学知识。试一下n=106n=106时输出什么?更会溢出,但是(dnsh)(dnsh)重点不在这里。事实上,它的速度太慢!让我们把程序改成“每步取模”的形式,然后加一个“计时器”,看看它到底有
52、多慢。#include#include#include#includeint main()int main() const int MOD=1000000;const int MOD=1000000;int n,s=0;int n,s=0;scanf(%d,&n);scanf(%d,&n);for (int i=1;i=n;+i)for (int i=1;i=n;+i) int factorial=1;int factorial=1;for (int j=1;j=i;+j)for (int j=1;j=i;+j)factorial=(factorial*j%MOD);factorial=(fa
53、ctorial*j%MOD);s=(s+factorial)%MOD;s=(s+factorial)%MOD; printf(%dn,s);printf(%dn,s);printf(Time used= %.2lfn,(double)clock()/CLOCKS_PER_SEC);printf(Time used= %.2lfn,(double)clock()/CLOCKS_PER_SEC);return 0; /return 0; /输出时间包含键盘输入的时间,建议用文件输入输出,后面章节介绍文件 这个程序真正的特别之处在于计时函数clock()clock()的使用。该函数返回程序目前为止运
54、行的时间。这样,在程序结束之前调用它,便可获得整个程序的运行时间。这个时间除以常数CLOCKS_PER_SECCLOCKS_PER_SEC之后得到的值以“秒”为单位。 输入100000100000,按EnterEnter键,系统迟迟不输出答案,原因在于程序中重复进行了多次阶乘运算,浪费了大量时间,具体优化方法请参考例4.12 4.12 。第35页/共52页第三十五页,共53页。比饭量(fnling)3个人(grn)比饭量大,每个人(grn)说了两句话。A说:B比我吃得多,C和我一样多。B说:A比我吃得多,A也比C吃得多。C讲:我比B吃得多,B比A吃得多。事实上饭量越小的人讲对的话越多,请你编程
55、按饭量大小输出3人的顺序。第36页/共52页第三十六页,共53页。上面是原题,但从结果来看,3个人的饭量没有相同的。代码如下(rxi)。intA,B,C;/饭量inta,b,c;/正确度for(A=0;A3;A+)for(B=0;B3;B+)for(C=0;C3;C+)a=(AB)+(AC);/B说:A比我吃得多,A也比C吃得多。c=(CB)+(BA);/C讲:我比B吃得多,B比A吃得多。if(ab&bc&AB&BC)coutABCc&cb&AC&CB)coutACBa&ac&BA&AC)coutBACc&ca&BC&CA)coutBCAa&ab&CA&AB)coutCABb&ba&CB&BA
56、)coutCBAendl;第37页/共52页第三十七页,共53页。执行(zhxng)结果是:BCA。相对的饭量和正确度如下:a0b2c1A2B0C1第38页/共52页第三十八页,共53页。【上机练习(linx)4.4】1 1、求s=11+22+33+.+NN s=11+22+33+.+NN 2 2、求s=1+1/2!+1/3!+1/10!s=1+1/2!+1/3!+1/10!3 3、输入一个整数,若是素数,输出“YES”“YES”,否则输出“NO”“NO”4 4、任给一个自然数n n,求出这个自然数不同因数的个数。 如:n=6n=6时,因为1 1,2 2,3 3,6 6这四个数均是6 6的因数
57、,故输出为total=4total=4。5 5、输入一列图形(字母金字塔) a a a b a b a b c a b c . . . . a b c y z a b c y z6 6、把一张一元钞票换成一分,二分和五分的硬币,每种至少(zhsho)(zhsho)一枚。问有哪几种换法?7 7、百鸡问题:一只公鸡值5 5元,一只母鸡值3 3元,而1 1元可买3 3只小鸡。现有100100元钱,想买100100只鸡。问可买公鸡、母鸡、小鸡各几只?8 8、某人想将手中的一张面值100100元的人民币换成1010元、5 5元、2 2元和1 1元面值的票子。要求换正好4040张,且每种票子至少(zhsh
58、o)(zhsho)一张。问:有几种换法?应适当考虑减少重复次数。9 9、有一堆100100多个的零件,若三个三个数,剩二个;若五个五个数,剩三个;若七个七个数,剩五个。请你编一个程序计算出这堆零件至少(zhsho)(zhsho)是多少个?1010、编写一程序,验证角谷猜想。所谓的角谷猜想是:“对于任意大于1 1的自然数n n,若n n为奇数,则将n n变为3*n+13*n+1,否则将n n变为n n的一半。经过若干次这样的变换,一定会使n n变为1 1。”1111、哥德巴赫猜想(任何充分大的偶数都可由两个素数之和表示)。将4-1004-100中的所有偶数分别用两个素数之和表示。输出为:4=2+
59、24=2+26=3+36=3+3100=3+97100=3+97第39页/共52页第三十九页,共53页。转向控制(kngzh)语句break 语句语句(yj)在switch语句(yj)、while语句、do-while 语句、for 语句中使用break语句,以跳出switch语句或内层循环,继续执行逻辑上的下一条语句。第40页/共52页第四十页,共53页。示例(shl)#include using namespace std;int main()int n;for( ; ; )cinn;if (n = 0) break;第41页/共52页第四十一页,共53页。示例(shl)#include
60、using namespace std;int main()int n;while(true)cinn;if (n = 0) break;第42页/共52页第四十二页,共53页。转向控制语句continue 语句用于循环语句中,作用(zuyng)是结束本次循环,接着立即测试循环控制表达式,判断是否继续执行下一次循环。第43页/共52页第四十三页,共53页。#include void main()int n, counter=0;for(n=1;n=100;n+)if(n%3=0 | n%5=0 | n%7=0)continue;coutnt;counter+;if(counter%10=0)c
61、outendl;coutendl;示 例第44页/共52页第四十四页,共53页。早期的程序控制方法Goto 语句无条件转向语句它的一般形式为goto 语句标号;语句标号:标识符,定名(dng mng)规则与变量名相同;例如: goto label-1;goto loop;第45页/共52页第四十五页,共53页。Goto 语句语句(yj)的例子的例子C+ 语言(yyn)int main( ) int i, sum=0;i=1;loop: sum=sum+i;i+;goto loop;coutsumendl;return 0;loop:汇编语言load 0 a 数据(shj)装入寄存器0load
62、1 b 数据(shj)装入寄存器1mult 0 1 寄存器0与1的数据(shj)相乘load 1 c 数据(shj)装入寄存器1add 0 1 寄存器0与1的数据(shj)加goto loopsave 0 d 保存寄存器0里的数据(shj)第46页/共52页第四十六页,共53页。Goto 语句语句(yj)和和 if 语句语句(yj)main( )int i, sum=0;i=1;loop: if (i=100)sum=sum+i;i+;goto loop;printf(%d,sum);第47页/共52页第四十七页,共53页。关于 Goto 语句的讨论著名的荷兰(h ln)教授 E. W. Di
63、jkstra1965年,年,IFIP(InternationalFederation for InformationProcessing)会议上,)会议上,Dijkstra提出提出“Go To语句可以从高级语言中取语句可以从高级语言中取消消”,“一个程序的质量与程序中一个程序的质量与程序中所含的所含的Go To语句的数量成反比语句的数量成反比”。但是,但是,Dijkstra讲话的影响讲话的影响(yngxing)很小,当很小,当时人们正广泛地使用时人们正广泛地使用FORTRAN,而而Go To语句则是语句则是FORTRAN的支柱。的支柱。Algol60设计实现者GoTo有害论提出(t ch)者信
64、号量理论提出(t ch)者最短路径算法提出(t ch)者THE操作系统设计者程序正确性证明推动者第48页/共52页第四十八页,共53页。关于 Goto 语句的讨论1968年,Dijkstra给ACM通讯写了一篇短文“Go To Statement Considered Harmful” ,该文后改成(i chn)信件形式刊登,成为著名的“GoTo Letter”。Dijkstra在信中建议:“Go To语句太容易把程序弄乱,应从一切高级语言中去掉;只用三种基本控制结构就可以写各种程序,而这样的程序可以由上而下阅读而不会返回”。在整个计算科学的范围内,引发了关于Goto语句的讨论。第49页/共5
65、2页第四十九页,共53页。关于 Goto 语句的讨论60年代末至70年代,关于goto语句的争论非常激烈正方:从高级语言(yyn)中去掉goto语句:包含goto语句的程序难以阅读,难以查错;去掉(q dio)goto语句后,可以直接从程序结构上反映程序的运行过程。使程序的结构清晰、便于阅读,便于查错,而且也有利于程序正确性的证明。反方:goto语句(yj)无害,应该保留:goto语句使用起来比较灵活,而且有些情形能够提高程序的效率。如果一味强调删除goto语句,有些情形反而会使程序过于复杂,增加一些不必要的计算量。第50页/共52页第五十页,共53页。关于 Goto 语句的讨论(toln)D
66、onald E. Knuth(高德纳)1974年,D.E.Knuth对于goto语句的争论作了全面的公正的评述:不加限制地使用goto语句,特别是使用往回跳的goto语句,会使程序的结构难于理解,这种情形应该尽量避免使用goto语句;为了提高程序的效率,同时又不破坏程序的良好结构,有控制(kngzh)地使用一些goto语句是有必要的。“有些情形(qng xing),主张废除转向语句,有些情形(qng xing)我主张引进转向语句。”第51页/共52页第五十一页,共53页。感谢您的欣赏(xnshng)!第52页/共52页第五十二页,共53页。内容(nirng)总结第一节 for语句。(1)执行“控制变量初始化语句”,使控制变量获得一个初值。(3)控制变量从7变到77,增量为7。5、按字母表的顺序,从字母A到Z顺序打印输出。研究对象就是经典的“A+B”问题:输入若干对整数,输出每对之和。factorial=(factorial*j%MOD)。这个(zh ge)时间除以常数CLOCKS_PER_SEC之后得到的值以“秒”为单位。4、任给一个自然数n,求出这个(zh ge)自然数不同因数的个数第五十三页,共53页。