信息学奥赛培训材料

一、IF语句的嵌套

在if语句中，如果then子句或else子句仍是一个if语句， 则称为if语句的嵌套。 例1 计算下列函数 Y=1 (x>0) =0 (x=0) =-1(x<0)

分析：根据输入的x值，先分成x>0与x≤0两种情况，然后对于情况x≤0，再区分x是小于0，还是等于0。 源程序如下: program ex; var

x:real; y:integer; begin

wrtie('Input x:');readln(x);

if x>0 then y:=1｛x>0时，y的值为1｝ else ｛x≤0时｝ if x=0 then y:=0 else y:=-1;

writeln('x=',x:6:2,'y=',y); end.

显然，以上的程序中，在then子句中嵌套了一个Ⅱ型if语句。当然程序也可以写成如下形式：

program ex; var

x:real;y:integer; begin

wrtie('Input x:');readln(x); if x>=0 then

if x>0 then y:=1 else y:=0 else y=-1;

writeln('x=',x:6:2,'y=',y); end.

但是对于本题，下面的程序是不对的。 y:=0;

if x>=0 then

if x>0 then y:=1 else y:=-1;

明显，从此人的程序书写格式可以看出，他想让else与第一个if配对，而事实上，这是错的。因为pascal规定：else与它上面的距它最近的then配对,因此以上程序段的逻辑意义就与题义不符。

要使上程序段中esle与第一个then配对,应将程序段修改为： y:=0; 或者 y:=0; if x>=0 if x>=0 then if x>0 then then y:=1 begin

else if x>0 then Y:=1; else y:=-1; end

else Y:=-1; 二、case语句

上面我们知道可以用嵌套的if语句实现多分支的选择结构。但是如果分支越来越多时，用嵌套的if语句实现多分支就显得繁杂。当多分支选择的各个条件由同一个表达式的不同结果值决定时，可以用case语句实现。它的选择过程，很象一个多路开关，即由case语句的选择表达式的值，决定切换至哪一语句去工作。因此在分支结构程序设计中，它是一种强有力的手段。在实现多路径分支控制时，用case对某些问题的处理和设计，比用if语句写程序具有更简洁、清晰之感。

(一)、情况语句的一般形式： case <表达式> of

<情况标号表1>：语句1; <情况标号表2>：语句2; :

<情况标号表n>：语句n end;

其中case、of、end是Pascal的保留字， 表达式的值必须是顺序类型，它可以是整型、布尔型及以后学习的字符型、枚举型和子界型。情况标号表是一串用逗号隔开的与表达式类型一致的常量序列。语句可以是任何语句，包括复合语句和空语句。

(二)、case语句的执行过程

先计算表达式（称为情况表达式）的值，如果它的值等于某一个常量（称为情况常量，也称情况标号），则执行该情况常量后面的语句，在执行完语句后，跳到case语句的末尾end处。

(三)、说明

①情况表达式必须是顺序类型的；

②情况常量是情况表达式可能具有的值，因而应与情况表达式具有相同的类型； ③情况常量出现的次序可以是任意的；

④同一情况常量不能在同一个case语句中出现两次或两次以上； ⑤每个分语句前可以有一个或若干个用逗号隔开的情况常量；

⑥如果情况表达式的值不落在情况常的范围内，则认为本case语句无效，执行case语

句的下一个语句。turbo pascal中增加了一个\"否则\"的情况,即增加一个else子句，但也是可省的。

⑦每个常量后面只能是一个语句或一个复合语句。

例2 根据x的值，求函数Y的值：

分析：利用case语句进行程序设计, 关键在于巧妙地构造情况表达式。本例中三种情况可用一个表达式区分出来：Trunc(x/100)。因为x在(0～100)之间时表达式值为0；x在[100,200)时表达式值为1 ；其余部分可用else子句表示。

源程序如下: program ex; var x,y:real; begin

write('Input x:');readln(x); case trunc(x/100) of 0:y:=x+1; 1:y:=x-1; else y:=0;

