广东省汕头市金山中学高中信息技术奥林匹克信息学竞赛班第五

1、数组【引例】输入20个数，将它们按从大到小的次序排序后输出。讨论：如果按我们前面学的知识，我们应设20个变量来存储这20个数，如果要排序的数不是20个，而是100个，那我们就应设100个变量？没这么笨吧，我们有更好的办法解决。§5.1 一维数组数组是由固定数量的相同类型的元素按一定顺序排列而成。只有一个下标类型的数组称为一维数组。1数组类型定义和说明类型定义的一般形式为： TYPE <类型标识符> = ARRAY 下标类型 OF <基类型>；数组说明： VAR <数组名> ：<数组类型标识符>；数组名是由用户定义的标识符，下标类型可以是

2、子界类型或枚举类型，下标规定了数组元素的个数和排列次序。基类型表示数组中每个元素的类型，它可以是任何数据类型，但同一数组中的元素类型必须相同。如： type A = array 1.20 of integer; B = array 0.50 of char; Var x , y : A; a : B;其中x、y被说明为A类型数据，即均为拥有20个元素的数组，下标从1到20，元素类型为整型；a被说明为B类型数据，即拥有51个元素的数组，下标从0到50，元素类型为字符型。 数组也可以直接在说明部分说明数组的类型，如：var x , y : array 1.20 of integer; a : ar

3、ray 0.50 of char;0123456750a下标数组中的每个元素都是变量，每个元素在数组中有固定的位置，可以用数组名及方括号括起的下标来表示。如a数组中的第5个元素可表示为：a 4数组元素的运算和变量相同，如： readln (a4); x3:=x3+y1;2数组元素的赋值和引用 如为一个数组A1.10 赋值，可用下列语句实现： for i:=1 to 10 do read (Ai); 如果两个数组类型相同，如数组x和y，可用赋值语句： x:=y； 把y的10个元素值赋给x的相应元素，它等效于： for i:=1 to 20 do xi:=yi; 但要给数组元素赋同一个值，不能这样

4、赋值： x:=0; 而应该用如下语句：for i:=1 to 20 do xi:=0;【例1】求100以内的所有素数。筛法：主要用于求一个区间上的质数表 去掉1 从2开始，把凡是2的倍数的数去掉（2保留） 从下一个未被去掉的数k开始，把凡是k的倍数的数去掉（k保留） 依此类推，直至筛选过程： (a) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 98 99 100 (b) 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 98 99 100 (c) 2 3 4

5、 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 98 99 100 算法分析：（1）设布尔类型数组A2.100以下标2100代表整数2100；数组元素的布尔值代表其是否为素数；设Ai=true 则i为素数，Ai=false 则i为合数；A中元素初始均赋为true；（2）从数组中新找一个素数P；（3）从P+1开始，把凡是P的倍数的数筛去（赋为false）；（4）重复步骤2、3，直到P>（5）打印数组中未被筛去的元素（元素值为true）；23456789100PP删去P的倍数找新的PXXXX23456789100参考程序：progra

6、m prime;const n=100;vara : array 2.n of boolean;i , p : integer;beginfor i:=2 to n do ai:=true; a数组初始化，全部置truefor i:=2 to n div 2 do if ai then begin ai 相当于 ai=true p:=i*2; while p<=n do begin 将a中i的倍数去掉 ap:=false; p:=p+i; end; while end; thenfor i:=2 to n do 打印素数if ai=true then write(i:4);end.【例2

7、】输入n个数，将它们按从小到大排序后输出。 请先思考自己的算法，再看以下内容！方法一 选择排序基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。排序过程： 在数组元素1.n中找出最小数，将数组第1位上的数与最小数交换； 在剩下的数中2.n中找出最小数，与第2位上的数交换； 依次类推，直到全部的数排完。 技巧： 寻找最小数借助哨兵变量x，存放的不是最小数的值，而是最小数的位置（下标），扫描一趟后，最小数即Sx。 交换数组元素Si和最小数即交换Si和Sx例如： 初始状态 49 38 65 97 76 13 27 49第一趟

