《NOIP循环结构的程序设计.ppt》由会员分享，可在线阅读，更多相关《NOIP循环结构的程序设计.ppt（43页珍藏版）》请在三一办公上搜索。
1、第四章 循环结构,第一节 循环语句（FOR语句）第二节 当语句（WHILE语句）第三节 直到循环（REPEAT语句）第四节 多重循环结构,在实际应用中，会经常遇到许多有规律性的重复运算，这就需要掌握本章所介绍的循环结构程序设计。在Pascal语言中，循环结构程序通常由三种的循环语句来实现。它们分别为FOR循环、当循环和直到循环。通常将一组重复执行的语句称为循环体，而控制重复执行或终止执行由重复终止条件决定。重复语句是由循环体及重复终止条件两部分组成。,第一节 循环语句（FOR语句）,for语句的一般格式,for:=to do;/递增型循环for:=downto do;/递减型循环其中for、t
2、o、downto和do是Pascal保留字。表达式1 与表达式2的值称为初值和终值。循环的语句格式：FOR 变量名:=初值 TO 终值 DO 语句；求1+2+3+N的和。如何编程呢？【例】S：=0；FOR I：=1 TO 10 DO S：=S+I；Writeln（S=，S）；,For语句执行过程,先将初值赋给左边的变量（称为循环变量）；判断循环变量的值是否“等于”终值，如已等于终值，则下次不再执行（本次是最后一次执行，循环变量的值也不更改），则跳到步骤；如果小于等于终值，则执行do后面的那个语句（称为循环体）；循环变量递增（对to）或递减（对downto)；返回步骤；循环结束，执行for循环下
3、面的一个语句。,说明,循环变量必须是顺序类型。可以是整型、字符型、枚举型等，但不能为实型。循环变量的值递增或递减的规律是：选用to则为递增；选用downto则递减。循环体可以是一个基本语句，也可以是一个复合语句。循环变量的初值和终值一经确定，循环次数就确定了。但是在循环体内对循环变量的值进行修改，常常会使得循环提前结束或进入死环。所以禁止在循环体中随意修改控制变量的值。如：for i:=1 to 10 dobegin i:=2*i+1;/禁止类似的修改，Free Pascal中会提示语法错误 writeln(i);end;以上for循环是一个死循环，i永远等于2，不可能达到终止值10。for语
4、句中的初值、终值都可以是顺序类型的常量、变量、表达式。,应用举例,例4.1 输出1100之间的所有偶数。程序如下：Program ex4_1;var i:integer;begin for i:=1 to 100 do if i mod 2=0 then write(i:5);end.,例4.2 编程计算1到100的累加和：s=1+2+3+100。【分析】设i为循环控制变量，累加和放在s中，利用循环变量i的值从1变化到100的规律，不需要另外引进从1变化到100的其它变量，程序的流程图如4-2所示。程序如下：Program ex4_2;var s,i:integer;begin s:=0;fo
5、r i:=1 to 100 do s:=s+i;writeln(s);end.运行结果：5050只要对程序稍加修改就可以计算出以下算式的值：s=1+1/2+1/3+1/100 s=12+22+32+1002 s=2+4+6+100等等。,例4.3 将顺序打印出26个小写英文字母:abczzcba。程序如下：Program ex4_3;var k:char;begin for k:=a to z do write(k);for k:=z downto a do write(k);writeln;end.,例4.4 N的阶乘是指1到N的累乘，即N！=1*2*3*N，输入一个数，求这个数的阶乘？程序
6、如下：Program ex4_4;var n,i:integer；/i为循环变量 s:longint;/s存放阶乘的结果，类型为长整 型，防止结果太大beginreadln(n);s:=1;/这条语句少了，选手们思考一 下，会出现什么现象?for i:=2 to n do/从2到n累乘到s中s:=s*i;writeln(s);/输出n!的值end.虽然s定义成longint，但输入12以上的数时，还是会出现错误的结果，说明结果超出了longint能够储存的范围，这时需要定义更大的类型，如int64，或干脆定义成实型变量用科学计数法来近似表示这个数，如real、extended。,上例中用到了“
7、递推”算法。所谓递推算法是指在一个数的序列值中，下一项的值在前一项的值的基础上推算出来的，即下一项对前一项有某种依赖关系。例如，为求5!，应先知道4!的值，然后再乘以5；为求6!必先求出5！。也就是说，从1！可以推出2！，从2！可以推出3！，从3！可以推出4！，以此类推。求n!的递推公式为：a1=1(n=1)an=n*an-1(n1)a1=1是“初始条件”或“边界条件”。只要找出递推关系，就可以由循环来处理，一项一项地推算出来以后各项。在程序中用同一个变量s来存储每一次推出来的值，由前一个s推出后一个s是递推。,例4.5 已知一对兔子，每个月可以生一对小兔，而小兔经过一个月生长后也可每月生一对
8、小兔。即兔子的对数是：第一个月1对，第二个月2对，第三个月3对，第四个月5对，假设兔子的生育期是12个月，并且不死，问一年后，这对兔子有多少对活着的后代？【分析】根据题目给出的条件，得到算法：设当前月兔子有x对，它的前一个月有lastx对，前二个月有prevx对，明显存在一个递推关系，即x=lastx+prevx。Program ex4_5;Var i,lastx,prevx,x:integer;begin prevx:=1;lastx:=2;for i:=3 to 12 do begin x:=lastx+prevx;prevx:=lastx;lastx:=x;end;writeln(x);
9、end.,运行结果：233,例4.6 一个两位数x，将它的个位数字与十位数字对调后得到一个新数y，此时y恰好比x大36，请编程求出所有这样的两位数。【分析】用for循环列举出所有的两位数，x为循环变量；用公式a:=x div 10分离出x的十位数字；用公式b:=x mod 10分离出x的个位数字；用公式y:=b*10+a合成新数y；用式子y-x=36筛选出符合条件的数x并输出。Program ex4_6;var a,b,x,y:integer;begin for x:=10 to 99 do begin a:=x div 10;b:=x mod 10;y:=b*10+a;if y-x=36 t
10、hen writeln(x);end;readln;end.,例4.7 把整数3025从中剪开分为30和25两个数，此时再将这两数之和平方，(30+25)2=3025计算结果又等于原数。求所有符合这样条件的四位数。【分析】设符合条件的四位数为N，它应当是一个完全平方数，用(a*a)表示。为了确保N=(a*a)在四位数（10009999）范围内，可确定a在3299循环；计算N=a*a；将四位数N拆分为两个数n1和n2；若满足条件(n1+n2)*(n1+n2)N 就输出 N。Program ex4_8；Var n,a,x,n1,n2:integer；begin for a:=32 to 99 do
11、 begin n:=a*a；n1:=n div 100；/拆取四位数的前两位数 n2:=n-n1*100；/拆取四位数的后两位数 x:=n1+n2；if x*x=N then writeln(N)；end；readlnend.,例4.9 根据公式2/6=1+1/22+1/32+1/n2，计算圆周率的pai值。【分析】此题是上例的一个变例，关键在于求出右边的累加和，变量n由键盘输入，n越大，圆周率的pai值就越精确。但是，i作为循环控制变量参加循环体的运算，它是整型数，那么当i=182时，i*i已经超过了正整数32767的范围，在Pascal系统里就把它变为-65536+i*i的整型数进行处理，
12、当i=256时，-65536+i*i正好等于零，从面产生以零作除数的编译错误，所以我们在程序里应该把i定义为长整型，这样可以输入更大的n(不能大于46341，等于65536时，也会同样出现被0除的溢出错误)。Program ex4_9;var i,n:integer;/应该为longint(长整型)pai,s:real;begin readln(n);s:=0;for i:=1 to n do s:=s+1/(i*i)pai:=sqrt(6*s);writeln(pai:8:6);end.,运行结果：输入：1000输出：3.132077输入：10000输出：3.141497,【上机练习4.1】
13、,1、求12+22+32+10022、求s=1+1/2+1/3+1/1003、计算100之内所有的奇数之和。4、计算n！，其中n由键盘输入。5、求10个数中的最大值和最小值。6、按字母表的顺序，从字母A到Z顺序打印输出。7、求菲波拉契数列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,第二节 当语句（WHILE语句）,WHILE循环,对于for循环有时也称为计数循环，当循环次数未知，只能根据某一条件来决定是否进行循环时，用while 语句或repeat语句实现循环要更方便。while语句的形式
14、为：while do；其意义为：当布尔表达式的值为true时，执行do后面的语句。,while语句的执行过程为：判断布尔表达式的值,如果其值为真,执行步骤2,否则执行步骤4;执行循环体语句(do后面的语句);返回步骤1;结束循环,执行while的下一个语句。说明：这里while和do为保留字。当布尔表达式成立时，执行do后面的语句(循环体)，当布尔表达式的值为false时，才结束循环，转去执行while语句的下一条语句，故又称此语句为“当”语句或“当型循环”。while语句的特点是：先判断，后执行。,例4.10 求恰好使s=1+1/2+1/3+1/n的值大于10时n的值。【分析】恰好使s的值大
15、于10意思是当表达式s的前n-1项的和小于或等于10，而加上了第n项后s的值大于10。从数学角度，我们很难计算这个n的值。故从第一项开始，当s的值小于或等于10时，就继续将下一项值累加起来。当s的值超过10时，最后一项的项数即为要求的n。程序如下：Program ex4_10；Var s:real;n:integer;/n表示项数begin s:=0.0;n:=0;while s=10 do/当s的值还未超过10时beginn:=n+1;/项数加1s:=s+1/n;/将下一项值累加到send;writlen(n=,n);/输出结果end.,例4.11 求两个正整数m和n的最大公约数。【分析】求
16、两个正整数的最大公约数采用的辗转相除法求解。以下是辗转的算法：分别用m,n,r表示被除数、除数、余数。求m/n的余数r.若r=0,则n为最大公约数.若r0,执行第步.将n的值放在m中,将r的值放在n中.返回重新执行第步。程序如下:program ex4_11;Var m,n,a,b,r:integer;begin write(Input m,n:);readln(m,n);a:=m;b:=n;r:=a mod b;while r0 do begin a:=b;b:=r;r:=a mod b;end;writeln(The greatest common divide is:,b:8);end.
17、,例4.12 利用格里高公式求。/4=1-1/3+1/5-1/7+，直到最后一项的值小于10-6为止。【分析】解本题的关键就是求右边数值序列的和，序列有明显的特点：分母是从1开始的奇数，加、减号轮流出现，因此，我们可以用n=n+2表示序列数值的变化，用f=-f来设置它们知项的符号位。程序如下：Program ex4_12;Var n,f:integer;t,pai:real;begin pai:=0;t:=1;n:=1;f:=1;while abs(t)=1e-6 do begin pai:=pai+t;n:=n+2;f:=-f;t:=f/n;end;pai:=pai*4;writeln(pa
18、i:10:8);end.,运行程序会发现没有结果，为什么？因为布尔表达式abs(t)=1e-6，即1/n=1e-6，而程序的说明部分n是整型数，它的范围是-3276832767，条件永远成立，所以形成死循环，从而没有运行结果。while循环不需要用顺序型数据来控制循环的次数，改程序的说明部分中的n为实型数或说明为长整型即可，请同学们自己修正，以后要对变量的取值范围引起重视。,【上机练习4.2】,1、用WHILE循环完成如下3题：求s=1+2+3+4+10 求s=1+1/2+1/3+1/100 计算n！，其中n由键盘输入。2、输入任一的自然数A,B,求A,B的最小公倍数。3、小球从100高处自由
19、落下,着地后又弹回高度的一 半再落下。求第20次着地时,小球共通过多少路程?4、Faibonacci数列前几项为:0,1,1,2,3,5,8,其规 律是从第三项起,每项均等于前两项之和。求前30 项,并以每行5个数的格式输出。5、鸡兔同笼,头30,脚90,求鸡兔各几只？,第三节 直到循环（REPEAT语句）,用while语句可以实现“当型循环”，用repeat-until 语句可以实现“直到型循环”。repeat-until语句的含义是：“重复执行循环，直到指定的条件为真时为止”。直到循环语句的一般形式:Repeat;:;until;其中Repeat、until是Pascal保留字，repea
20、t与until之间的所有语句称为循环体。,说明：repeat语句的特点是：先执行循环，后判断结束条件，因而至少要执行一次循环体。repeat-until是一个整体，它是一个（构造型）语句，不要误认为repeat是一个语句，until是另一个语句。repeat语句在布尔表达式的值为真时不再执行循环体，且循环体可以是若干个语句，不需用begin和end把它们包起来，repeat 和until已经起了begin和end的作用。while循环和repeat循环是可以相互转化的。,例4.13 求两个正整数m和n的最大公约数。程序采用repeat-until循环实现。Program ex4_13;var
21、m,n,r:integer;begin readln(m,n);repeat/辗转相除法 r:=m mod n;m:=n;n:=r;until r=0;writeln(m);end.,例4.14 校体操队到操场集合,排成每行2人,最后多出1人;排成每行3人,也多出1人;分别按每行排4,5,6人,都多出1人;当排成每行7人时,正好不多。求校体操队至少是多少人?【分析】设校体操队为X人,根据题意X应是7的倍数,因此X的初值为7,以后用inc(x,7)改变X值；为了控制循环,用逻辑变量yes为真(True)使循环结束；如果诸条件中有一个不满足,yes 的值就会为假(false)，就继续循环。Prog
22、ram ex4_14;var x:integer;yes:boolean;begin x:=0;repeat yes:=true;inc(x,7);if x mod 2 1 then yes:=false;if x mod 3 1 then yes:=false;if x mod 4 1 then yes:=false;if x mod 5 1 then yes:=false;if x mod 6 1 then yes:=false;until yes;/直到yes的值为真 writeln(All=,x);readlnend.程序中对每个X值，都先给Yes 赋真值，只有在循环体各句对X进行判断
23、时，都得到“通过”（此处不赋假值）才能保持真值。,例4.15 求1992个1992的乘积的末两位数是多少？【分析】积的个位与十位数只与被乘数与乘数的个位与十位数字有关，所以本题相当于求1992个92相乘，而且本次的乘积主下一次相乘的被乘数，因此也只需取末两位参与运算就可以了。Program ex4_15;var a,t:integer;Begin a:=1;t:=0;repeat t:=t+1;a:=(a*92)mod 100;until t=1992;writeln(a);Readln;End.,例4.16 利用格里高公式求。/4=1-1/3+1/5-1/7+，直到最后一项的值小于10-6为
24、止.【分析】解本题的关键就是求右边数值序列的和，序列有明显的特点：分母是从1开始的奇数，加、减号轮流出现，因此，我们可以用m=n+2表示序列数值的变化，用f=-f来设置它们知项的符号位。Program ex4_16;var f:integer;n,t,pai:real;begin pai:=0;t:=1;n:=1;f:=1;repeat pai:=pai+t;n:=n+2;f:=-f;t:=f/n;until abs(t)1e-6;pai:=pai*4;writeln(pai:10:8);end.运行结果：3.14159066,以上我们已介绍了三种循环语句。一般说来，用for 循环比较简明，只
25、要能用for循环，就尽量作用for循环。只在无法使用for循环时才用while循环和repeat-until循环，而且 while 循环和repeat-until循环是可以互相转化的，具体用哪个，还要看个人喜好，但他们也存在细微区别，那就是while语句的循环体有可能一次都不会被执行，而repeat语句中循环体至少执行一次。for 循环在大多数场合也能用while和repeat-until循环来代替。一般for循环用于有确定次数循环，而while和repeat-until循环用于未确定循环次数的循环。,【上机练习4.3】,1、用REPEAT循环完成如下3题：求s=1+2+3+4+10 求s=1
26、+1/2+1/3+1/100 计算n！，其中n由键盘输入。2、读一组实数,遇零终止,打印其中正、负数的个数 及各自的总和。3、用辗转相除法求两个自然数的最大公约数。4、找出被2、3、5除时余数为1的最小的十个数。5、将一根长为369cm的钢管截成长为69cm和39cm 两种规格的短料。在这两种规格的短料至少各截 一根的前提下,如何截才能余料最少。,第四节 多重循环结构,当一个循环的循环体中又包含循环结构程序时，我们就称之为循环嵌套。内循环整个作为外循环的一条语句。,例4.17 求1!+2!+10!的值。【分析】这个问题是求10自然数的阶乘之和，可以用for 循环来实现。程序结构如下：for n
27、:=1 to 10 do begin N!的值t 累加N!的值s end显然,通过10次的循环可求出1!,2!,10!,并同时累加起来,可求得S的值。而求T=N!,又可以用一个for循环来实现:因此,整个程序为:program ex4_17;var t,s:longint;i,j,n:integer;begin S:=0;for n:=1 to 10 do begin t=1;for j:=1 to n do/求n!t:=t*j;S:=S+t;/累加n!end;writeln(s=,s:0:0);end.,以上的程序是一个二重的for循环嵌套。这是比较好想的方法，但实际上对于求n!，我们可以根
28、据求出的(n-1)!乘上n即可得到，而无需重新从1再累乘到n。程序可改为：program ex4_17;var t,s:longint;i,j,n:integer;begin s:=0;t:=1;for n:=1 to 10 do begin t:=t*n;/t为上一个数的n-1的阶乘值，再乘以n即为n!s:=s+t;/累加n!end;writeln(s=,s:0:0);end.显然第二个程序的效率要比第一个高得多。第一程序要进行1+2+10=55次循环，而第二程序进行10次循环。如题目中求的是1！2！1000！，则两个程序的效率区别更明显。,例4.18 一个炊事员上街采购,用500元钱买了9
29、0只鸡,其中母鸡一只15元,公鸡一只10元,小鸡一只5元,正好把钱买完。问母鸡、公鸡、小鸡各买多少只？【分析】设母鸡I只,公鸡J只,则小鸡为90-I-J只,则15*I+10*J+(90-I-J)*5=500,显然一个方程求两个未知数是不能直接求解。必须组合出所有可能的i,j值，看是否满足条件。这里I的值可以是0到33，J的值可以0到50。源程序如下：programr ex4_18;var i,j,k:integer;begin for i:=0 to 33 do/枚举母鸡的数量 for j:=0 to 50 do/枚举公鸡的数量 begin k:=90-i-j;if 15*i+10*j+5*k
30、=500 then writeln(i:5,j:5,k:5);end;end.,例4.19 求100999中的水仙花数。（若三位数ABC，ABC=A3+B3+C3，则称ABC为水仙花数。例如153，13+53+33=1+125+27=153，则153是水仙花数。）【分析】根据题意，采用三重循环来求解。由于循环次数一定，用for循环最为简单。程序如下：Program ex4_19_1;var a,b,c:integer;begin for a:=1 to 9 do for b:=0 to 9 do for c:=0 to 9 do if a*a*a+b*b*b+c*c*c=a*100+b*10+
31、c then write(a*100+b*10+c:6);end.运行结果：153370371407,同时也可以采用一个for循环来求解，表面上看好像优于三重循环，实际上却比上面的程序效率低，请同学们自己分析。程序如下：Program ex4_19_2;var m,a,b,c:integer;begin for m:=100 to 999 do begin a:=m div 100;/m的百位 b:=(m mod 100)div 10;/m的十位 c:=m mod 10;/m的个位 if a*a*a+b*b*b+c*c*c=m then writeln(m:6);end;end;,例4.20
32、求100200之间的所有素数。【分析】我们可对100200之间的每一整数进行判断，判断它是否为素数，是则输出。而对于任意整数i，根据素数定义，我们从2开始，到，找i的第一个约数。若找到第一个约数，则i必然不是素数，否则i为素数。用for和while语句结合来编写。程序如下：programr ex4_20;var i,x:integer;begin for i:=100 to 200 do begin x:=2;while(x0)do/枚举2到之间的每个数 begin x:=x+1;/在枚举的范围内并且没有出现约数则继续枚举 end;if xtrunc(sqrt(i)then write(i:8
33、);end;end.,例4.21 试编写能够打印输出如下图形的程序：#程序如下：Program ex4_21;var i,j,k:integer;begin for i:=8 downto 1 do/总共要输出8行内容 begin for j:=1 to 8-i do write();/控制每行空格数目,这个循环可以写成：write(:8-i);for k:=2*i-1 downto 1 do write(#);/控制每行中的个数 writeln;end;end.此程序的设计是由两个并列循环加一个嵌套循环构成的。各环的作用如下：（1）外层环控制打印的行数，此倒三角形共8行，故外环的设置为递减型
34、循环。（2）嵌套在外环中的第一个并列循环为空格输出，根据图形变化控制输出不同数量的空格。（3）外环内第二个并列循环为控制三角形每行中#号的个数。,例4.22 验证哥德巴赫猜想：任一个充分大的偶数N（N=4），可以用两个素数之和表示。例如：4=2+26=3+38=3+598=17+79输入一个数，不是偶数则输出：“is not even.”，否则输出表示它的二个素数。【分析】哥德巴赫猜想是一个古老而著名的数学难题，它的理论证明很麻烦，迄今未得出最后证明。在这方面我国数学家陈景润的研究成果处于世界领先地位。这里只对有限范围内的数用计算机加以验证，不算严格的证明。充分大的偶数用N表示，将它分成P和Q
35、，使NP+Q。P从1开始（每次加1），QN-P。若P、Q均为素数，则输出结果，否则以P+1再试。,Program ex4_22;var n,p,q,j:integer;flagp,flagq:boolean;begin readln(n);if n mod 2=0 then/输入的是偶数 begin p:=1;/p从1开始枚举 repeat p:=p+1;q:=n-p;/n=p+q flagp:=true;/查看当前的p是不是素数 for j:=2 to trunc(sqrt(p)do if(p mod j)=0 then flagp=false;flagq:=true;/查看当前的q是不是素
36、数 for j:=2 to trunc(sqrt(q)do if q mod j=0 then flagq:=false;until flagp and flagq;/直到所枚举的p、q是素数为止 writeln(p,q);end else writeln(is not even.);/输入不是偶数的情况end.,【上机练习4.4】,1、求s=11+22+33+.+NN 2、求s=1+1/2!+1/3!+1/10!3、输入一个整数，若是素数，输出“YES”，否则输出“NO”4、任给一个自然数n，求出这个自然数不同因数的个数。如：n=6时，因为1，2，3，6这四个数均是6的因数，故输出为 tot
37、al=4。5、输入一列图形（字母金字塔）a a b a b c.a b c y z6、把一张一元钞票换成一分，二分和五分的硬币，每种至少一枚。问有哪几种换法？7、百鸡问题：一只公鸡值5元，一只母鸡值3元，而1元可买3只小鸡。现有100元钱，想买100只鸡。问可买公鸡、母鸡、小鸡各几只？,8、某人想将手中的一张面值100元的人民币换成10元、5元、2元和1元面值的票子。要求换正好40张，且每种票子至少一张。问：有几种换法？应适当考虑减少重复次数。9、有一堆100多个的零件，若三个三个数，剩二个；若五个五个数，剩三个；若七个七个数，剩五个。请你编一个程序计算出这堆零件至少是多少个？10、编写一程序，验证角谷猜想。所谓的角谷猜想是：“对于任意大于1的自然数n，若n为奇数，则将n变为3*n+1，否则将n变为n的一半。经过若干次这样的变换，一定会使n变为1。”11、输入二个正整数，求出它们的最大公约数和最小公倍数。12、求1-100之间的所有素数（素数是大于1，且除1和它本身外，不能被任何其它整数所整除的整数）。13、哥德巴赫猜想（任何充分大的偶数都可由两个素数之和表示）。将4-100中的所有偶数分别用两个素数之和表示。输出为：4=2+26=3+3.100=3+97,