end;{end of case}

writeln('x=',x:8:2),'y=',y:8:2); end.

三、选择结构的程序设计

例3 输入一个年号,判断它是否是闰年。

分析：判断闰年的算法是：如果此年号能被400除尽， 或者它能被4整除而不能被100整除，则它是闰年。否则，它是平年。

源程序如下: program ex; var year:integer; begin

write('Input year:');readln(year); write(year:6);

if (year mod 400=0 ) then writeln('is a leap year.') else

if (year mod 4=0)and(year mod 100<>0) then writeln('is a leap year.') else writeln('is not a leap year.'); end.

例4 判断1995年,每个月份的天数。

分析：程序分为:输入月份,计算该月的天数,输出天数

源程序如下： program days;

var month,days:integer; begin

write('Input month:');readln(month); case month of

1,3,5,7,8,10,12:days:=31; 4,6,9,11 :days:=30; 2 :days:=28; else days:=0; end;

if days<>0 then writeln('Days=',days); end.

例5 期未来临了，班长小Q决定将剩余班费X元钱，用于购买若干支钢笔奖励给一些学习好、表现好的同学。已知商店里有三种钢笔，它们的单价为6元、5元和4元。小Q想买尽量多的笔（鼓励尽量多的同学），同时他又不想有剩余钱。请您编一程序，帮小Q制订出一种买笔的方案。 分析：对于以上的实际问题，要买尽量多的笔，易知都买4元的笔肯定可以买最多支笔。因此最多可买的笔为x div 4支。由于小q要把钱用完，故我们可以按以下方法将钱用完： 若买完x div 4支4元钱的笔，还剩1元，则4元钱的笔少买1支，换成一支5元笔即可；若买完x div 4支4元钱的笔，还剩2元，则4元钱的笔少买1支，换成一支6元笔即可；若买完x div 4支4元钱的笔，还剩3元，则4元钱的笔少买2支，换成一支5元笔和一支6元笔即可。

从以上对买笔方案的调整，可以看出笔的数目都是x div 4，因此该方案的确为最优方案。

源程序如下： program pen;

var a,b,c:integer;{a,b,c分别表示在买笔方案中，6元、5元和4元钱笔的数目} x,y:integer;{x，y分别表示剩余班费和买完最多的4元笔后剩的钱} begin

write('x=');readln(x){输入x}

c:=x div 4;{4元笔最多买的数目}

y:=x mod 4;｛求买完c支4元笔后剩余的钱数y｝ case y of

0 : begin a:=0;b:=0; end;

1 : begin a:=0;b:=1;c:=c-1; end; 2 : begin a:=1;b:=0; c:=c-1;end; 3 : begin a:=1;b:=1; c:=c-2;end; end;

writeln('a=',a,'b=',b,'c=',c); end. 练 习

1．输入三角形的三个边，判断它是何类型的三角形（等边三角形？等腰三角形？一般三角形？）。

2．输入三个数，按由大到小顺序打印出来。

3．计算1901年2099年之间的某月某日是星期几。

循环程序设计(2次)

一、计数循环（For循环） 在实际应用中，会经常遇到许多有规律性的重复运算，这就需要掌握本章所介绍的循环结构程序设计。在Pascal语言中，循环结构程序通常由三种的循环语句来实现。它们分别为FOR循环、当循环和直到循环。通常将一组重复执行的语句称为循环体，而控制重复执行或终止执行由重复终止条件决定。因此，重复语句是由循环体及重复终止条件两部分组成。 For语句的格式

for <控制变量>:=<表达式1> to <表达式2> do <语句>;

for <控制变量>:=<表达式1> downto <表达式2> do <语句>;

其中for、to、downto和do是Pascal保留字。表达式1 与表达式2的值也称为初值和终值。

For语句执行过程

①先将初值赋给左边的变量（称为循环控制变量）；

