NOIP(全国青少年信息学奥林匹克联赛)复习Pascal――数组1

程序设计Pascal数组(一)1、一维数组Type类型标识符号=array[下标类型]of元素类型；Var数组名：类型标识符；orVar数组名：array[下标类型]of元素类型；定义：例6-1定义如下数组：（1）表示20种商品的价格；（2）表示30件邮件的安全邮递情况；（3）统计50个学生在一次考试（满分为100，最低分为0分）中各分数的分布情况；（4）统计一篇文章中各字母的出现频率（所有字母均小写）。Varprice:array[1..20]ofreal;mail:array[1..30]ofboolean;score:array[0..100]ofinteger;number:array[‘a’..’z’]ofinteger;共有20个实型数，price[1]-price[20]共有50个布尔型数，mail[1]-mail[30]共有101个整型数，score[0]-score[100]共有26个整型数，number[‘a’]-number[‘z’]程序设计Pascal想一想：下列数组这定义对不对，如不对，为什么？Vara:array[1..n]ofchar;b:array[10..1]ofinteger;c:array[integer]ofboolean;d:array[1.0..3.0]ofreal;e:array[1..50000]ofreal;说明：a数组中n为变量；b数组中，下标的上下界应从小到大；c、e数组元素个数太多，空间分配不够；d数组下标为实型，不是有序类型。程序设计Pascal一维数组的基本操作：1、数组的赋值、输入、输出例6-1按顺序读入10个数，再以逆序的方式输出。分析：可以定义一个10个元素的数组，用循环读入、输出。Programex10-1(input,output);varx:array[1..10]ofinteger;I:integer;beginforI:=1to10doread(x[I]);writeln(‘fanxushuchu:’);forI:=10downto1dowrite(x[I]:3);end.本例将数组下标作为循环变量，便于数组的输入、输出运行结果：10310-27789091–4821218–4199078–2703110fanxushuchu:数组元素的赋值可以用赋值语句。程序设计Pascal2、数组元素的移动例6-2将a数组中第一个元素移动到最后数组末尾，其余数据依次往前平移一个位置。P85分析：（1）先将第一个元素取出放在临时单元中；（2）将a[2]a[1]、a[3]a[2]…a[n]a[n-1]（3）再将临时单元tempa[n]Programex6-2(input,output);constn=10;vara:array[1..n]ofinteger;I:integer;temp:integer;beginforI:=1tondoread(a[I]);temp:=a[1];forI:=1ton-1doa[I]:=a[I+1];a[n]:=temp;forI:=1tondowrite(a[I]:3);End.思考：如果将最后一个元素移到第一个位置，其余数据依次向后平移一个位置，如何修改？如果将数组实现逆序交换，又该如何修改程序？…1234n-1n234n-1n1…程序设计Pascal例6-3对于数组a，输入一个测试数据x，如果x存于数组a，则把x元素删除；否则将x插在相应的位置，要求数组仍然有序（假设数组递增)分析：本题是一个查找问题。查找的最常用方法是顺序查找和二分查找。我们先采用顺序查找，二分查找以后再讲。顺序查找的过程是：从头开始，根据给定的值，依次与数组中的数进行比较，相同即为找到，若查遍整个数组仍然没有，则表示该元素不存在。由题意知：本题查询的条件是数组的元素小于x，若发现有数据与x相等，则将删除该数，否则，若数组中的数大于x，则此处就是插入x的位置。注意：如果是删除，则将x后的数向前平移一个；如果是插入，则先将x插入点的元素依次向后平移。3、数组元素的查找、插入、删除程序设计PascalProgramex6-3(input,output);constn=100;vara:array[1..n+1]ofinteger;{如果x插入，数组x将增加一个数据}x:integer;I,j:integer;beginforI:=1tondoread(a[I]);read(x);a[n+1]:=x;{将a[n+1]设为x，可以作为后面比较的结束标志}I:=1;whilea[I]xdoI:=I+1;{循环结束时，I即为需要插入或删除的位置}ifI=n+1thenwrite(‘Notfoundandnoplacetoinsert.’){x大于数组a中所有元素,无需处理}elseifa[I]=xthenbegin{找到x，删除}writeln(‘foundanddeleted.Result:’);forj:=Iton-1doa[j]:=a[j+1];{数据前移}forj:=1ton-1dowrite(a[j]:3);endelsebegin{没找到x，插入}writeln(‘notfoundandinsert.Rusult:’);forj:=n+1downtoI+1doa[j]:=a[j-1];{数据后移}a[I]:=x;forj:=1ton+1dowrite(a[j]:3);end;writeln;end.程序设计Pascal4、数组元素的排序排序的常用方法有：冒泡法、选择法、插入法、希尔法、快速分类法等。这些算法会逐步地接触到。例6-4从键盘中输入若干个数，将它们按照从小到大的顺序输出。分析：选择法：设若干个数存放在a[1]、a[2]、…a[n]中。（1）先从n个数选出一个最小数放在a[1]中：即让a[1]分别与a[2]到a[n]比较，如果发现a[1]a[i],则将a[1]与a[I]交换。等一轮比较下来，最小数就存放在a[1]中。（2）依（1）类推，a[2]中放第二小，a[3]中放第三小数，…一直到a[n-1]，这样序就形成了。程序设计Pascal程序如下：Programmaopao_sort(input,output);constn=10;vara:array[1..10]ofinteger;I,j,temp:integer;beginforI:=1tondoread(a[I]);forI:=1ton-1doforj:=n-1downtoidoifa[j+1]a[j]thenbegintemp:=a[j+1];a[j+1]:=a[j];a[j]:=tempend;forI:=1tondowrite(a[I]:4);end.选择法简单易懂，但运行速度慢。冒泡法是一种比较有名的排序法。冒泡法的算法思想是：将相邻的两个数比较，小的冒到前面，大的沉到后面。程序设计Pascal冒泡法程序：Programmppx(input,output);constn=10;vara:array[1..n]ofinteger;I,temp:integer;t:boolean;beginrandomize;forI:=1tondobegina[i]:=trunc(random(100));write(a[i]:4);end;repeatt:=true;fori:=1ton-1doifa[i]a[i+1]thenbegintemp:=a[i];a[i]:=a[i+1];a[i+1]:=temp;t:=false;enduntilt;writeln;forI:=1tondowrite(a[I]:4);End.随机产生10个0-100的整数并输出冒泡排序做标记，若没有交换值则t为true,出现交换后t改为false将排好的序输出。程序设计Pascal应用：例6-5将一个十进制整数转化为二进制数。分析：在标准类型中，长整型范围是-2147483648-21474483647,而二进制数10000000000的十进制数为1024，因此如果直接来转换会出现数据溢出。为了能更好存储二进制的各个位数，可以采用数组。假定输入的数据是长整型，则存储二进制数的数组长度为32。十二的方法是除以2反向取余法。Programex6-5(input,output);varbin:array[0..50]of0..1;x:longint;k,I:integer;Beginread(x);forI:=0to50dobin[I]:=0;{将数组清0}k:=0;whilex0dobeginbin[k]:=xmod2;x:=xdiv2;k:=k+1;end;write(‘二进制为:’)forI:=k-1downto0dowrite(bin[I]:1);end.思考：如果要求将十进制的实数转化为二进制数，如何处理？提示：小数采用乘2取整的方法。程序设计Pascal例6-6圆盘找数，如图所示：找出4个相邻的数，使其相加之各最大和最小的是哪4个数？并给出它们的起始位置。52本题实际上就是先求出相邻的四个数的和，然后找出最大数和最小数。如何求相邻的四个数的和呢？设和存放在S中，我们不妨先确定一个序，即确定第一个数的位置和最后一个数的位置。假设圆盘上的20个数中5为第一个数，12为最后一个数。则可将这20个数放在a数组中。数组的下标取0-19。0≤I17时，s=a[I]+a[I+1]+a[I+2]+a[I+3]I=17时，s=a[I]+a[I+1]+a[I+2]+a[0]I=18时，s=a[I]+a[I+1]+a[0]+a[1]I=19时，s=a[I]+a[0]+a[1]+a[2]+a[3]由取余的知识可知：I=17时，a[0]=a[(I+3)mod20];I=18时，a[1]=a[(i+3)mod20)…,即0≤I≤19时，都有s=a[I]+a[(I+1)mod20]+a[(I+2)mod20)+a[(I+3)mod20)成立。程序设计PascalProgramex6-6(input,output);vara:array[0..19]ofinteger;s,max,min:integer;smax,smin:integer;{smax,smin记录最大和以及最小和的起始位置}I:integer;beginforI:=0to19doread(a[I]);max:=-maxint;min:=maxint;{设置最大值和最小值的初始值}forI:=0to19dobegins:=a[I]+a[(I+1)mod20]+a[(I+2)mod20]+a[(I+3)mod20];ifsmaxthenbeginmax:=s;smax:=I;end;ifsminthenbeginmin:=s;smin:=I;end;end;write(‘max:’,a[smax]:2);forI:=1to3dowrite(‘+’,a[smax+I]mod20]:2);write(‘=‘,max);writeln(‘startfrom’,smax+1);write(‘min:’,a[smin]:2);forI:=1to3dowrite(‘+’,a[smin+I]mod20]:2);write(‘=‘,min);writeln(‘startfrom’,smin+1);end.程序设计Pascal例6-7投票问题：竞选时，要求选民在A、B、C、D四个候选人中选择（人数不限），如果选择了ABCD以外的人员则为废票。统计时输入“#”结束，请按候选人得票数从大到小顺序输出候选人及其得票情况。分析：设两个数组name数组存放候选人姓名，name[1]放得票最多的人名，name[4]存放得票最少的人名。score存放各人的得票数。假设开始时，name数组中各元素的值依次为A、B、C、D，则问题就转化为重组name数组，而score数组只起存储作用。程序设计PascalProgramex6-7(input,output);varscore:array