您现在的位置：毕业论文 >> 教学论文 >> 正文

对分查找算法及程序实现教学案例第2页

更新时间：2011-11-17: 来源：毕业论文

生：一半一半的方法。
师：用你的话完整地概括一下在猜数游戏中所用到的方法。
生1：先猜中间数，根据大了、小了去掉一半，在新的范围内再猜中间数，再去掉一半，如此重复猜数，直到找到最终结果。
问题二：猜数游戏中的数据有什么特点？（有序还是无序？）
生：数据是有顺序的。
问题三：如果数据是无序的，能不能用这样的方法去猜？
生：不能。如果是无序的，可以先用排序法整理成有序的。
我们今天就来学习在有序的数据中快速查找数据的方法，教师展示课题“对分查找”（又称“折半查找”或“二分法查找”）及它的算法思想。并演示已做好的“对分查找”应用程序。
问题四：请思考100以内的自然数最多的猜数次数为多少？如果是n个数最多为几次？
生2：（思考讨论后）100个数一半一半下去最多为7次，如果是n个数最多为「log2n」次。
师：所以对于有序的数据，对分查找要比顺序查找效率要高得多……
有个平时很活跃的学生轻轻地嘟了一句：如果查找的是1或100，效率就低多了！旁边的学生也纷纷附和。
师：是的，所以说没有哪一个方法是十全十美的，不过对于“对分查找”来说，平均查找次数肯定是要比“顺序查找”要少得多，但是它有一个前提：数据必须有序。
设计意图：通过一个个问题，引发学生讨论、思考，逐层诠释“对分查找”的本质及优缺点。
（三）巧设疑点，突破难点
1．自然语言：以如下图的递增序列中查找35 为例，用课件引导学生动态分解“对分查找”过程：
第一次：key<d(m)，数据落在上半部分，让j=m-1。
第二次：key>d(m)，数据落在下半部分，让i=m+1。
第三次：key>d(m)，数据落在下半部分，让i=m+1。
第四次：key=d(m)，找到数据，退出循环。

key<d(m)        key>d(m)       key>d(m)       key=d(m)
（1）           （2）          （3）          （4）
2．流程图
把刚才的对分查找过程用流程图来表示。要得到①处“未找遍”的确切条件，学生一时有些困难，所以先引导学生思考完成下面具体找数的过程。
问题五：流程图中②处“中间结点位置m”如何计算？
学生根据猜数游戏经验，很快得出结论：fix((i+j)/2)或int((i+j)/2)
问题优：流程图中③、④处的处理语句是什么？
学生结合猜数过程，不难得出结论：③j=m-1 ④i=m+1
问题七：现在大家一起来思考流程图中①处“未找遍”的条件是什么？
教师提示i、j的动态变化，学生思考讨论，最后得出结论：i<=j 。

设计意图：用流程图清晰地表达对分找数的过程，设计的三个问题巧妙地个个击破本算法的难点，进一步明确“对分查找”的设计思路。

（四）复设要点，程序实现
Private Sub Command1_Click()
    Dim key, pos As Integer
    key = Val(Text1.Text)                '在文本框1中输入查找数
    nc = 0: pos = 0                      '用pos来记录查到的数的位置
    i = 1: j = 10000
            ①                        '查找（循环）范围
       nc = nc + 1
       m =         ②                 '计算中点位置
       If d(m) = key Then毕业论文http://www.youerw.com/
              ③    : Exit Do        '用pos记录在数组中的序号，结束查找
       elseif d(m) < key Then
                ④                    '修改查找范围
       Else
               ⑤                     '修改查找范围
       End If
    Loop
If       ⑥       Then             '找没找到的标志
Text2.Text = "找不到"
Else
Text2.Text = "在d(" + Str(pos) + ")中"