广东省汕头市金山中学高中信息技术 pascal教程07 第七课 一维数组教案.doc

第七课 一维数组【引例】输入20个数，将它们按从大到小的次序排序后输出。讨论：如果按我们前面学的知识，我们应设20个变量来存储这20个数，如果要排序的数不是20个，而是100个，那我们就应设100个变量？没这么笨吧，我们有更好的办法解决。数组：由固定数量的相同类型的元素按一定顺序排列而成。只有一个下标类型的数组称为一维数组。7.1 数组类型定义和说明类型定义的一般形式为： type = array 下标类型 of ；数组说明： var ：；数组名是由用户定义的标识符，下标类型一般是子界类型，下标规定了数组元素的个数和排列次序。基类型表示数组中每个元素的类型，它可以是任何数据类型，但同一数组中的元素类型必须相同。如： 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 : array 0.50 of char;0123456750a下标数组中的每个元素都是变量，每个元素在数组中有固定的位置，可以用数组名及方括号括起的下标来表示。如a数组中的第5个元素可表示为：a 4数组元素的运算和变量相同，如： readln (a4); x3:=x3+y1;7.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; 但要给数组元素赋同一个值，不能这样赋值： 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 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参考程序：program prime;const n=100;var a : 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】输入n个数，将它们按从小到大排序后输出。 请先思考自己的算法，再看以下内容！方法一 选择排序基本思想：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。排序过程： 在数组元素1.n中找出最小数，将数组第1位上的数与最小数交换； 在剩下的数中2.n中找出最小数，与第2位上的数交换； 依次类推，直到全部的数排完。 技巧： 寻找最小数借助哨兵变量x，存放的不是最小数的值，而是最小数的位置（下标），扫描一趟后，最小数即sx。 交换数组元素si和最小数即交换si和sx例如： 初始状态 49 38 65 97 76 13 27 49第一趟排序后 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 : 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 sjsx then x:=j; if xi then begin 交换si和sx temp:=si; si:=sx; sx:=temp; end; end; for i:=1 to n do write(si:5);end.参考程序： 方法二 冒泡排序 基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。 算法设计：设想被排序的数组r1.n垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组r，凡扫描到违反本原则的轻气泡，就使其向上漂浮，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。 排序过程：首先，从底部rn和rn-1开始比较，小数上浮(rn-1)，大数下沉(rn)；然后比较rn-1和rn-2，小数上浮直到比较r2和r1，小数上浮，此时第一趟结束，r1中的数必是最小数。 第二趟仍从底部rn和rn-1开始比较，直到比较r3和r2，小数上浮，结束时r2中的数为次小数（本趟中的最小数）； 重复以上过程，直到将所有数排完。例如： 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 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+1sj then begin 交换sj+1和sj temp:=sj+1; sj+1:=sj; sj:=temp; end; for i:=1 to n do write(si:5);end. 参考程序：课后练习七：编程完成以下各题：1 随机产生50个数，求其中最大数和最小数。2 输入n个整数(n不大于1000)，将这n个整数按从大到小排序，然后输出排序结果。采用选择排序算法。3 采用冒泡排序算法完成上题。4 有一组数，其排列形式如下：11，19，9，12，5，20，1，18，4，16，6，10，15，2，17，3，14，7，13，8，且尾部的8和头部的11首尾相连，构成环形的一组数，编程找出相邻的4个数，其相加和最大，输出这4个数。5 给一维数组输入任意6个数，然后每次将末尾的数放到最前，直至原队头的数至队末，形成方阵。例如：输入 7 4 8 9 1 5输出 7 4 8 9 1 5 5 7 4 8 9 1 1 5 7 4 8 9 9 1 5 7 4 8 8 9 1 5 7 4 4 8