②判断循环控制变量的值是否已\"超过\"终值，如已超过，则跳到步骤⑥； ③如果末超过终值，则执行do后面的那个语句（称为循环体）； ④循环变量递增（对to）或递减（对downt o）１； ⑤返回步骤②；

⑥循环结束，执行ｆｏｒ循环下面的一个语句。 说明

①循环控制变量必须是顺序类型。例如，可以是整型、字符型等，但不能为实型。 ②循环控制变量的值递增或递减的规律是：选用to则为递增；选用downto则递减。 ③所谓循环控制变量的值\"超过\"终值，对递增型循环，\"超过\"指大于，对递减型循环，\"超 过\"指小于。

④循环体可以是一个基本语句，也可以是一个复合语句。 ⑤循环控制变量的初值和终值一经确定，循环次数就确定了。但是在循环体内对循环变量的值进行修改，常常会使得循环提前结束或进入死环。建议不要在循环体中随意修改控制变量的值。

⑥for语句中的初值、终值都可以是顺序类型的常量、变量、表达式。

应用举例

例1．输出1－100之间的所有偶数。 var i:integer; begin

for i:=1 to 100 do

if i mod 2=0 then write(i:5); end.

例2．求N！＝1＊2＊3＊…＊N ，这里N不大于10。 分析：程序要先输入N，然后从1累乘到N。 程序如下： var

n,i : integer；｛i为循环变量｝ S : longint;｛s作为累乘器｝ begin

write('Enter n=');readln(n);{输入n} s:=1;

for i:=2 to n do｛从2到n累乘到s中｝ s:=s*i;

writeln(n,'!=',s);｛输出n!的值｝ end.

练 习

1． 求s=1+4+7+…+298的值。

2． 编写一个评分程序，接受用户输入10个选手的得分(0-10分)，然后去掉一个最高分和一个最低分，求出某选手的最后得分(平均分)。

3． 用一张一元票换1分、2分和5分的硬币，每种至少一枚， 问有哪几种换法（各几枚）？

二、当型循环（while循环）

对于for循环有时也称为计数循环，当循环次数未知，只能根据某一条件来决定是否进行循环时，用while 语句或repeat语句实现循环要更方便。 while语句的形式为：

while <布尔表达式> do <语句>；

其意义为：当布尔表达式的值为true时，执行do后面的语句。 while语句的执行过程为：

①判断布尔表达式的值,如果其值为真,执行步骤2,否则执行步骤4; ②执行循环体语句(do后面的语句); ③返回步骤1;

④结束循环,执行while的下一个语句。

说明：这里while和do为保留字，while语句的特点是先判断，后执行。 当布尔表达式成立时，重复执行do后面的语句(循环体)。

例1 、求恰好使s=1+1/2+1/3+…+1/n的值大于10时n的值。

分析：\"恰好使s的值大于10\"意思是当表达式s的前n-1项的和小于或等于10，而加上了第n项后s的值大于10。从数学角度，我们很难计算这个n的值。故从第一项开始，当s的值小于或等于10时，就继续将下一项值累加起来。当s的值超过10时，最后一项的项数即为要求的n。 程序如下： var

s : real;

n : integer;｛n表示项数｝ begin

s:=0.0;n:=0;

while s<=10 do｛当s的值还未超过10时｝ begin

n:=n+1;｛项数加1｝

s:=s+1/n;｛将下一项值累加到s｝ end;

writlen('n=',n);｛输出结果｝ end.

例2、求两个正整数m和n的最大公约数。

分析：求两个正整数的最大公约数采用的辗转相除法求解。以下是辗转的算法： 分别用m,n,r表示被除数、除数、余数。 ①求m/n的余数r.

②若r=0,则n为最大公约数.若r≠0,执行第③步. ③将n的值放在m中,将r的值放在n中. ④返回重新执行第①步。 程序如下:

program ex4_4;

var m,n,a,b,r:integer; begin

write('Input m,n:'); readln(m,n);

a:=m;b:=n;r:=a mod b; while r<>0 do begin

