《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页。
