tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 其它课程 >>

折半查找算法及程序实现教案


折半查找算法及程序实现 一、教材分析 教学重点:以图示法方式,演示折半查找算法的基本思想。 教学难点:由折半查找算法的思想到程序代码编写的转换,尤其是其中关 键性语句的编写是教学中的难点。 二、学情分析 学生应该已经掌握程序设计的基本思想,掌握赋值语句、选择语句、循环 语句的基本用法和 VB 基本操作,这节课学生可能会遇到的最大问题是:如何归 纳总结对分查找解决不同情况问题的一般规律,鉴于此,在教学中要积极引导 学生采取分解动作、比较迁移等学习策略。 三、教学目标 知识与技能:理解对分查找的概念和特点,通过分步解析获取对分查找的 解题结构,初步掌握对分查找算法的程序实现。 过程与方法:通过分析多种不同的可能情况,逐步归纳对分查找的基本思 想和方法,确定解题步骤。 情感态度与价值观:通过实践体验科学解题的重要性,增强效率意识和全 局观念,感受对分查找算法的魅力,养成始终坚持、不断积累才能获得成功的 意志品质。 四、教学策略与手段 1、教学线索:游戏引领---提出对分查找原理--- 解析对分查找的算法特 征---实践解决问题。 2、学习线索:分解问题---归纳问题---实践提升,在三个阶段的不断推进 中明确对分查找算法,总结规律。 五、教学过程

1、新课导入 (1)热身:游戏(2 分钟) 找同学上来找一本上千页电话册里面的一个名字。(课程导入我写的不是很 详细,自己设计哦) (2)教师引导:所以我不希望只有他一个人体验这种方便,我们教室里还 有一大帮人,其实这种什么不止用于查找电话铺,还可以运用到实际生活中, 教室里有这么多人,坦白说,按学校的老方法一个人一个人的数,对所有老师 来说都及其费力,那我们想想,是不是数数 2368,这样好点对吗?。不要小看 这种想法,他其实是非常棒的,他能把解决问题的时间缩短一半,因此我们提 出了这种算法 2、新课: 首先我们一起来看一看折半查询算法中的“折半”的含义。 师:何为折半呢? 生:减半;打一半的折扣。 例如,我手里拿着一根绳子,现在我们来进行折半试验,首先拿住绳子的 两个端点, 然后从中点的位置进行对折,这样绳子就缩短为原来长度一半,然后将一 半的绳子继续执行与刚才相同的操作,使得绳子的长度逐渐的缩短,直到绳子 长度短得不能再进行折半了。 师:那什么时候就不能再折半了呢? 生:即绳子的两个端点合二为一为止。 折半查找算法的思想与绳子折半的过程基本相同。下面我们先通过图示来 看看折半查找算法究竟是什么? 教学步骤二:分解对分查找算法(5 分钟)

假设一个从小到大排列的数据存放在一个数组中——Data(10),而查找数 据存放在变量 x 中。如图 1 所示,橙色方框的代表的是查询数据 x,每个浅兰色 方框代表的是数组中的每个元素,框内显示的数据是每个数组元素对应的下标 (序号),整排的浅兰色方框就可以看成整个数组,即待查数据表(数组元素 表)。
x

0

1

2

3

4

5

6

7

8

9

10

Low

High

图一 第一步:就像抓住绳子的两端一样,首先设立两个标记 Low、High 分别来 标识查询区间的低端和高端,即数组元素的下标,如图 1 所示。 师:对于初始查询区间,它们是多少呢? 生:Low=0 , High=10 第二步:取区间的中点标记 Mid,如图 2 所示。 师:查询区间的中点为多少?(这个地方,有的学生可能直接说出下标值, 所以要提醒学生让中点和两个端点相联系,即用端点表示中点) 生:Mid=(Low+High)/2 师:中点位置上的数据为什么?(提醒学生数据是放在数组 Data 中的) 生:Data( Mid)

0

1

2

3