a:=b;b:=r; r:=a mod b; end;

writeln('The greatest common divide is:',b:8); end.

三、直到循环（REPEAT－until循环）

用while语句可以实现\"当型循环\"，用repeat-until 语句可以实现\"直到型循环\"。

repeat-until语句的含义是：\"重复执行循环，直到指定的条件为真时为止\"。 直到循环语句的一般形式: Repeat

<语句1>; :

<语句n>;

until <布尔表达式>;

其中Repeat、until是Pascal保留字，repeat与until之间的所有语句称为循环体。 说明：

①repeat语句的特点是：先执行循环，后判断结束条件，因而至少要执行一次循环体。 ②repeat-until是一个整体，它是一个（构造型）语句，不要误认为repeat是一个语句， until是另一个语句。

③repeat语句在布尔表达式的值为真时不再执行循环体，且循环体可以是若干个语句，不需用begin和end把它们包起来， repeat 和until已经起了begin和end的作用。while循环和repeat循环是可以相互转化的。

对于例2中求两个正整数的最大公约数，程序可用repeat-until循环实现如下： var

m,n,a,b,r : integer; begin

write('Input m,n='); readln(m,n); a:=m;b:=n; repeat

r:=a mod b; a:=b;b:=r; until r=0;

writeln('The greatest common divide is',a); end.

以上我们已介绍了三种循环语句。一般说来，用for 循环比较简明，只要能用for循环，就尽量作用for循环。只在无法使用for循环时才用while循环和repeat-until循环， 而且 while 循环和repeat-until循环是可以互相替代的。for 循环在大多数场合也能用whiel和repeat-until循环来代替。一般for循环用于有确定次数循环，而while和repeat-until循环用于未确定循环次数的循环。

当一个循环的循环体中又包含循环结构程序时，我们就称之为循环嵌套。 三、循环结构程序设计

例3 求1!+2!+…+10!的值。

分析：这个问题是求10自然数的阶乘之和，可以用for 循环来实现。程序结构如下： for n:=1 to 10 do begin

①N!的值àt ②累加N!的值t end

显然,通过10次的循环可求出1!,2!…,10!,并同时累加起来, 可求得S的值。而求T=N!,

又可以用一个for循环来实现: t=1;

for j:=1 to n do t:=t*j;

因此,整个程序为: program ex4_5; var t,s:real;

i,j,n:integer; begin S:=0;

for n:=1 to 10 do begin t:=1;

for j:=1 to n do t:=t*j; S:=S+t; end;

writeln('s=',s:0:0); end.

以上的程序是一个二重的for循环嵌套。这是比较好想的方法，但实际上对于求n!，我们可以根据求出的(n-1)!乘上n即可得到，而无需重新从1再累乘到n。 程序可改为： program ex4_5; var t,s:real;

i,j,n:integer; begin

S:=0;t:=1;

for n:=1 to 10 do begin t:=t*n; S:=S+t; end;

writeln('s=',s:0:0); end.

显然第二个程序的效率要比第一个高得多。第一程序要进行1+2+…+10=55次循环，而第二程序进行10次循环。如题目中求的是1！＋2！＋…＋1000！，则两个程序的效率区别更明显。

例4 一个炊事员上街采购,用500元钱买了90只鸡, 其中母鸡一只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_6; var i,j,k:integer; begin

for i:=1 to 5 do for j:=1 to 8 do begin

k:=90-i-j;

if 15*i+10*j+5*k=500 then writeln(i:5,j:5,k:5); end; end.

例5、求100－200之间的所有素数。

分析：我们可对100－200之间的每一整数进行判断，判断它是否为素数，是则输出。而对于任意整数i，根据素数定义，我们从2开始，到 ，找i的第一个约数。若找到第一个约数，则i必然不是素数。否则i为素数。 源程序如下： var

i : integer; x : integer; begin

for i:=100 to 200 do begin x:=2;

while (x<=trunc(sqrt(i)))and(i mod x<>0)do begin x:=x+1; end;

