一维数组应用习题课.doc

【课题】PASCAL一维数组应用习题课【教学目标】知识目标：了解构造类型数据结构，掌握使用数组存储和处理批量数据的方法，熟悉查找排序算法设计；学会分析问题并建立数学模型；能力目标：体验算法解决问题的程序设计思想；通过排序算法基本思想的实现，使学生善于应用数组解决实际生活中的问题。情感目标：揭示计算机程序的人类智慧理念，养成良好的编程风格与习惯； 重在思维方法鼓励创新。【教学重点】领会数据有序处理，掌握数组折半查找、直插排序算法；【教学难点】数组折半查找、直插排序算法。【教学方法】讲练法、分析法 【课程类型】实践课【教学反思】【教学过程】一、引入：数组是PASCAL构造类型中最简单的一种。上次课使用数组成绩排序，但如何将数组中的内容，按颠倒的次序重放？若只能借助一个临时的存储单元而不得另外开辟数组，如何实现？二、新授例1、将数组中的内容按颠倒的次序重放。注意不是要求按逆序打印，而是重新放置数组内容。a数组：a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 i j 程序如下： Program invent(outout);Const n=9;VAR a:array1.Nof integer; p,I,j,t:integer;Beginfor i:=1 to n do read(Ai); readln; p:= n div 2; writeln(the original array); for i:=1 to n do write(Ai:4);writeln; for i:=1 to p do begin j:=n-i+1; t:=Ai; Ai :=Aj ; Aj :=t end;writeln(the array has been inverted:); for i:=1 to n do writeln(Ai:4); writeln;END.例2. 将一个数插入到有序的数列中，使插入后的数列仍然有序。方法：1、 从数组中找出插入X的位置P，2、 从ap到am中的数向后平移一个位置，即移到ap+1am+1中3、 把X放入ap中。读入有序数列到a数组中While (x=ap and (p=ap and (p=m) do P : =p+1; For i: = m downto p do ai+1:= aiap:=x;m:=m+1;writeln(a data has been inseted into a sequential array);for i:=1 to m do write(ai:5);writeln; end. 【例3】 折半查找算法简介查找是在程序设计中最常用到的算法之一。假定要从m个整数中去查找X的值是否存在，最原始的办法就是从头到尾逐个去找。这种查找的方法称为顺序查找。折半查找的速度有所改进，但只适用于已排好序的数列，假定a数组中有以下15个整数10 17 20 22 31 44 51 55 68 73 89 95 120 133 137 待查找的数放在X中，查找过程按如下顺序 559522174473133102031516889120167折半查找(又称二分查找)，是查找一个已排好序的表的最好方法。算法思想：首先设置三个指示器top,bot,mid,分别指向查找范围的顶部、底部和中间位置。假定十五个有序数列，则初始top=1,bot=15,mid=(top+bot) div 2,这时bot一定大于top。算法步骤：step1 首先确定整个查找区间的中间位置，mid = （ left + right ）div 2；step2 如果x=amid,则设查到标志为“真”（用待查关键字值与中间位置的关键字值进行比较：若相等，则查找成功；）打印有关信息；Step3否则，若小于xamid，则在前半区域继续进行二分查找，应该在top到mid-1之间，改变bot,使之等于mid-1;若大于，则在后半区域继续进行二分查找，应该在mid+1到bot之间，改变top,使之等于mid+1;重复上述步骤直到botbot) or findTop：=1；bot：=N；find:=false;Else if xamidNot find打印未找到Else if(xamid)Bot:=mid-1;Top:=mid+1; 源程序如下：Program binarySearch(input,output);Const n=15;Type arr=array1.n of integer;Var a:arr; x,i,mid,top,bot:integer; Find:Boolean; Begin for i:=1 to n do read(ai); readln; write(INPUT X to look for );readln(x);top:=1; bot:=n; find:=false;repeat mid:=(top+bot) div 2;if(x=amid) then begin writeln(find , x:3,it position is , mid:2); find:=true; endelse if(xamid) then top:=mid+1 until (bottop ) or find;if not find then writeln(x:3,not been found)end .四、归纳总结折半查找(又称二分查找)，是查找一个已排好序的表的最好方法。算法思想：首先设置三个指示器top,bot,mid,分别指