8、排序后 13 38 65 97 76 49 27 49第二趟排序后 13 27 65 97 76 49 38 49第三趟排序后 13 27 38 97 76 49 65 49第四趟排序后 13 27 38 49 49 97 65 76第五趟排序后 13 27 38 49 49 97 97 76第六趟排序后 13 27 38 49 49 76 76 97第七趟排序后 13 27 38 49 49 76 76 97最后排序结果 13 27 38 49 49 76 76 97 参考程序： program sort1; var s : array1.1000 of real; i , j , n, x

9、 : integer; temp : real;begin readln(n); for i:=1 to n do read(si); 输入n个数 for i:=1 to n-1 do begin x:=i; for j:=i+1 to n do 在si+1 至sn 中寻找最小值if sj<sx then x:=j; if x<>i then begin 交换si和sx temp:=si; si:=sx; sx:=temp; end; end; for i:=1 to n do write(si:5);end.方法二 冒泡排序 基本思想：两两比较待排序数据元素的大小，发现两个

10、数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。 算法设计：设想被排序的数组R1.n垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。 排序过程：首先，从底部Rn和Rn-1开始比较，小数上浮(Rn-1)，大数下沉(Rn)；然后比较Rn-1和Rn-2，小数上浮直到比较R2和R1，小数上浮，此时第一趟结束，R1中的数必是最小数。 第二趟仍从底部Rn和Rn-1开始比较，直到比较R3和R2，小数上浮，结束时R2中的数

11、为次小数（本趟中的最小数）； 重复以上过程，直到将所有数排完。例如： 49 13 13 13 13 13 13 13 (R1)38 49 27 27 27 27 27 27 (R2)65 38 49 38 38 38 38 38 (R3)97 65 38 49 49 49 49 49 (R4)76 97 65 49 49 49 49 49 (R5)13 76 97 65 65 65 65 65 (R6)27 27 76 97 76 76 76 76 (R7)49 49 49 76 97 97 97 97 (R8) 参考程序：program sort2; var R : array1.1000

12、of real; i , j , n : integer; temp : real;begin readln(n); for i:=1 to n do read(Ri); 输入n个数 for i:=1 to n-1 do for j:=n-1 downto 1 doif sj+1<sj then begin 交换sj+1和sj temp:=sj+1; sj+1:=sj; sj:=temp; end; for i:=1 to n do write(si:5);end.§5.2 多维数组1二维数组类型定义的一般形式为：TYPE <类型标识符> = ARRAY 下标类型1

13、，下标类型2 OF <基类型>；数组说明： VAR <数组名> ：<数组类型标识符>；也可以直接在说明部分说明数组的类型，如： VAR <数组名> ：ARRAY 下标类型1，下标类型2 OF <基类型>；例如：var a : array 1.3 , 0.4 of integer;a1,0 a1,1 a1,2 a1,3 a1,4a2,0 a2,1 a2,2 a2,3 a2,4a3,0 a3,1 a3,2 a3,3 a3,4 a数组是一个二维数组，有两个下标，一维下标的值从1到3，二维下标从0到4，数组元素的类型为integer。 它共有

14、15个元素，可以看成3×5的矩阵。2多维数组 如果下标个数有n个，则称为n维数组。类型定义的一般形式为：TYPE <类型标识符> = ARRAY 下标类型1，下标类型n OF <基类型>；数组说明： VAR <数组名> ：<数组类型标识符>；也可以直接在说明部分说明数组的类型，如： VAR <数组名> ：ARRAY 下标类型1，下标类型n OF <基类型>；例如：金山中学全体在校生的期末成绩可以用以下的多维数组来表示 S : array 1.3 , 1.12 , 1.70 , 1.10 of integer; 其

15、中第一维下标1.3表示3个年级，第二维下标1.12表示每年级12个班，第三维1.70表示各班同学的学号，第四维表示该同学各门课程的成绩。【例3】求两矩阵的乘积b11 b12 b1mb21 b22 b2m bs1 bs2 bsmB 设矩阵A和B的形式如下：a11 a12 a1sa21 a22 a2s an1 an2 ansA 计算矩阵A和B的乘积矩阵C： 根据矩阵相乘公式：（详见数学基础矩阵）c11 c12 c1mc21 c22 c2m cn1 cn2 cnmC i=1,2,nj=1,2,m 参考程序：program timematrix; const maxnm=100; var i , j