if x>trunc(sqrt(i)) then write(i:8); end; end.

练 习

1、输入一个正整数n，将n分解成质因数幂的乘积形式。 例如：36=22*32

2、编写一程序，验证角谷猜想。所谓的角谷猜想是：\"对于任意大于1的自然数n，若n为奇数，则将n变为3*n+1，否则将n变为n的一半。经过若干次这样的变换，一定会使n变为1。\"

3．有一堆100多个的零件，若三个三个数，剩二个；若五个五个数，剩三个；若七个七个数，剩五个。请你编一个程序计算出这堆零件至少是多少个？

数 组

一维数组

一、为什么要使用数组

例1 输入50个学生的某门课程的成绩，打印出低于平均分的同学号数与成绩。

分析：在解决这个问题时，虽然可以通过读入一个数就累加一个数的办法来求学生的总分，进而求出平均分。但因为只有读入最后一个学生的分数以后才能求得平均分，且要打印出低于平均分的同学，故必须把50个学生的成绩都保留下来， 然后逐个和平均分比较，把高于平均分的成绩打印出来。如果，用简单变量a1，a2,…，a50存放这些数据，可想而知程序要很长且繁。

要想如数学中使用下标变量ai形式表示这50个数，则可以引入下标变量a[i]。这样问题的程序可写为：

tot:=0;{tot表示总分}

for i:=1 to 50 do ｛循环读入每一个学生的成绩，并累加它到总分｝ begin

read(a[i]); tot:=tot+a[i]; end;

ave:=tot/50;｛计算平均分｝ for i:=1 to 50 do

if a[i]二、一维数组

当数组中每个元素只带有一个下标时，我们称这样的数组为一维数组。

1、一维数组的定义 （1）类型定义

要使用数组类型等构造类型以及第6章要学习的自定义类型(枚举类型与子界类型)，应在说明部分进行类型说明。 这样定义的数据类型适用整个程序。 类型定义一般格式为： type

<标识符1>=<类型1>; <标识符2>=<类型2>; :

<标识符n>=<类型n>;

其中type是Pascal保留字,表示开始一个类型定义段。在其后可以定义若干个数据类型定义。<标识符>是为定义的类型取的名字, 称它为类型标识符。

类型定义后，也就确定了该类型数据取值的范围，以及数据所能执行的运算。

（2）一维数组类型的定义 一维数组类型的一般格式：

array[下标1..下标2] of <基类型>;

说明：其中array和of是pascal保留字。下标1和下标2 是同一顺序类型，且下标2的序号大于下标1的序号。它给出了数组中每个元素(下标变量) 允许使用的下标类型，也决定了数组中元素的个数。基类型是指数组元素的类型，它可以是任何类型，同一个数组中的元素具有相同类型。因此我们可以说，数组是由固定数量的相同类型的元素组成的。

再次提请注意：类型和变量是两个不同概念，不能混淆。就数组而言，程序的执行部分使用的不是数组类型（标识符）而是数组变量（标识符）。 一般在定义数组类型标识符后定义相应的数组变量，如： type arraytype=array[1..8]of integer; var a1,a2:arraytype;

其中arraytype为一个类型标识符,表示一个下标值可以是1到 8,数组元素类型为整型的一维数组；而a1,a2则是这种类型的数组变量。 也可以将其全并起来：

var a1,a2:array[1..8]of integer;

当在说明部分定义了一个数组变量之后,pascal 编译程序为所定义的数组在内存空间开辟一串连续的存储单元。

例如，设程序中有如下说明： type rowtype=array[1..8]of integer; coltype=array['a'..'e']of integer; var a:rowtype;b:coltype;

2、一维数组的引用

当定义了一个数组，则数组中的各个元素就共用一个数组名( 即该数组变量名)，它们之间是通过下标不同以示区别的。 对数组的操作归根到底就是对数组元素的操作。一维数组元素的引用格式为： 数组名[下标表达式]

