3.7对分查找算法及程序实现.ppt

3 7对分查找算法及程序实现 1 对分查找的概念对分查找又称二分查找 是一种高效的查找方法 对分查找的前提是 被查找的数据序列是有序的 升序或降序 对分查找的基本思想是在有序的数列中 首先将要查找的数据与有序数列内处于中间位置的数据进行比较 如果两者相等 则查找成功 否则就根据数据的有序性 再确定该数据的范围应该在数列的前半部分还是后半部分 在新确定的缩少范围内 继续按上述方法进行查找 直到找到要查找的数据 即查找成功 如果要查找的数据不存在 即查找不成功 2 对分查找的过程若key为查找键 数组d存放n个已按升序排序的数据 在使用对分查找时 把查找范围 i j 的中间位置上的数据d m 与查找键key进行比较 结果必然是如下三种情况之一 1 若keyd m 由与 1 相同的理由 必须在新的范围 m 1 j 中继续查找 这样 除了出现情况 2 在通过一次比较后 新的查找范围将不超过上次查找范围的一半 中间位置数据d m 的下标m的计算方法 m i j 2或m fix i j 2 以规模为16的递增数组d为例 观察对分查找的过程 要查找的数据key为37 3 对分查找算法的表示使用对分查找在数组变量d中查找key 用自然语言描述的算法如下 1 确定初始查找范围 i 1 j n 2 是否能继续查找 如果i j 那么转到 4 3 找不到 输入出结果0 算法结束 4 计算中点位置 m i j 2 5 相等 如果d m key 那么转到 7 6 修改查找范围 如果key d m 那么j m 1 否则i m 1 转到 2 7 找到 输出结果m 算法结束 使用流程图描述对分查找的算法如下图所示 4 对分查找算法程序的实现要点 1 由于比较次数难以确定 所以用Do语句来实现循环 2 在Do循环体中用If语句来判断查找是否成功 3 若查找成功则输出查找结果 并结束循环 ExitDo 4 若查找不成功 则判断查找键在数组的左半区间还是右半区间 从而缩小范围 对分查找的程序结构如下 升序序列 对分查找程序的基本框架 PrivateSubCommand1 Click i 1 j nDoWhilei jm i j 2Ifd m KeyThen 输出结果 退出查找 代码略 ElseIfKey d m Thenj m 1Elsei m 1EndIfLoopEndSub 查找次数的估算对规模为n的数组进行对分查找时 无论是否找到 至多进行log2n 1 log2n表示大于或等于log2n的最小整数 次查找就能得到结果 而使用顺序查找算法 在最坏的情况下 查找键在最后一个或没找到 需要进行n次查找 最好的情况是一次查找 查找键在第一个 平均查找次数是 本节的学习要求掌握对分查找算法的基本思想 掌握对分查找算法的程序实现要点 学会编写简单的对分查找的程序 掌握对顺序查找与对分查找次数的估算 对分查找算法在历次考试中出现的概率为90 以上 考查方式为选择题与填空题 1 下列有关查找的说法 正确的是 A 顺序查找时 被查找的数据必须有序B 对分查找时 被查找的数据不一定有序C 顺序查找总能找到要查找的关键字D 一般情况下 对分查找的效率较高 D 2 某网站报名参加免费三亚游的会员序列号有 101 135 238 342 450 558 633 708 846 910 采用对分查找 查找序列号为846号网友信息的过程中 依次被访问的序列号是 A 450 708 846B 450 708 910 846C 558 708 846D 558 708 910 846 A 3 某电子图书馆网站有10万本图书记录 已索引排序 假设从中取出一条记录并与待查找项进行比较所花时间为10毫秒 则用对分法在该系统中查找任意一本指定图书最多花费的时间约为 A 100万毫秒B 50万毫秒C 10毫秒D 170毫秒 D 4 某数组有7个元素 依次为158 234 369 478 552 697 748 若采用对分查找法在该数组中查找数据748 需要查找的次数是 A 1B 2C 3D 4 C 5 在有序单词序列 As Book Door English Floyd Good Hello Sun中 用对分查找法找到单词 Good 所需要的查找次数是 A 1B 2C 3D 4 B 6 某8位男生的肺活量数据放在数组元素a l 到a 8 中 其数据依次为 3205 3408 3471 3498 3621 3829 4233 4540 使用对分查找 设定查找键key 若第一个被访问到的数据是3498 小于key值 则第二个被访问到的数据是 A 3408B 3829C 4233D 4540 B 7 使用对分查找在已排序的数组d 数组元素d l d 2 d n 中查找key的算法流程图如下 其中 框中的内容分别是 A j m 1 i m 1B j m 1 i m 1C j m 1 i m 1D j m 1 i m 1 C 8 有两组数据 54 31 43 12 8 73 56 34 89 60 23 67 87 83 75 70 63 59 55 37 33 21 17 7下列有关查找方法描述不正确的是 A 可以直接使用顺序查找B 可以直接使用对分查找C 可以直接使用对分查找D 可以直接使用顺序查找 C 9 某查找算法的部分VB程序代码如下 t Falsei 0DoWhilei 7Andt Falsei i 1Ifd i KeyThent TrueLoopIft FalseTheni 0数组元素d 1 到d 7 的数据依次为 8 9 5 8 4 7 8 当变量key的值为8时 运用该算法处理后 变量i的值是 A 1B 2C 4D 7 A 在一行数据 1 23 6 2 4 5 6 18 5 19 中 存在连续递增的数据序列 1 23 6 2 4 5 6 18 5 19 其序列长度分别为2 1 5 2 则连续递增的数据序列长度最大值max 5 寻找max的方法如下 从第二个数据开始 将该数与它的前一个数比较 如果该数大于它的前一个数 则k k 1 否则k 1 直到最后一个数据处理完成为止 在此过程中将k的最大值保存在变量max中 依据上述算法描述编写的VB程序如下 但加框处代码有错 请改正 1 加框 处应填入 2 加框 处应填入 max k Constn 10Dima 1Ton AsInteger Text1 KeyPress过程用于输入数据并将数据依次存放到数组a中PrivateSubText1 KeyPress KeyAsciiAsInteger 该过程代码略EndSubPrivateSubCommand1 Click DimiAsIntegerDimkAsInteger 连续递增的数据序列长度DimmaxAsInteger 连续递增的数据序列长度最大值max 1k 1Fori 2TonIfa i a i 1 Thenk k 1Elsek 1 1 Ifk maxThenk max 2 NextiText2 Text Str max EndSub a i 1 某学校把每个学生的姓名和家长联系电话保存到计算机中 以便遇到紧急情况时可以及时通知学生家长 每个学生的姓名和家长联系电话已经保存在数组xm和phone 都为字符串类型 中 现在要设计一个根据输入的学生姓名查询该学生家长的联系电话的程序 程序运行时的界面如下图所示 完善程序 下列程序运行时 在Text1中输入学生姓名 单击 查询家长电话 按钮Command1后 在标签Label2中显示对应的学生家长电话 若找不到则显示 未找到该学生 程序代码如下 Dimxm 1To1000 AsStringDimphone 1To1000 AsStringConstnAsInteger 1000PrivateSubCommand1 Click DimxAsStringDimfindAsBooleanDimiAsIntegerx Text1 Texti 0find FalseDoWhile i n Andfind False If Thenfind TrueLoopIffind TrueThenLabel2 Caption 该学生家长联系电话为 phone i ElseLabel2 Caption 未找到该学生 EndIfEndSubPrivateSubForm Load 学生姓名及家长电话数组赋初值语句 忽略EndSub 请阅读代码并问答下列问题 1 解决此问题的算法是 在程序 和 划线处填入适当的语句或表达式 将程序补充完整 2 程序中 划线处应填入 3 程序中 划线处应填入 注 该示例程序在素材文件夹下vb33文件夹中 顺序查找算法 i i 1 x xm i 12 某中学2009年下半年和2010年上半年各有300名和100名学生参加信息技术高考 下列VB程序用于统计参加过这两次考试的学生信息 其中Command1 Click过程的算法流程图如下所示 VB程序代码如下所示 Dima 1To300 AsString 用于存放2009年下半年考试学生的身份证号码Dimb 1To100 AsString 用于存放2010年上半年考试学生的身份证号码 FormLoad过程用于进行一些初始化准备工作PrivateSubForm Load 将参加2009年下半年考试学生的身份证号码放在数组a中 将参加2010年上半年考试学生的身份证号码放在数组b中 将数组a中数据升序排列 将数组a和数组b中的数据分别显示在列表框List1和List2中 代码略EndSub 请回答下列问题 1 流程图中虚线框部分所采用的查找算法名称是 2 加框 处代码有错 应改为 3 加框 处代码有错 应改为 Command1 Click 过程用于统计参加过这两次考试的学生信息PrivateSubCommand1 Click DimiAsInteger botAsInteger topAsInteger mAsIntegerFori 1To300 bot 1top 300DoWhilebotb i Thenm bot 1 Elsebot m 1EndIfLoopNextiEndSub 对分查找算法 Fori 1to100 top m 1 13 按学号查找成绩 新生分班结束了 教务处将学生学号 学生班级和分班考试成绩录入到计算机中 为方便学生查询录取情况 编制了一个根据学生学号查找某位学生所在班级及分班考试成绩的程序 如下图所示 程序运行后 同学可以自己输入自己的学号 然后单击 开始查找 按钮 计算机即可显示该同学的班级和成绩 如果学号错误 则显示 未找到该学生信息 实现该程序的部分代码如下 Constn 100Dimxh 1Ton AsIntegerDimcj 1Ton AsSingleDimbj 1Ton AsStringDimxAsIntegerFunctionfind i j AsIntegerDimmAsIntegerDoWhilei jm Fix i j 2 Ifxh m xThenfind mExitFunctionEndIfIfx xh m Thenj m 1Elsei m 1EndIfLoopfind 1EndFunction PrivateSubCommand1 Click DimiAsInteger jAsIntegerDimkAsInteger cAsInteger sAsStringDimrAsInteger 以学号为关键字对成绩表和班级表进行升序排序Fori 1Ton 1Forj nToi 1Step 1Ifxh j xh j 1 Thenk xh j 1 xh j 1 xh j xh j kc cj j 1 cj j 1 cj j cj j cs bj j 1 bj j 1 bj j bj j sEndIfNextjNexti List1 ClearFori 1To100List1 AddItemStr xh i bj i Str cj i Nexti 根据输入的学号查找对应的班级和分班考试成绩r 1x Val Text1 Text x变量待查找学生序号r find 1 n Ifr 1ThenText2 Text 未找到该学生信息 ElseText2 Text bj r Str cj r EndIfEndSubPrivateSubForm Load 数组初始化语句 忽略EndSub 回答下列问题 1 程序中排序采用的是哪种排序算法 2 程序是查找采用的是哪种查找算法 3 显示查找结果的控件属于 类 该控件的名称是 4 如果有100名同学的分班成绩存储在计算机中 现在要查找按学号升序规律排在第23位同学的分班情况及成绩 按照上述程序的查找算法 一共需要几次比较才能找到该同学的数据 冒泡排序算法 对分查找算法 Text2 6 文本框 小杨设计了某单位的公积金查询系统 输入职工的公积金账号 可以查出该账号对应的余额 所有职工的公积金账号和相应的余额已分别保存在数组a 按从小到大排序 和数组b中 第i个职工的账号保存在a i 中 对应的账号余额保存在b i 中 程序界面如图所示 左边列表框List1中显示的是部分职工的账号和余额 在文本框Text1中输入职工的公积金账号 单击 查询余额 按钮 Command1 后 如果找到此账号 则在标签Label2中显示 此账号余额为 和账号对应的余额值 如果未找到则显示 找不到此账号 请重新输入 解决此问题的算法流程图如图所示 相应的查找部分程序段如下 Dima 1Ton AsLongDimb 1Ton AsSinglePrivateSubCommand1 Click DimxAsLong iAsLong jAsLong mAsLong fAsBooleanx Val Text1 Text i 1 j n f False 设账号总数为nDoWhile i j AndNotf Ifx a m Thenf TrueElseIfx a m Thenj m 1Else EndIfLoopIffThenLabel2