16、, k , n , m , s : integer; a , b , c : array 1.maxnm , 1.maxnm of integer;begin write( ' n , s , m : ' ); readln( n , s , m ); writeln( ' A : ' ); for i:=1 to n do for j:=1 to s do read(a i , j ); writeln( ' B : ' ); for i:=1 to s do for j:=1 to m do read(b i , j ); for i:=1

17、to n do for j:=1 to m do begin c i , j :=0; for k:=1 to s do c i , j :=c i , j +a i , k * b k , j ; end; writeln( ' C : ' ); for i:=1 to n do begin for j:=1 to m do write(ci,j:5); writeln; end;end.【例4】求奇数幻方幻方是指n2个自然数排成n行n列的n阶方阵，且每行、每列和两条对角线上n个数之和都等于同一个数S。816357492S称为幻方和，Sn(n2+1)/2奇数幻方的排列方法：首

18、先确定1的位置放在第一行的中间位置；然后在当前自然数的右上方放下一个自然数；如果当前自然数在第一行，则下一个自然数放在最后一行；如果当前自然数在最右侧，则下一个自然数放在最左侧； 如果准备放下一个数的格内已有数，则下一个自然数放在当前自然数的正下一格。参考程序：program jshf; const maxn=100; var s : array1.maxn,1.maxn of integer; n , i , j , ii , jj , k : integer; begin readln(n); for i:=1 to n do s数组初始化 for j:=1 to n do si,j:=0

19、; i:=1; j:=(n div 2)+1; for k:=1 to n*n do begin si,j:=k;jj:=j; ii:=i; 备份i、j j:=j+1; if j>n then j:=1; i:=i-1; if i<1 then i:=n; if si,j>0 then begin 若准备放下一个数的格内已有数 j:=jj; i:=ii+1; if ii>n then ii:=1; end; end; for i:=1 to n do begin 输出结果 for j:=1 to n do write(si,j:4); writeln; end; end

20、.§5.3 字符串字符串类型，其一般形式：TYPE <标识符>=STRINGN;N必须是小于256的整数，表示字符串的最大长度，N缺省值为255。例如： var name1 : string20; 字符串name1的最大长度为20 ss : string; 字符串ss的最大长度为255 字符串的实际长度取决于程序执行时所赋予的实际字符个数， 可以用函数Length(字符串名)取得，如：t=length(ss); t为整型变量，利用length函数取得字符串ss的实际长度 字符串类型变量可以整体输入和输出，如： read(ss); write(ss); 字符串可以进行连接，

21、连接符为“+”，如：good + morning = good morning 字符串中的每一个字符可以对应字符数组中的一个元素，可以用字符串名加下标（类似数组）的方法来表示，如： ss:= computrr;ss7:= e; writeln(ss); 将输出computer 字符串与字符数组的区别在于字符串最大长度只有255，而数组元素的个数可以超过255。 字符串可以进行六种关系运算：、<>、>=、<=、>、< 。当两个字符串进行比较时，是从左到右逐个字符按照它们的ASCII码值进行比较。例如： a < b 为 true ABCD < ABC

22、 为 false Pascal提供了不少函数和过程用于字符串的操作，如：copy（S ：string；i , L ：integer）：string；返回字符串S中从第i个字符开始的L个字符所组成的字符串concat（S1,S2,Sn：string）：string； 合并一系列字符串Pos（P , S ：string）：byte； 返回子字符串P在字符串S中的位置delete（S ：string；I，L：ineger）； 从字符串S中删除从第I个字符开始的L个字符 Insert（S ：string；D ：string；P ：integer）； 在字符串D的P位置插入字符串S str（I ：int

23、eger / real；S ：string）； 整数 / 实数转字符串 val（S ：srting；R ：real；D ：integer）； 字符串转整数 / 实数【例5】编写一个学生成绩统计的程序。 输入：n个学生的姓名、成绩； 输出：平均分，成绩低于平均分的学生的姓名。参考程序： program exam; const maxn=100; var name : array1.maxn of string; 数组name用于存放学生姓名，数组元素为字符串 score : array1.maxn of integer; 数组score用于存放学生成绩 n , i , sum : integer

