信息技术（基础模块上下册）5.3 运用典型算法

5.3运用典型算法第5单元

程序设计入门任务1运用排序算法列表1数据处理通常会涉及很多数据，这些数据需要一个容器进行管理，这个容器就是数据结构，Python中的数据结构主要有序列(列表、元组等)集合和字典。列表(list)是Python最常用的序列，具有可变性，可以追加、插、删除和替换元素。创建列表创建列表可以使用方括号“[]”将元素括起来，元素之间用逗号分隔。a=[12,35,56,23]b=['张三','李四','王五']列表1追加元素a=[12,35,56,23]a.append(30)#在列表后面追加一个元素a+=[30,40]#利用“+=”运算符在列表后面追加多个元素a.extend([30,40])#利用“extend()”方法在列表后面追加多个元素要在列表中追加单个元素,可使用append()方法；要在列表中追加多个元素或另一个列表，可使用“+=”运算符或extend()方法。列表1插入元素a=[12,35,56,23]a.insert(2,30) #在列表索引2（第3个元素）位置上插入一个元素使用insert()方法可以在列表中指定索引位置插入一个元素。替换元素使用“=”运算符可以替换列表的元素。a=[12,35,56,23]a[1]=10#在列表索引1位置上将35替换为10列表1删除元素a=[12,35,56,23]a.remove(35)#在列表中查找第一个值为35的元素并删除a.pop(1)#删除列表索引1位置上的元素使用remove()方法或pop()方法可以删除列表中的元素。remove()方法从左至右查找列表中的元素，如果找到匹配的元素则删除；如果找到多个匹配元素，只删除第一个；如果没有找到则提示错误。pop()方法删除指定索引位置上的元素，如果不指定索引位置，则删除最后一个元素。选择排序算法2选择排序基本思路：每次从待排序的数据中选出最小元素，顺序放在之前已经排好序的数据最后，直到全部数据排序完毕。实现方法：取第一个数和后面的数逐一比较，然后一轮之后得到最小的数放在第一个，然后开始取第二个,重复之前的比较。选择排序算法27459821145982712598471249857124589712457981245789初始状态：第1轮：第2轮：第3轮：第4轮：第5轮：第6轮：选择排序算法2假设排序列表为a，数据个数为n。a=[7,4,5,9,8,2,1]foriinrange(len(a)-1):minIndex=i#记录最小数索引

forjinrange(i+1,len(a)):ifa[minIndex]>a[j]:#若找到更小的数

minIndex=j#将找到的最小数和未排序的第一个数交换

a[i],a[minIndex]=a[minIndex],a[i]print(a)插入排序算法3插入排序基本思路：每次取出一个待排序的数据元素，按其大小插入到之前已经排好序的数据集中，直到全部待排序元素插入完毕。具体实现方法为：从左边开始取值，然后和它左边的所有元素值进行比较，如果取的值比它左边的值小就与其交换，重复以上操作。插入排序算法37459821475982145798214579821457892124578911245789初始状态：第1轮：第2轮：第3轮：第4轮：第5轮：第6轮：插入排序算法3假设排序列表为a，数据个数为n。a=[7,4,5,9,8,2,1]foriinrange(1,len(a)):#从第二个数开始

forjinrange(i-1,-1,-1):#从外层循环的下标值比较到第一个数

ifa[j+1]<a[j]:#若找到更小的数

a[j+1],a[j]=a[j],a[j+1]#较小的值左移print(a)Python功能库4Python既有内置函数和标准库，又有第三方库和工具，可用于文件读写、网络抓取和解析、数据库连接、音视频处理、数据挖掘、机器学习等，灵活运用Python功能库，能够扩展程序功能，提高编程效率。通常用import命令就可以引Python功能库，例如，要与MySQL数据库建立连接，就要使用第三方库pymysql，引入这个库的语句为:importpymysql实践体验5编写篮球比赛积分排名程序。分析问题设计算法编写程序调试运行课后拓展6采用插入排序算法，对某一字符列表进行降序排序。操作提示：字符排序是按照字符的ASCII码顺序，且相同字母的大小写其ASCII码不相同。02

巩固提高01讨论与交流通过网络查阅并讨论其他排序算法。任务2运用查找算法顺序查找算法1顺序查找也称线性查找，即从数据结构线性表的一端开始，顺序扫描，依次将扫描到的关键字与给定值相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于给定值的数据，表示查找失败。顺序查找多用于查找对象的排列无规律时。假设查找列表为a，对象个数为n，算法流程图如图所示。流程图顺序查找算法1a=['B','A','E','F','D','C']target='E'#查找目标i=0#初始查找位置found=False#查找是否成功标志whilei<len(a)andnotfound:#未扫描完且未找到则循环查找

ifa[i]==target:#查找匹配对象

found=Trueelse:i+=1#未找到继续扫描下一个对象print(found)示例代码二分查找算法2二分查找也称折半查找，比顺序查找的效率高，但它要求待查数据结构是有序排列的，适用于不经常变动且查找频率较高的有序数据。二分查找从数据结构的中间位置开始，如果中间元素正好与查找关键字相等，则查找成功；否则利用中间位置将数据分成前、后两个部分，如果中间元素大于查找关键字，则继续在前一半数据中查找，否则继续在后一半数据中查找，重复这样的操作，每一次比较都使搜索范围缩小一半。二分查找算法2如要在序列“10,20,40,60,70,80,90”中查找70，查找过程示意图如图所示。1020406070809070809070第1轮：第2轮：第3轮：偏小偏大正确二分查找算法2假设查找列表a，对象个数为n。a=[10,20,40,60,70,80,90]#有序列表target=70#查找目标i=0#初始查找位置j=len(a)-1whilei<=j:m=(i+j)//2#取中间值

ifa[m]==target:print("所查对象位置下标:",m)breakelifa[m]>target:j=m-1else:i=m+1流程图示例代码实践体验3编写英语单词默写程序。分析问题设计算法编写程序调试运行课后拓展402

巩固提高01讨论与交流通过网络查阅并讨论其他查找算法，讨论5.2任务2中猜数字游戏，用哪种查找方式速度最快。某公司举行新产品发布会，参会客户都进行了登记，采用二分查找算法，在登记表中查找是否有某一客户参会。操作提示:需要先按照客户名称排序。课后拓展503

探究与合作1.玩转“汉诺塔”游戏——递归算法“汉诺塔”是一个古老的益智游戏，如图所示，木板上有3根柱子，分别是原始柱、借力柱和目标柱，原始柱上有若干个圆盘，规定每次只能移动一个圆盘，且小的圆盘只能叠在大的圆盘上面。请设计算法，用尽可能少的次数把所有圆盘从原始柱全部移动到目标柱上。操作提示：递归算法是一种直接或者间接调用自身的算法(如函数的自调用)，它体现了“以此类推”“用同样的步骤重复”的思想，可以使算法的描述简洁，易于理解，其实质是把问题转换为规模缩小了的同类问题。课后拓展503

探究与合作2.绘制递归图形Python程序中内置了大量的函数，turtle模块是其中一个绘制图形的函数库，就像一只小乌龟，在一个横轴为x、纵轴为y的坐标系原点(0