5.4 查找算法的程序实现课件（15张PPT）

课件15张PPT。5.4 查找算法的程序实现浙江教育-出卷网- 《算法与程序设计》游戏：商品价格竞猜第一组（方法甲）： 猜商品甲，只告诉对方猜的是“正确”还是“错误”，直到猜中为止。 第二组（方法乙）： 猜商品乙，如果没猜中，告诉对方“大了”还是“小了”，直到猜中为止。 想一想： 这两种方法有什么不同？哪种方法更快捷一些？采用这两种方法的前提是什么？ 查找算法的程序实现二分查找二分查找（对分查找）查找条件： 被查找的数据必须是有序的。 基本思想： 在有序的数据列中，首先将要查找的数据与有序数组内处于中间位置的数据进行比较，如果两者相等，则查找成功；否则根据数组元素的有序性，就可确定该数据应该在数组的前半部分还是后半部分继续进行查找；在新确定的范围内，继续按上述方法进行查找，直到找到要查找的数据，即查找成功，或直到子表不存在，即查找不成功。 超市商品价格查询系统流程图High = mid - 1Low = mid + 1low、high、mid表示待查找数据的位置，即数组元素的下标。注意：程序 代码Private Sub Command1_Click( ) Dim low, high, key, mid As Integer low = 1: high = 30:key = Val(Text1.Text) Do While low <= high mid = Int((low + high) / 2) If key = A(mid) Then： Text2.Text = "该商品价格为: " & b(mid) &“元” ****** ‘退出循环 ElseIf key > A(mid) Then： ? ? ? ? ? ? Else $ $ $ $ $ $ End If Loop If # # # # # # Then Text2.Text= “ 找不到该商品，请重新输入条形码“ : Text1.Text = "" End Sublow > highExit Dolow = mid + 1high = mid - 1超市商品价格查询系统程序 代码Private Sub Command1_Click( ) Dim low, high, key, mid As Integer low = 1: high = 30:key = Val(Text1.Text) Do While low <= high mid = Int((low + high) / 2) If key = A(mid) Then ： Text2.Text = "该商品价格为: " & b(mid) &“元” ****** ‘退出循环 ElseIf key > A(mid) Then： ： ? ? ? ? ? ? Else $ $ $ $ $ $ End If Loop If # # # # # # Then Text2.Text = “ 找不到该商品，请重新输入条形码“ : Text1.Text = "" End Sublow > highExit Dolow = mid + 1high = mid - 1Label3.CaptionLabel3.Caption 美化运行界面 编写代码 调试运行 拓展练习：挑战1： 如果在代码中引进布尔变量，怎样来完成“查找失败”部分的代码设计？ 加油！期待你挑战成功！！！ 程序 代码Private Sub Command1_Click( ) Dim low, high, key, mid As Integer low = 1: high = 30:key = Val(Text1.Text) Do While low <= high mid = Int((low + high) / 2) If key = A(mid) Then： Label3.Caption = "该商品价格为: " & b(mid) &“元” Exit Do ‘退出循环 ElseIf key > A(mid) Then： low = mid + 1 Else high = mid - 1 End If Loop If low > high Then Label3.Caption = “ 找不到该商品，请重新输入条形码“ : Text1.Text = "" End Subflag=falseflag=true : Exit Do ‘退出循环: Dim flag as boolean: flag=false 作品展示 拓展练习： 挑战2： 有兴趣的同学可以将此查询系统进一步改进，设计成超市收银台的收款系统。 加油！期待你挑战成功！！！ 小结二分查找 一、查找条件：有序数据 二、基本思想 1.循环，满足条件：low<=high ①计算查找区域的中间位置：mid=int((low+high)/2) ②确定新的查找区域（key与 A(mid)比较）： 若相等，则查找成功,退出循环 若大于，则在后半区域继续查找，low=mid+1 若小于，则在前半区域继续查找，high=mid-1 2.如果low>high，查找失败 三、程序实现 分析问题→设计算法→编写代码→调试运行 ... ...