第一篇：对分查找算法教案
对分查找算法教案
一、设计思想
对分查找是计算机科学中的一个基础算法。对于一个基础算法的学习，同样可以让学生在一定的情境下，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程。本堂课以一个游戏暖场，同时激活学生的思维，引导学生去探索游戏或生活背后的科学原理。为了让学生在教师的引导下能自我解析算法的形成过程，本课分解了问题动作，找出问题的全部可能情况，在对全部可能情况总结归纳的情况下，得出对分查找的基础算法，最后在程序中得到实现，从而使学生建立起对分查找算法形成的科学逻辑结构。
二、教材分析
本课的课程标准内容：
（一）计算机解决问题的基本过程（1）结合实例，经历分析问题、确定算法、编程求解等用计算机解决问题的基本过程，认识算法和程序设计在其中的地位和作用。
（三）算法与问题解决例举 C 查找、排序与问题解决
（2）通过实例，掌握使用数据查找算法设计程序解决问题的方法。本课的《学科教学指导意见》内容：基本要求：1.初步掌握对分查找算法。2.初步掌握对分查找算法的程序实现。
教材内容：第二章 算法实例 2.4.3对分查找和第五章5.4查找算法的程序实现，课题定为对分查找算法及程序实现，安排两个课时，第一课时着重是对分查找算法的形成和初步程序实现，第二课时利用对分查找算法解决一些实际问题的程序实现，本教学设计为第一课时。
从《课程标准》和《学科教学指导意见》对本课教学内容的要求来看，要求学生能从问题出发，通过相应的科学步骤形成对分查找的算法。对学生来说，要求通过这一课时的学习能初步掌握或了解对分查找的前提条件、解决问题的对象，明确对分查找算法结构和对分查找的意义。
三、学情分析
学生应该已经掌握程序设计的基本思想，掌握赋值语句、选择语句、循环语句的基本用法和VB基本操作，这节课学生可能会遇到的最大问题是：如何归纳总结对分查找解决不同情况问题的一般规律，鉴于此，在教学中要积极引导学生采取分解动作、比较迁移等学习策略。（说明：由于这个课是算法与程序设计课，对学生有一定的要求，学生至少应该熟悉算法的基本概念，掌握顺序结构、分支结构和循环结构，天津的学生虽然学的是Java,但是在算法这一块上都是相通的，如果对算法流程，三种基本结构原理和语句如果都掌握的话，理解这个课应该没什么大的问题，VB只是一个程序实现的工具。但如果学生没有较好的算法基础，没有前续的知识作辅垫，这节课会比较困难，教师就要灵活处理。）
四、教学目标
知识与技能：理解对分查找的概念和特点，通过分步解析获取对分查找的解题结构，初步掌握对分查找算法的程序实现。
过程与方法：通过分析多种不同的可能情况，逐步归纳对分查找的基本思想和方法，确定解题步骤。
情感态度与价值观：通过实践体验科学解题的重要性，增强效率意识和全局观念，感受对分查找算法的魅力，养成始终坚持、不断积累才能获得成功的意志品质。
五、重点难点
教学重点和难点：分解并理解对分查找的过程。
六、教学策略与手段
1、教学线索：游戏引领---提出对分查找原理---解析对分查找的算法特征---实践解决问题。
2、学习线索：分解问题---归纳问题---实践提升，在三个阶段的不断推进中明确对分查找算法，总结规律。
七、教学过程
1、新课导入
（1）热身：游戏（2分钟）教师展示一件特色物品，让一个学生来猜这个物品的价格，其他学生只需要根据这个学生猜出的价格提示“高了”或是“低了”，如果学生能在约定次数内猜对这个物品的价格，就把这件物品“赠送”给他……。
（2）讨论：你觉得怎么样猜可以猜的快一点呢？有什么技巧吗？你从这个游戏当中得到什么启示？(2分钟)
（3）教师引导：这个世界不是缺少问题，而是缺少发现，其实在这个游戏的背后，含有一个非常经典的算法。引出对分查找的的概念。(1分钟)
2、新课：
教学步骤一：分析对分查找的原理和方法。（3分钟）
（1）对分查找是效率很高的查找方法，但被查找的数据必须是有序的。
（2）首先将查找的数与有序数组内处于中间位置的数据比较，如果中间位置上的数与查找的数不同，根据有序性，就可确定应该在数组的前半部分还是后半部分继续查找。
（3）在新确定的范围内，继续按上述方法进行查找，直到获得最终结果。
教学步骤二：分解查找过程中可能出现的所有情况。（第一种情况5分钟）
以规模为10的升序数组d为例：用一个数组d（1 to 10）来存放序列，用i表示查找范围的第一个数组元素的下标，j表示最后一个数组元素的下标,mid表示中间位置元素的下标。（1）
第一种情况：要找的值在后半部分；
以查找键KEY=48为例分析
第一次查找：：
范围d(1)～d(10),mid= └(1+10)/2┘, d(mid) 所以可以确定接下来要找的范围是后半部分。 比较后i=mid+1 第二次查找： 范围d(6)～d(10),mid= └(6+10)/2┘,d(mid) 所以可以确定接下来要找的范围是后半部分。 比较后：i=mid+1 第三次比较： 范围d(9)～d(10)，mid= └(9+10)/ ┘2，d(mid)=Key，找到了。 思考：如果要找的是52? i,j,mid分别是多少？ 总结一: 如果d(mid) 教学步骤三：继续分解对分查找算法中包含的其他情况。（9分钟） 讨论:两人为一合作小组，分别画出key=17和key=20的查找示意图,并用共同的智慧讨论并回答以下两个问题。 问题1:当d(mid)>key时，新查找的范围在哪里？i和j如何变化？ 问题2:在什么情况下查找会结束？继续进行重复查找的条件是什么? （2） 第二种情况：要找的值在前半部分； 以查找键KEY=17为例分析： （3）第三种情况：要找的值找不到；以查找键KEY=20为例分析： 总结二：如果d(mid)>key ,新查找范围为上半部分, i值不变，j=mid-1。 总结三：(1)找到了查找会结束;(2)在i<=j时重复查找,如果还是找不到,查找也会结束。 教学步骤四：对各种情况进行归纳总结。（2分钟） （1）Key与d(mid)的大小比较影响i,j的取值的规律： i的取值规律：if d(mid) j的取值规律：if d(mid)>key then j=mid-1,用分支结构实现。 (2)继续进行重复查找的条件： i≤j，用循环结构实现。 教学步骤五：用流程图来描述对分查找算法（3分钟） 教学步骤六：对分查找算法的初步程序实现。（9分钟） 教师事先设计好VB窗体，学生只需在相应的程序体输入代表算法思想的关键语句。 附主要程序体： Private Sub Command2_Click() Dim key As Integer, mid As Integer, i As Integer, j As Integer key = Val(Text1.Text)i = 1: j = 10 Do While ____(1)_______ mid =(i + j)2 If d(mid)= key Then Text2.Text = “找到了，是第” & mid & “个” Exit Sub End If If _____(2)_______ Then _____(3)_______ Else _____(4)_______ End If Loop Text2.Text = “对不起，找不到！” End Sub 教学步骤七：评价。（4分钟） 用过程反馈表评价学生的程序实现情况，学有余力的同学可以进一步讨论或实践问题：如果是降序序列，该怎么样改动程序？如果序列元素不是10个，而是100个或更多呢？ 教学步骤八：盘点对分查找法的核心内容,总结提升。（3分钟）(1)采用对分查找的前提是数据序列必须是有序。 (2)由于对分查找过程中的每次比较都能使得搜索空间减半，对分查找将不会使用超过┌log2(n+1)┐次来找到目标值。 (3)提升对分查找算法的实际意义：同学们可能还没有意识到对分查找是多么高效，那不妨设想一下在一个有一百万个人名的电话簿中找一个名字，对分查找可以让你不超过21次就能找到指定的名字。如果你能够将世界上所有的人按照姓名排序，那么你在35次内就能找到任何人。 教学步骤十：总结本课的科学解题过程。（2分钟） 八、作业： 以下的三组元素序列能采用对分查找法来查找吗？ (1)7，22，25，35，44，61，88，99,100 （2）22，46，77，89，67，99，33，20,98 （3）87，75，58，44，23，11，7，2，0，-8,-10 2、设计一个能用对分查找算法思想解决的实际问题，用自然语言描述即可，为下节课作准备。 《对分查找及其算法实现》教学设计 湖北省巴东县第一高级中学 刘少银 一、教材学情分析 本次课是浙江版高中信息技术选修教材《算法与程序设计》第二章算法实例第四节查找中的一部分内容。由于教材体系不适合校本实际，我们在教学过程中对教材体系作了如下调整。 讲授顺序：第一章 算法和算法的表示、第三章 面向对象的程序设计的基本知识、第四章 VB程序设计初步、第二章算法实例，第五章 算法实例的程序实现穿插在相关内容教学中完成。 因此在前期教学中学生已经初步掌握了算法基础及算法表示，VB程序设计初步等。本次课是让学生掌握对分查找的思想及算法的实现。 二、教学目标 知识与技能：理解对分查找的基本含义、方法，理解并能画出对分查找的流程图； 过程与方法：通过案例分析、直观观察，增强分析问题和解决问题的能力； 情感、态度与价值观：感受信息技术与现实生活的关联，激发对信息技术学科的求知欲，培养主动学习和使用信息技术的意识；养成科学的学习态度，不迷信书本、不迷信权威。 三、教学重难点 教学重点：对分查找的基本方法及注意事项； 教学难点：对分查找算法的实现。 四、教学策略 ·以“猜数”游戏导入，引入对分查找的概念； ·师生讨论、生生讨论、生生互助；分析、归纳、总结，理解并掌握对分查找的基本思想； ·采用分类研究、分享成果、课后练习等学习方法，理解对分查找方法及基本主要特征； ·采用自然评价、师生评价、生生评价等形式对学习进行过程性评价。 五、教学过程 1．游戏激趣，释疑对分查找 （三个程序图片） （初始界面）（人工猜数界面）（程序猜数界面） 准备：几张白纸，一支记号笔。启动猜数程序。 师：同学们好！大家看到前面的程序了吗？它是一个什么程序呢？ 同学：猜数游戏程序。 师：对，这是我用VB针对李泳主持的“幸运52”中猜商品价格环节开发的一款程序，我先来说说针对主持人的部分：当李泳宣布商品的价格范围时，比如10000元内，猜商品价格的人就可以在猜数范围栏起始栏填上“0”，终至栏填“10000”，然后再将鼠标移到猜数栏中单击，程序即提示：“准备！倒计时30秒”，当单击提示处，猜价格倒计时开始，猜价格人即可在猜数栏上填上所猜价格的数值，然后根据主持人的提示，选择“不对”重新填写商品价格或选择“正确”让所猜价格在“猜得结果”栏内显示正确结果并停止计时，提示栏中即显示“您猜了M次，对了，恭喜您”。 师：大家觉得程序光有这样的功能神奇吗？ 生：不神奇。 师：对，我也是这样认为的。这个程序神奇的地方在它能帮助猜商品价格人在规定的时间内，根据主持人的提示准确地猜出商品的价格，而且猜中率100%，所以现在“幸运52”停播了，大家知道为什么吗？ 生：不知道。 师：就是因为我开发了这个程序呀！ 生：（有的说信，有的抱着怀疑的态度不吭声，也有说不信的） 师：有同学愿意上来试试吗？ 师：你在纸上写下你的数值范围和要猜的数，然后给大家看一下，别说出来，别让电脑听见了。 师：好，操作程序让程序帮忙把写的数找出来。 （程序找到正确的数） 师：神奇吧。 师：还有那位同学愿意试一下。 师：同样，你还是先写下要猜的数和范围100～200，这次我们不让大家看到他要猜的数，请大家帮忙记下程序每次出现的数字。 师：电脑程序也猜出了正确结果：132。 程序给出的数字是： 第一个数是：150 第二个数是：12 5第三个数是：137 第四个数是：1 31第五个数是：13 4最后是：13 2大家能看出什么规律了吗？ 生：看不出 师：单纯从这几个数当中是看不出什么规律，现在我们依次把这些数放到数轴上，再看一下，大家看能找出什么规律呢？ 同学发言„„ 师：大家认为他说的怎样？为什么不鼓掌呀！ 师：对，正如刚才的同学说的那样，程序是在给定范围内依次找中点方法来找到我们要找的最终数值，这就是我们今天要讨论的一种新的查找方法：对分查找。 师：我们刚才的游戏中的数列是序的吗？ 生：是有序的，升序排列的。 师：如果是降序能用对分查找方式查找吗？ 生：能。 师：大家想一想，如果我们打乱数据的排序顺序，在没有排序的数列中能否用对分查找的方法，找到我们想找到的数据？ 同学：不能。 师：对，这就是对分查找方法的一个特征，或称为条件。因为我们是根据数据的大小找到它在数列中的位置。 【设计意图】通过游戏和对程序给出数值在数轴上的分布分析，让学生初步理解和掌握对分查找的方法及前提条件，为后一阶段对分查找算法的实现作好铺垫。 2．分析实例，实现对分查找算法 师：下面我们一起来看一下程序是怎样一步一步的给出以上数据并最终找到“132”这个数的。 师：首先在100至200之间找中点，然后再用中点值150与所要找的数132比较，得出的结论是所要找的数在100至150之间的数，一下数值的范围就缩小了一半，终止变量j的值就由200变成了150；第二次查找时，程序就给出100至150的中点值125；当程序进行第三次查找时，起始变量i的值就被修改为125，它们的中点值应该是：（125+150）/2=137.5。有小数了，怎么办？ 生：„„（有点茫然） 师：对于小数，程序可以继续查找，但有可能要增加查找次数。为了保证在整数范围内查找，我们就要对含小数的中间值进行处理：取整。大家还记得我们学过VB的取整函数吗？ 生：int。 师：对。即int（137．5），结果是多少？ 生：137。 师：所以我们查找i到j范围内的中点值的表达式应该为：m=int（（i+j）/2）。 师：依次类推，程序会依次给出131、134、132即找到了要找的数。 师：请同学们根据算法逐步求精的原则在下面画出流程图。 （展示如下流程图，然后请同学完成完善对分查找的算法流程图） 流程图补充完善后的结果： 【设计意图】通过对程序给出中间数的分析，帮助学生理解对分查找算法实现的方法，为学生顺利完成对分查找算法流程图给予理论与实践上的支持。 3．推出特例，完善对分查找算法 师：同学们，刚才我们完成的对分查找的流程图；下面请同学们用刚才的查找方法分析一下在199至200范围内要找200这个数，能找到吗？为什么？如何解决这个问题？ （将教室内学生按座位分成若干组，进行讨论。每个组推选一名小 组长，完成后作小组发言） „„ （每一小组完成发言后，老师或点评，或让学生点评） 师：根据刚才同学的讨论分析，那我们先前给出的流程图就有了一些缺陷，怎么修改？ （在同学们的发言声中，修改完善流程图） 修改后的流程图如下： 【设计意图】给出特例，让学生相互讨论、互助学习，归纳总结出上述流程图中出现问题的症结所在，并给出正确的流程图；由此可让学生体验到科学探究的方法，从而培养学生的科学态度与探索精神。 六、课后作业 师：1．在前面的取整中我们用了取整函数int，大家想一想能不能用四舍五入函数处理？如果用四舍五入函数（round）处理，流程图又将怎样修改？ 2．请看教材P40-43，比较我们所给出的流程图与教材上的流程图有什么差异？两个流程图最后结果是否一致，那个流程图的结果有问题，问题是怎么造成的？请写出一篇500—800字的小论文。 （提示：认真阅读教材P40至P43内容，并分析教材中所给算法的逻辑错误） 作业提交方式：电子邮件（校内、校外均可） 邮件名称：登分号+姓名+论文题目 作业提交地址：bdxyz@qq.com 【设计意图】作业（1）扩充课堂内容，丰富学生知识面，丰富学生分别学习内容；作业（2）通过两个流程图之间差异性比较，引导学生判别书本上所给出流程图的逻辑错误，从而培养学生：1．科学的学习态度和精神，不迷信教材、不迷信权威；2．运用论文等形式来表达自己观点；3．通过学生自己的分析、探索，找出教材中的错误。 七、教学反思 整节课充满了笑声和掌声，课堂气氛活跃，学生参与度高。老师的主导作用和学生的主体地位得到了充分的体现。学生在师生互动、生生讨论、生生互助中比较好地掌握了对分查找的思想和算法实现，教学效果好。但由于时间关系，没有将程序的源代码展示给学生，让学生有一种意犹未尽的感觉是本次课的一个缺憾。 五种查找算法总结 一、顺序查找 条件：无序或有序队列。 原理：按顺序比较每个元素，直到找到关键字为止。 时间复杂度：O(n)二、二分查找（折半查找） 条件：有序数组 原理：查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束； 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。 如果在某一步骤数组为空，则代表找不到。 这种搜索算法每一次比较都使搜索范围缩小一半。 时间复杂度：O(logn)三、二叉排序树查找 条件：先创建二叉排序树： 1.若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3.它的左、右子树也分别为二叉排序树。 原理： 在二叉查找树b中查找x的过程为： 1.若b是空树，则搜索失败，否则： 2.若x等于b的根节点的数据域之值，则查找成功；否则： 3.若x小于b的根节点的数据域之值，则搜索左子树；否则： 4.查找右子树。 时间复杂度： 四、哈希表法（散列表） 条件：先创建哈希表（散列表） 原理：根据键值方式(Key value)进行查找，通过散列函数，定位数据元素。 时间复杂度：几乎是O(1)，取决于产生冲突的多少。 五、分块查找 原理：将n个数据元素“按块有序”划分为m块（m ≤ n）。 每一块中的结点不必有序，但块与块之间必须“按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字； 而第2块中任一元素又都必须小于第3块中的任一元素，……。 然后使用二分查找及顺序查找。 《数据结构》 第八次实验报告 学生姓名 学生班级 学生学号 指导老师 重庆邮电大学计算机学院 计算机专业实验中心 一、实验内容 1)有序表的二分查找 建立有序表，然后进行二分查找 2)二叉排序树的查找 建立二叉排序树，然后查找 二、需求分析 二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x 三、概要设计 1、顺序查找，在顺序表R[0..n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示： int SeqSearch(SeqList R,int n,KeyType k){ } int i=0;while(i } if(i>=n){ } printf(“%d”,R[i].key);return i;return-1;else printf(“%d”,R[i].key);i++; 2、二分查找，在有序表R[0..n-1]中进行二分查找，成功时返回记录的位置，失败时返回-1，具体的算法如下： int BinSearch(SeqList R,int n,KeyType k){ } return-1;} int low=0,high=n-1,mid,count=0;while(low<=high){ mid=(low+high)/2;printf(“第%d次查找：在[ %d ,%d]中找到元素R[%d]:%dn ”,++count,low,high,mid,R[mid].key);if(R[mid].key==k) return mid;high=mid-1;low=mid+1;if(R[mid].key>k)else 四、详细设计 源代码： #include static int a[1024],count=0; void Find1(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid]>x)Find1(low,mid-1,x);else if(a[mid] void Find2(int low,int high,int x){ int mid;if(low<=high){ mid=(low+high)/2;count++;if(a[mid] 五、心得体会 通过这次在实现顺序和二分查找算法的过程中，让我对顺序和二分查找算法有了更多的了解。查找根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）的操作，应用十分广泛。顺序查找是一种最简单的查找方法。它的基本思路是：从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,则查找成功；若扫描结束后,仍未找到关键字等于k的记录,则查找失败。二分查找也称为折半查找要求线性表中的结点必须己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。在学习过程中，善于发现，会找到更多的捷径。 六、附录 运行结果截图。 实验五 查找算法 实验项目：必做：顺序查找、折半查找 选做：二叉查找树 实验类型: 验证性 实验内容： 顺序查找：用数组或链表实现，数据有序或无序均可； 折半查找：必须用数组实现，且数据有序； 注意：提交的实验报告要显示已有的数据元素、待查找的数据；应包含查找成功、不成功的情况。第二篇：《对分查找及其算法实现》教学设计
第三篇：五种查找算法总结
第四篇：数据结构实验报告-查找算法
第五篇：数据结构实验指导(实验五：查找算法)
点击咨询 