高中信息技术 3、查找算法课件 浙教版 课件.ppt

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,、对分查找,的基本思想,对分查找的,前提是数据已经有序,（以递增为例），然后把,待查找的数据,与,数组中间位置的数比较,，如果比中间位置的数大，在数组的后半部分继续查找，否则在数组的前半部分查找，继续对分查找，直到找到待查找的数在数组中的位置或数组已无法对分。,查找算法,10,15,17,18,22,27,35,45,48,52,65,67,72,85,97,98,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,下标,元素,数组,d(i):,I=1,J=16,M=fix(,(i+j)/2,)=8,第,1,次比较：,Keyd(m),查找范围应该,变成,d(9)d(16),Key=52,我们用变量,I,和,J,记录所要查找范围的起始和终止位置,2,、对分查找的基本过程：,10,15,17,18,22,27,35,45,48,52,65,67,72,85,97,98,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,下标,元素,数组,d():,I=8+1,J=16,M=fix(,(i+j)/2,)=12,第,2,次比较：,Keyd(m),查找范围应该,变成,d(9)d(11),Key=52,我们用变量,I,和,J,记录所要查找范围的起始和终止位置,10,15,17,18,22,27,35,45,48,52,65,67,72,85,97,98,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,下标,元素,I=9,J=12-1,M=fix(,(i+j)/2,)=10,第,3,次比较：,Key=d(m),找到了,Key=52,思考：如果,key=33,能找吗？那么至少需要比较几次？,（,2,）在规模为,n,的数组变量,d,中进行对分查找的流程图,未找到，输出结果：0,开始,I1，jn,i=j?,找到，输出结果：,m,结束,N,Y,计算中点,m(i+j)2,d(m)=key?,D(m)key?,im+1,jm-1,Y,Y,N,N,3,、当堂练习：,利用对分查找,在某校报名参加学生会主席竞选的学号列表,20080101,、,20080135,、,20080238,、,20080342,、,20080450,、,20080558,、,20080633,、,20080708,、,20080846,、,20080910,中，查找学号为,20080846,学生的过程中，依次被访问到的学号是（）,（,A,）,20080450,、,20080708,、,20080846,（,B,）,20080450,、,20080708,、,20080910,、,20080846,（,C,）,20080558,、,20080708,、,20080846,（,D,）,20080558,、,20080708,、,20080910,、,20080846,4,、,对分查找的核心,代码分析,Key=Val(Text1.Text),i=1,j=num,Do While,i=j,If,d(M,)=Key,Then,Label1.Caption=,在数组的,+,Str(M,),+,位置中,Exit Sub,End If,If,d(M,)Key,Then,Else,End If,Loop,Label1.Caption=,在数组中没有找到,+,Str(Key,),m=(i+j)2,i=m+1,j=m-1,这个语句还有其它写法吗,?,Int,(i+j)/2),或,fix(i+j)/2),5,、顺序查找,27,36,32,18,d(1),d(2),d(3),d(4),输入查找的元素值,key=32,i=1,i=2,i=3,此时,d(i)=key,数组中的第,3,个位置,如果输入查找的元素值,key=22,i=1,i=2,i=3,i=4,i=5,27,36,32,18,d(1),d(2),d(3),d(4),此时,i,等于,5,超过数组中元素个数,找不到,从数组,d,的第1个元素,d(1),开始，依次判断各元素的值是否与查找键,key,的值相等。,（,1,）、过程,（,2,）顺序查找的流程图,开始,i 1,d(i)=key?,i=n?,ii+1,未找到，输出结果：0,找到，输出结果：,i,结束,Y,N,Y,N,（,3,）转化成程序,Private Sub Command2_Click(),顺序查找,Key=Val(Text2.Text),For i=1 To,num,If,d(i)=Key,Then,Label2.Caption=,在数组的,+,Str,(i),+,位置中,Exit For,End If,Next,If,i=num+1,Then,Label2.Caption=,在数组中没有找到,+,Str,(Key),End If,End Sub,6,、顺序与对分查找比较,是否需要,事先排序,平均查找次数,顺序查找,不需要,(n+1)/2,多,对分查找,需要,Log,2,n,少,例,1,：从中国上海到美国旧金山海底电缆共有,15,个接点。现在某接点发生故障，需及时修理，为了尽快断定故障发生点，一般至多需要检查接点的个数为,个。,点评：,这种检查线路故障的方法，就是二分法的应用。二分法不仅可用于查找线路、水管、气管故障，还可以用于实验设计、资料查询，也是求解高次方程的常用方法。,7、,对分查找算法的实际应用,例,2,：,在,26,枚崭新的金币中，混入了一枚外表与它们完全相同的假币（重量比真金的略低），现在只有一台天平，请问你最多称,次就可以发现这枚假币？,分析：,本题可以通过二分法的思想来处理这种对称的问题。,解：,第一次各,13,枚称量，选出较轻一端的,13,枚，继续称；第二次两端各,6,枚，若平衡，则剩下一枚即为假币，否则选取出较轻的,6,枚继续称；第三次两端各,3,枚，选取出较轻的,3,枚继续称；第四次，两端各一枚，若不平衡，可找出假币，若平衡，则剩余的是假币，所以，最多只需称,4,次。,8,、复习题解,高考倒计时：,P70,例,5,、,P75,例,12,、,P77,第,8,题、,P81,第,15,题,