5.4查找算法的程序实现.doc

对分查找及VB程序实现导学案 班级： 姓名：一、本节课目标1. 理解和掌握对分查找的基本原理；2. 通过实例，体会对分查找的基本过程，理解对分查找的流程图，能结合实例看懂对分查找的主要代码；3学会使用选择排序思想设计解决简单查找问题的算法。4初步掌握对分查找算法的程序实现，提高学生综合运用各种基本语句的能力。二、重难点重点：（1）理解对分查找的基本原理，能看懂对分查找的主要代码；难点：（1）利用对分查找解决实际问题，完成对分查找算法的数学建模；（2）确定每一遍查找的范围。三、教学内容（一）阅读作业本59页知识点，完成以下整理。 1.对分查找的基本原理： 2.特征：对分查找的前提是被查找的数据序列必须是 的。对分查找时，i表示开始位置，j表示结束位置，计算中间位置m = 3.对分查找执行过程的理解【实例分析】若用一个数组d(1)到d(16)来存放升序的元素序列， d(1)d(2)d(3)d(4)d(5)d(6)d(7)d(8)d(9)d(10)d(11)d(12)d(13d(14)d(15)d(16)10151718222735454852656772859798查找键key为35，用i表示查找范围的起始位置的下标，j表示终止位置的下标，mid表示中间位置元素的下标，请完成以下对分查找的分析：查找次数查找范围MidKey与d(mid)的关系新范围i的值新范围j的值总结：对于升序的数列中查找过程中，比较key与d(m)，有三种情况要判断： key = d(m),表示找到，记下中点位置m，并结束查找（退出循环语句Exit Do） key d(m),则要到大的那部分去找，此时j不变，i= ；对于有个数的有序数组来说，最多查找次数为 （二）练习巩固：完成作业本P60练习（三）流程图分解、代码流程图：见作业本61页图4-10-1对分查找程序代码Dim search, i, j As Integeri = 1: j = 16search = 0Do While i j 进入查找的条件，i与j的关系 m = If d(m) = key Then search = m: Exit Do 找到，返回在数组中的序号 End If If key d(m) Then Else End If LoopIf search0 Then Text1.Text = str(search)Else Text1.Text = “没有找到”【思考】若要知道查找的次数，如何修改代码？（四）练习巩固：完成作业本P65练习 四、课后练习1.某数组有10个元素，依次为：5，12，16，23，27，30，35，41，49，50。下列说法正确的是（ ）A、使用对分查找数据12，需要的查找次是3次 B、使用顺序查找数据50，需要的查找次数是9次C、使用对分查找数据41，需要的查找次数是2次 D、使用顺序查找数据5，需要的查找次数是0次2.某高校学籍管理系统软件有2万个学生的电子档案（已按学籍号排序），假设从中取出一条记录并与待查项进行比较所花时间为8毫秒，则用对分法在该系统中查找任意一位学生档案最多花费的时间约为（ ）A、160毫秒 B、80毫秒 C、10毫秒 D、120毫秒3.（2016年10月高考【加试题】）某对分査找算法的VB程序段如下:i = 1: j = 9: n = 0key = Val(Textl.Text)Do While i = jn = n + 1m = Fix(i + j) / 2)If key = d(m) Then Exit Do Exit Do表示退出循环If key d(m) Then j = m - 1 Else i = m + 1Loop数组元素d(1)到d(9)的值依次为“7，12，18，25，39，58，61，72，86”。若该程序段运行结束后，n的值为2，则key的值是（ ）A、39 B、18或61C、18或72D、12或614.有如下程序段：Dim i As Integer, j As Integer, m As Integeri = 0: j = 8: k = Val(Text1.Text)Do While i = jm = Fix(i + j) / 2)If k = b(m) ThenExit DoElseIf k b(m) Thenj = mElsei = m + 1End IfEnd IfLoop数组元素b(0)到b(8)存储着参加比赛同学的编号，依次为“5，8，11，21，32，39，56，65，72”，经过该程序段“加工”查找编号为8的同学的过程中，依次被访问到的编号是（ ）A、32 11 8 B、21 8 C、32 8 D、39 21 85.编写VB程序，实现如下功能：在文本框Text1中输整数x，单击“查找删除”按钮Command1，在数组a（从小到大排列并显示在标签Label1中）中查找该数。若找到，则从数组a中删除该数（该数后的数组元素都往前移一位），并在标签Label2中显示删除后的结果（运行效果如图所示）；否则在标签Label2中显示“该数没有找到”。Dim a(1 To 10) As IntegerPrivate Sub Form_Load()Dim i As IntegerRandomizea(1) = Int(Rnd() * 10 + 1)Label1.Caption = Str(a(1)For i = 2 To 10a(i) = a(i - 1) + Int(Rnd() * 10 + 1) Label1.Caption = Label1.Caption + Next iEnd SubPrivate Sub Command1_Click()Dim i As Integer, j As Integer, m As Integer, k As IntegerDim x As Integer, f As Booleanx = Val(Text1.Text)i = 1: j = 10: f = FalseDo While m = If a(m) = x Then f = TrueElseIf Then i = m + 1 Else j = LoopIf f = True Then For k = m To 9 该数据后面的元素都往前移一位，思考如何移位 Nex