说明：①下标表达式值的类型, 必须与数组类型定义中下标类型完全一致,并且不允许超越所定义的下标下界和上界。

②数组是一个整体，数组名是一个整体的标识，要对数组进行操作，必须对其元素操作。数组元素可以象同类型的普通变量那样作用。如:a[3]:=34;是对数组a中第三个下标变量赋以34的值。read(a[4]);是从键盘读入一个数到数组a第4个元素中去。 特殊地,如果两个数组类型一致,它们之间可以整个数组元素进行传送。如： var a,b,c:array[1..100] of integer; begin

c:=a;a:=b;b:=c; end.

在上程序中，a,b,c三个数组类型完全一致， 它们之间可以实现整数组传送，例子中，先将a数组所有元素的值依次传送给数组c，同样b数组传给a，数组c又传送给b，上程序段实际上实现了a,b 两个数组所有元素的交换。

对于一维数组的输入与输出, 都只能对其中的元素逐个的输入与输出。在下面的应用示例中将详细介绍。

三、一维数组应用示例

例2 输入50个数,要求程序按输入时的逆序把这50个数打印出来。也就是说，请你按输入相反顺序打印这50个数。

分析：我们可定义一个数组a用以存放输入的50个数, 然后将数组a内容逆序输出。 源程序如下： program ex5_1;

type arr=array[1..50]of integer; {说明一数组类型arr} var a:arr;i:integer; begin

writeln('Enter 50 integer:');

for i:=1 to 50 do read(a[i])；{从键盘上输入50个整数} readln;

for i:=50 downto 1 do {逆序输出这50个数} write(a[i]:10); end.

例3 输入十个正整数,把这十个数按由小到大的顺序排列。 将数据按一定顺序排列称为排序，排序的算法有很多，其中选择排序是一种较简单的方法。

分析：要把十个数按从小到大顺序排列，则排完后，第一个数最小，第二个数次小，……。因此，我们第一步可将第一个数与其后的各个数依次比较，若发现，比它小的，则与之交换，比较结束后，则第一个数已是最小的数（最小的泡往下冒）。同理，第二步，将第二个数与其后各个数再依次比较，又可得出次小的数。如此方法进行比较，最后一次，将第九个数与第十个数比较，以决定次大的数。于是十个数的顺序排列结束。

例如下面对5个进行排序，这个五个数分别为8 2 9 10 5。按选择排序方法，过程如下：

初始数据 ：8 2 9 10 5 第一次排序：8 2 9 10 5 9 2 8 10 5 10 2 8 9 5 10 2 8 9 5 第二次排序：10 8 2 9 5 10 9 2 8 5 10 9 2 8 5 第三次排序：10 9 8 2 5 10 9 8 2 5 第四次排序：10 9 8 5 2

对于十个数，则排序要进行9次。源程序如下： program ex5_2;

var a:array[1..10]of integer; i,j,t:integer; begin

writeln('Input 10 integers:');

for i:=1 to 10 do read(a[i]);｛读入10个初始数据｝ readln;

for i:=1 to 9 do｛进行9次排序｝ begin

for j:=i+1 to 10 do｛将第i个数与其后所有数比较｝ if a[i]t:=a[i];a[i]:=a[j];a[j]:=t; end; write(a[i]:5); end; end.

练习：

1．输入一串小写字母（以\".\"为结束标志），统计出每个字母在该字符串中出现的次数(若某字母不出现，则不要输出)。 例：

输入：aaaabbbccc. 输出：a:4 b:3 c:3

2．输入一个不大于32767的正整数N，将它转换成一个二进制数。 例如： 输入：100

输出： 1100100

3．输入一个由10个整数组成的序列，其中序列中任意连续三个整数都互不相同，求该序列中所有递增或递减子序列的个数。 例如：

输入：1 10 8 5 9 3 2 6 7 4 输出：6

对应的递增或递减子序列为： 1 10 10 8 5 5 9 9 3 2 2 6 7 7 4