4

5

6

7

8

9

10

Low

Mid

High

第三步:判断中点位置上的数据 Data( Mid)与要查找数 x 是否相等, 如何相等,则找到,并结束查找;如果不相等,就执行第四步。 师:这个判断语句如何写呢? 生:if Data( Mid)=x then print “x 找到” 结束查找 end if 第四步:如果不相等,那么对查询区间进行折半操作。 师:那如何折半——是从中点处向左侧折半还是向右侧折半?(这是整个 折半查询进行下去的关键所在,所以一定要让学生自己学会判断) 由于待找数据表是从小到大排列的, 而且区间中点位置上的数据 Date(Mid) 也知道,所以,通过 Data(Mid)与 x 的比较,看一看,x 比 Data(Mid)大还是小, 就可以判断出 x 落在中间数 Data(Mid)的左侧还是右侧, 从而判断出向左还是向 右折半。 师:那么,判断语句如何写呢? 生:if Data(Mid)<x then

说明 x 比 Data(Mid)大,且数据表是从小到大排列的,从而判断出 x 落在右 侧。所以从中点处向右侧折半。 师:如图 3 所示,观察新查询区间,发现高端标记没有变化,而低端标记 变了,那低端标记 Low 为多少呢? 生:我们来看图 2,由于中点位置上的数据已经被查询过,所以,新查询区 间内的数据就不能再包含它,Low 就得比 Mid 多 1,即:Low=Mid+1。

0

1

2

3

4

5

6

7

8

9

10

e
Low High

lse

说明 x 比 Data(Mid)小,所以就向左侧折半,如图 4 所示,观察新区间,发 现低端标记没有变化,而高端标记变了,同样道理,新查询区间内不能包含 Mid 对应的数据,所有 High 比 Mid 小 1,即:High=Mid–1 end if 第五步:重复执行第二、三、四步骤。 师:如果一直没有找到,那么什么时候不再进行折半查找呢?(提示学生 想一想绳子折半的情况)

0

1

2

3

4

5

6

7

8

9

10

Low

High

生:直至 Low>High,停止折半查询。 教学步骤四:对各种情况进行归纳总结。 (1)x 与 data(mid)的大小比较影响 i,j 的取值的规律: i 的取值规律:if data(mid)<x then low=mid+1 j 的取值规律:if data(mid)>x then high=mid-1 用分支结构实现。 (2)继续进行重复查找的条件: low≤high,用循环结构实现。 教学步骤五:构建对分查找的流程图

教学步骤六:对分查找算法的初步程序实现。
开始 low≤high
low?1,high?1 0

N 继续查?
mid=(low+high)\2

Y 计算mid Y data(mid)=x? N
输出找到的信息

输出“未找到”

Y
low?mid+1

data(mid)<x?

N
high?mid-1

结束

教师事先设计好 Vb 窗体,学生只需要在相应的程序体输入代表算法思想的 关键语句。 附主要程序体: Private Sub Command2_Click() Dim x As Integer, mid As Integer, low As Integer, high As Integer x = Val(Text1.Text) low = 0: high = 10 Do While low <= high mid = (low + high) \ 2 If data(mid) = x Then Text2.Text = "找到了,是第" & mid & "个" Exit Sub End If If data(mid) < x Then low = mid + 1 Else high = mid - 1 End If Loop Text2.Text = "找不到"

