初中信息技术-Python编程-算法-【分治算法查卡片】

1、初中信息技术Python编程一一算法【分治算法查卡片】在现实生活中，我们经常会遇到一些查找问题，如从书架上找图书如从衣 柜中找衬衣等。这些问题一般规模较小，用穷举法就可以快速解决。信息世界里的问题规模要大很多，如在10亿个网页中查找包含单词 Python的网页，这时我们就需要找到更为高效的方法来缩短查找时间，提高 效率。分治算法那么是解决这类问题的高效算法之一。在本工程中，我们将一起探索基于分治算法的程序设计。分治算法的核心思想是分而治之。采用分治算法，可以逐步缩小问题的求 解范围，从而加快问题的求解速度。通过本节的学习，你将掌握以下技能：*理解用分治算法查找的过程*学会用分治算法设计程序，提

2、高查找效率 专题一：逻辑推演抽查游戏学校开展亲子阅读活动，李明同学完成阅读任务之后，妈妈会填写一张李 明当天完成任务情况的计分卡并保存，爸爸会在每个月初检查上个月李明的阅 读任务完成情况。检查时，爸爸会随机指定一个日期（如29）,然后查看与它对 应的计分卡是否存在。假设每月的计分卡都是按照日期从小到大顺序排放的，如何编写一段程序 模拟快速查找呢?A. 1 B, 25 C. 26 D. 513、列表 nums=3 , 20 , 31 , 39,42 , 50 , 58 , 65中,最后一个元素的 序号是（）。A. 8 B. 7 C.O D.94、歹U表colors：red,yellow”,blu

3、e,“green”white”,中间有几个元素暂时不知道，如何得到最后一个元素的序号？请用Python代码语句表示。通过纸卡查找游戏，探寻分治算法的过程，结合亲子阅读抽查，推演分治 算法的逻辑程序。体验纸卡游戏有9张叠放在一起的纸卡，从上到下编号依次为19 ,随机指定其中 一个纸卡编号x ,比一比看谁能更快地找到它，看一看谁的方法与众不同。在数量较少的情况下，分治算法的优势并不明显。现在把纸卡的数量扩大 到200个,还是自上而下依次从1到200进行编号，并随机指定纸卡编号X。 请再次尝试，看谁的查找方法速度更快。讨论:在有9张卡片的情况下，如果x=7: :1 ,依次翻过前6张纸卡，直到第7次找

4、到目标纸卡，这种方法效率高吗？为什1么？ ：2.在中间位置抽取1张纸卡，发现它的编号为5 ,应该继续往上找还是往下：找？为什么？ 推演算法逻辑纸卡的寻找过程可以概括为在有序列表中查找指定值，亲子阅读抽查也属于同类问题。这类问题一般分为两种情况：如果可以找到目标值，求解结果为目标值在列表中的序号；如果无法找到目标值，求解结果返回-1。假设8月份李明共获得12张计分卡，日期从小到大依次为1、5、7、8、12、15、18、21、27、29、30、31,李明妈妈已经从1到12编好序号，李明 爸爸抽查的日期为X。如果x=29 ,将查找范围的起始序号记作a、结束序号记作b ,中位序号记作m （ m的值等于

5、a, b平均数的整数局部），分治算法的执行过程如下列图所示。xs29标具为10由9 ：目标值为29时的查找过程在查找过程中：初始情况下（区域）,查找范围为112。由于x取值大于中位元素值（m对应的列表项），查找范围折半，取右侧（ 区域），继续查找。依次类推，直到查找范围缩减为10-10 （区域）此时，x取值等于中位讨论 如果x=7 ,分治算法的执行过程是怎样的?元素，确认求解结果为10。专题二：编程实现快速查找定义一个名为search的函数来实现分治算法。编写分治算法函数代码.自定义函数。为分治算法设计一个名称为search的自定义函数，包括cards、X两个输 入参数。出cards对应升序列

6、表，x对应整数查找目标。.设置查找范围。用a、b表示起始、结束序号，赋值代码如下：a=lb=len（cards）- 1说明：Python中列表序号是从0开始的，但我们弃用0号元素，所以a的初值为 lo b的初值等于最后一个元素序号，即len（cards）-l。（a+b）2计算获得中位序号。 是整除运算符号。.逐级分割查找范围，缩小查询规模。如果起始序号不大于结束序号，那么cards中取中位序号m对应的值 cardsm与x进行比拟。如果x等于cardsm,代表找到目标，返回mo如果x小于cardsm,令结束序号b等于m-1 ,往前寻找（折半取左侧）。如果x大于cardsm,令开始序号a等于m+1

7、，往后寻找（折半取右侧）。如果在cards中无法找到x ,那么返回程序代码如下:123456789101112131415#search函数程序def search(cards=listx=int):a=lb=len(cards)-l#逐级分割查找范围，缩小查询规模while a = b:m=(a+b)/2print(m=Jm) #跟踪中位序号 if x=cardsm:return melif x0:I print（“抽查日期的序号为:y）print（“恭喜，可获得神秘礼物”）else:print （“抽查日期“，r不存在”）print。本月没有神秘礼物，下月继续努力哦！）在程序中：首先准备原

8、始数据，存储在列表d中对应8月份李明的阅读记分卡（弃用 0号元素，卡片编号从1开始），对应抽查日期。调用search函数，把列表d传递给参数cards，把r传递给参数x ,将返 回结果赋值给变量y0如果y大于0 ,证明在列表d中找到了抽查日期r,显示序号；否那么，显 示不存在。2.3运行完整程序，交流查询结果观察执行结果，可以发现中位序号m的取值以及最终的求解结果，跟前文 逻辑推演情况完全一致034567891011121314151617181920212223242526#search函数程序def search(cards=listJx=int):a=lb=len(cards)-l#逐级

9、分割查找范围，缩小查询规模while a = b:m=(a+b)/2print(,m=,m) #跟踪中位序号if x=cardsm: return m elif x, r）if y0:print（抽查日期J的序号为:y）prirrt（“恭喜，可获得神秘礼物”）else:print （抽查日期二r不存在”）print（“本月没有神秘礼物，下月继续努力哦！ “）控制台m= 6m= 9m= 11m= 10抽查Id期29的序号为10 恭喜,可获得神秘礼物 程序运行结束请将查找目标r的值依次修改为7、28并执行程序，观察执行结果与你的 逻辑推演情况是否一致。拓展阅读分治算法执行效率分析执行一个算法所耗费

10、的时间，必须上机运行测试才能知道，但它的值与算 法中语句的执行次数成正比，哪个算法中语句执行次数少，耗费时间就少，耗 费时间较少的算法执行效率高。同学们上面所学的分治算法，通常被称作二分查找算法，也叫作折半查找 算法，是最为典型的一种分治算法，其优点是执行效率比拟高，缺点是对列表 有特殊要求（列表必须是有序排列的）。二分查找算法每次循环可以将查找规模缩小一半。当问题规模足够大时， 如在2017年全国4442.06万初中在校生中查找某个身份证号，最差的情况下 （在列表中不存在）循环比照次数不超过30次，与穷举算法的4442.06万次 相比，效率的提升是显而易见的。巩固与提高1、关于分治算法的说法错误的选项是（）。A.采用分治算法，可以逐步缩小问题的求解范围B.二分查找法要求