《对分查找算法复习课件》由会员分享,可在线阅读,更多相关《对分查找算法复习课件(17页珍藏版)》请在金锄头文库上搜索。
1、课题:对分查找算法复习课题:对分查找算法复习 对分查找算法对分查找算法 一、生活中的对分查找一、生活中的对分查找 淘宝网上热卖的终极飞翼擎天柱(猜价格游戏) 游戏规则如下: (1)在给出这个玩具的价格是在100到200之间的整数。 (2)竞猜价格时,先猜100-200之间的中间价格,如果太 小了,就猜150200之间的中间价格,依此类推 直到猜对为止。 我来试试(我愿意一试) 150 太小 175 太大 163 太小 169 太小 172 太大 170 恭喜您猜对了 二、二、“对分思想,验证奇迹对分思想,验证奇迹” 1.对分查找的基本思想:对分查找的基本思想: (1)前提:被查找的数据序列必须
2、是有序的。 (2)基本思想: 在有序的数据序列中(一般放在数组中),首先把查 找的数据与数组中间位置的元素进行比较,若相等, 则查找成功并退出查找;否则,根据数组元素的有序 性,确定数据应在数组的前半部分还是在后半部分查 找;在确定了新的查找范围后,重复进行以上比较, 直到找到或未找到为止。 2. 验证奇迹: 对分查找实际数据演示动画 3. 算法的基本框架: 说明:要查找的数为key,待查找的数存在数组d中。i为查找 范围的起点,j为查找范围的终点,m为范围 i , j 的中 间位置,find 为查找成功与否的标记,find 为true代表 查找成功;find 为false代表查找失败。 i=
3、1 j=16 find=false 查找的结果,若为 true表示找到,若为 false表示未找到 do while (id(m) ,则重新调整查找范围i=m+1 i , j 若keyd(m)? 未找到,输出信息 找到,输出m 结束 N Y Y N Y N find=true? find=true Y N 三、“琢玉成形,化玉为器” 转化为程序代码 通过上述16个数据中查找key过程,程序代码如下: i=1 : j=16 : find=false Do while (id(m) then 表示待查数据比中间位置上的数大时 i=m+1 重新调整查找范围的起始位置 i=m+1 else 表示待查数
4、据比中间位置上的数小时 j=m-1 重新调整查找范围的终点位置 j=m-1 end if Loop If find then 判断查找的结果,若为 true表示找到,若为 false表示未找到 label1.caption= 找到!该数在数组中的位置为: + Str(m) else label1.caption= 未找到!该数在数组中不存在!“ end if 通过上述16个数据中查找key的过程,推广至n个数据中查找: i=1 : j=n : find=false Do while (id(m) then i=m+1 else j=m-1 end if Loop If find then ?氠
5、扡汥?慣瑰潩?尠找到!该数在数组中的位置为: + Str(m) else ?氠扡汥?慣瑰潩?尠未找到!该数在数组中不存在!“ end if 打开上机实践文件夹中的“对分查找.vpb” 文件,将窗体中“对分查找”按钮事件过程( Command3_Click() )中的代码补充完整。(注:带红色?处)并调试程序使之运行成功。 四、四、“体验之旅,感受程序魅力体验之旅,感受程序魅力” 1. 对分查找算法中被查找数据是降序的情况程序该如何修改? i=1 : j=n : find=false Do while id(m) then . else . end if Loop If find then ?慬
6、敢?挮灡楴湯?找到!该数在数组中的位置为: + Str(m) else ?慬敢?挮灡楴湯?未找到!该数在数组中不存在!“ end if 五、五、“思想升华,化茧成蝶思想升华,化茧成蝶” 2.对分算法几个注意问题: (1)对分查找的前提:被查找数据必须是有序的。 (2)新的查找范围的确定:i=m+1 或 j=m-1 (3)查找结束的判断条件:找到数据(find=true)或 ij 3. 对分查找算法的最多查找次数: Log2n +1 4. 对分查找算法的实际意义:对分查找的高效性。 (1)一个包含一百万个人名的电话簿中找一个名字,对分 查找可以让你不超过20次就能找到指定的名字。 (2)将全国1
7、3亿人按身份证号排列后,你可在31次比较后 找到这个人的信息。 若用顺序查找还有这个效率吗? 假设每次对分最坏情况,直到最后一次才找到 就会有 2k = n / 2 得 到 k = long2n + 1;二分法每次都会把范围缩小一半,因为最后剩一个元素时,也要执行查找过程,所以+1。 六、“夯实基础,查漏补缺 ” 1. 某8位男生的肺活量数据放在数组元素 a(1)到a(8)中,其数据 依次为: 3205、3408、3471、3498、3621、3829、4233、 4540,使用对分查找,设定查找键 key,若第一个被访问到 的数据是3498,小于key值,则第二个被访问到的数据是( ) A、
8、3408 B 、3829 C、4233 D、4540 2. 某数组有7个元素,依次为 200、202、204、205、210、215、218, 若采用对分查找在该数组中查找数据 200,需要查找的次数是( ) 若采用顺序查找数据 200,需要查找的次数是( ),这能说明顺序查找算法比对分查找算法效率高吗? 。 A、1 B、2 C、3 D、4 3. 我们育才高中在校生大约有 1500人,学号有序排列,若现在利用 对分查找来查找你的学号,最多需要查找( )次就能找到你自己。 A、10 B、11 C、12 D、13 4. 还原高考 医保卡余额查询,小朱设计了某单位医保卡余额查询 系统,输入卡号,可以
9、查出该卡号对应的余额。该单位共有n (n500)名职工,所有职工的医保卡号码和相应的余额等数据存 放在数据库文件“ company.accdb”的worker 表中,程序界面如 图所示,左 边列表框List1中显示的是全部职工的卡号、姓名和 余额,在文本框 Text1中输入职工的卡号,单击“查询余额”按钮 (Command1)后,如果找到此卡号,则在标签 Label5中显示 “此人的卡号、姓名和余额”,如果未找到则显示“找不到此卡号, 请重新输入”。 程序实现代码如下:程序实现代码如下: Dim kh(1 To 500) As Long kh用于存储卡号 Dim nam(1 To 500) A
10、s String nam用于存储职工姓名 Dim ye(1 To 500) As Single ye用于存储医保卡余额 Dim n, i, j As Integer Private Sub Form_Load( ) 数据库链接与打开代码略 从数据库中读取每条记录的卡号、姓名、余额分别存于kh、nam、ye数组中 Do While not rs.EOF n = n + 1 ?桫渨?獲?敩摬? 卡号) ?慮?爠?楆汥獤尨 姓名) ?敹渨?獲?敩摬? 余额) rs.movenext Loop 将从数据库中读取出来的数据按余额升序排序 For i = 1 To n - 1 For j = n To i
11、 + 1 Step -1 If kh(j) kh(j - 1) Then t = kh(j): kh(j) = kh(j - 1): kh(j - 1) = t k = nam(j): nam(j) = nam(j - 1): nam(j - 1) = k p = ye(j): ye(j) = ye(j - 1): ye(j - 1) = p End If Next j Next I 楌瑳?摁?整?本单位共有?瑓?尠名职工 For i = 1 To n List1.AddItem Str(kh(i) + + nam(i) + + Str(ye(i) Next i 实现对卡号的查询,并显示所找到
12、的卡号的医保卡余额 Private Sub Command1_Click() Dim x, m As Integer Dim f As Boolean x = Val(Text1.Text) i = 1 j = n f = False Do While (i = j) and f m = (i + j) / 2 If x = kh(m) Then . ElseIf x kh(m) Then . Else i = m + 1 End If Loop If f = True Then 慌敢?灡楴湯?尠卡号:?瑓?桫洨?尠?姓名:?慮?尠?尠?尠余额为:?瑓?敹洨?尠元 Else ?扡汥?慃瑰潩?找不到此卡号,请重新输入 End If End Sub 请完成以下问题: (1)画虚线框部分所采用的算法是: (选择或冒泡) (2)程序中加框处有错,请改正: ; 。 (3)程序中画线部分应填入: ; 。