24、; ave : real;begin readln(n); sum:=0; for i:=1 to n do begin readln(namei); 字符串、字符不能和整型数据共用一个read readln(scorei); sum:=sum+scorei; end; ave:=sum/n; writeln(ave:8:1); for i:=1 to n do if scorei<ave then writeln(namei);end.【例6】输入一个字符串（长度<255），判断是否是回文串（回文串是指从左到右和从右到左读字符串是一样的）。 参考程序：program hwc; v

25、ar s : string; i , j , n : integer; t : boolean;begin readln(s); n:=length(s); t:=true; i:=1; j:=n; repeat if si<>sj then t:=false; i:=i+1; j:=j-1; until (i>=j) or (t=false); if t then writeln('Y') else writeln('N');end. Pascal还允许在字符串中嵌入控制字符。有两种表示控制字符的方法： 在符号# 后跟0255之内的整数，表示

26、与ASCII码相应的一个字符，如：# 65 表示字符A # 50 表示字符2# 10 表示换行 在符号 后跟一个字符，表示控制字符，如： G 表示响铃当它们与字符串常量混合在一起时，控制字符不能用单引号括起来，例如： writeln (waiting for input! GGG please #27 u ); 输出： waiting for input! please u （同时响铃）§5.4 类型强制转换Pascal 提供把变量类型强制转换的功能，即把一种变量作为另一种变量引用，其形式是在要转换的变量前冠以强制转换的类型标识符。如： A(B) 就是把变量B强制转换为A类型。 字符

27、型与整型可以相互转换字符变量c转换为整型变量i，i的值为该字符对应的ASCII码值；整型变量i转换为字符变量c，c为以i为ASCII码值所对应的字符。 布尔型与整型可以相互转换布尔变量转换为整型变量时，布尔值true对应1，false对应0；整型变量转换为布尔变量时，整型值为0时对应false，不等于0时对应true。 实型不能和其它类型相互转换，但整型变量可以直接赋给实型变量，如i为整型变量，r为实型变量，可以如下赋值： r:=i; 数组也可以使用类型强制转换，如数组B是一个二维整型数组，而类型A是一个一维整型数组类型，它们的定义如下：type A = array1.20 of intege

28、r;var B : array1.2 , 1.10 of integer;一般，数组B应采用B i , j 的形式，但可以将B强制转换为A，就可以把它当一维数组使用，如A(B) i 。转换前后的两个数组的对应关系如下：B1,1 B1,2 B1,10 B2,1 B2,2 B2,10 A(B)1 A(B)2 A(B)10 A(B)11 A(B)12 A(B)20 例如： program var c : char; b : boolean;i : integer; begin 运行结果： c:= a; writeln(c=,c); c=a i:=integer(c); writeln(i=,i);

29、i=97 i:=i+3; writeln(i=,i); i=100 c:=char(i); writeln(c=,c); c=d b:=false; writeln(b=,b); b=false i:=integer(b); writeln(i=,i); i=0 i:=2; writeln(i=,i); i=2 b:=boolean(i); writeln(b=,b); b=true end.§5.5 常见错误数组使用最常出现的错误是数组元素下标超出数组定义时规定的界限。由于默认状态下（即不在程序开头加$R+进行检查），运行时即使数组下标越界，系统将不出任何出错信息，依旧给数组赋值，

30、因此常导致我们花很多时间去寻找程序中的错误。Pascal提供了下标越界检查的功能，即在程序首部使用编译开关$R+（即option菜单中compile中的Range Checking）通知系统运行时对下标越界进行检查。但这种方法将占用运行时间，所以建议调试时加入$R+，调试结束后撤销（缺省时为$R-）。练 习 五随机产生50个数，求其中最大数和最小数。输入n个整数(n不大于1000)，将这n个整数按从大到小排序，然后输出排序结果。采用选择排序算法。采用冒泡排序算法完成上题。有一组数，其排列形式如下：11，19，9，12，5，20，1，18，4，16，6，10，15，2，17，3，14，7，13，8，且尾部的8和头部的11首尾相连，构成环形的一组数，编程找出相邻的4个数，其相加和最大，输出这4个数。给一维数组输入任意6个数，然后每次将末尾的数放到最前，直至原队头的数至队末，形成方阵。