End Sub 程序说明:1、获得要查找的数据 x 的值 2、i,j 赋初值。 low = 1: high = 10 3、求 mid 的值。mid = (low + high) \ 2 4、分三种情况,(1)如果 x=data(mid),则如果 data(mid) = x 那么 Text2.Text = "找到了,在第" + Str(mid) + "个"。 (2)如果 x>data(mid),那么 low=mid+1 否则 high=mid+1 5、重复上述的 3,4 步,直到 low 超出 j(或者理解为 low<=high 不成立,所 以不能用 for next,而要用 do while 语句) 6、如果有找到 x,那执行第 4 步(1)步后应该输出找到的位置后退出程序, 如果不退出,说明 x 没有找到,所以在相应位置要输出“找不到”。 折半查找算法基本思想总结(2 分钟) 对一有序数据表,首先从初始查找区间开始,取出区间中点位置上的数据 与要查询数据进行比较,若相等,则查找成功,并结束查询;否则,将当前查 找区间缩小一半。在新的查询区间内,同样取出区间中点位置上的数据与要查 询数据进行比较,若相等,则查询成功,并结束查询,否则将新的查询区间再 次缩小一半。然后继续采用相同的方法,直到查找数据成功或者查询区间不能 再折半(即查询失败)为止 教学步骤七:评价。 评价学生的程序实现情况,并讨论或实践问题:如果是降序序列,该怎么 样改动程序?如果序列元素不是 10 个,而是 100 个或更多呢? 教学步骤八:总结提升。 (1)由于对分查找过程中的每次比较都能使得搜索空间减半,对分查找将 不会使用超过 log2n 次比较来找到目标值。 x = Val(Text1.Text)

(2)提升对分查找算法的实际意义:同学们可能还没有意识到二分查找是 多么高效,那不妨设想一下在一个包含一百万个人名的电话簿中找一个名字, 二分查找可以让你不超过 21 次就能找到指定的名字。如果你能够将世界上所有 的人按照姓名排序,那么你可以在 35 步以内找到任何人。 八、作业: 1、以下的三组元素序列能采用对分查找法来查找吗? (1) 19,33,35,53,56,67,78,99 (2)53,35,67,78,56,99,33,19 (3)99,67,56,45,33,10,9,1,0,-9 2、设计一个能用对分查找算法思想解决的实际问题。


推荐相关:

数据结构实验---折半查找实验报告

一、实验目的与要求: 实验目的: 通过编程实现折半查找算法,掌握顺序查找方法的理论原理和实现 过程,从而加深对顺序查找方法的理解,提高折半查找方法的编程应用技巧。...


折半查找算法的实现

学生实验报告 (六)学生姓名 实验项目 学号 折半查找算法实现 □演示性实验 □验证性实验 N107 实验仪器台号 实验日期及节次 同组人 无 □综合性实验 √...


折半查找的实现

折半查找的实现_计算机软件及应用_IT/计算机_专业资料。实验五 折半查找的实现一、 实验目的 1. 掌握折半查找算法的基本思想; 2. 掌握折半查找算法的基本实现...


折半查询算法教案

折半查询算法教案_初中教育_教育专区。这是教育科学出版社出版的“算法程序设计”选修模块中第三章第4小节中的内容。今日推荐 160...


C++折半查找算法的实现

C++折半查找算法实现: #include<iostream> using namespace std; int Bisearch(int data[],int x,int begin,int last); void PrintData(int data[],int ...


实验二 折半查找算法设计

实验二 折半查找算法设计题目:折半查找算法设计 问题描述: (1)分析掌握折半查找算法思想,在此基础上,设计出递归算法和循 环结构两种实现方法的折半查找函数。 (...


折半查找算法实现(C++)

//此程序折半查找的详细算法实现 #include<iostream> using namespace std; void CreateData(int data[],int length);//为一个数组赋值 //此函数是折半查找...


实验三:折半查找算法设计

折半查找算法:递归查找和循环查找 假设有已经按照从小到大的顺序排列好的五个整数 a0~a4,要查找的数是 X,其基本思想是: 设查找数据 的范围下限为 l=1,上限...


数据结构折半查找算法

数据结构折半查找算法_工学_高等教育_教育专区。数据结构折半查找算法#include<stdio.h> #include<stdlib.h> #define MAX_LENGTH 100 typedef int KeyType; type...


数据结构-实验8查找的算法

8.2 实现折半查找算法 编写一个程序,输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查 找关键字 9 的结果。要求: (1)用非递归方法; (2...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com