资源简介

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
选择排序基本思路：每次从待排序的数据中选出最小元素，顺序放在之前已经排好序的数据最后，直到全部数据排序完毕。实现方法：取第一个数和后面的数逐一比较，然后一轮之后得到最小的数放在第一个，然后开始取第二个,重复之前的比较。
选择排序算法
2
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}7
4
5
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
4
5
9
8
2
7
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
5
9
8
4
7
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
9
8
5
7
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
5
8
9
7
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
5
7
9
8
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
5
7
8
9
初始状态：
第1轮：
第2轮：
第3轮：
第4轮：
第5轮：
第6轮：
选择排序算法
2
假设排序列表为a，数据个数为n。
a=[7,4,5,9,8,2,1]
for i in range(len(a)-1):
minIndex=i #记录最小数索引
for j in range(i+1,len(a)):
if a[minIndex]>a[j]: #若找到更小的数
minIndex=j #将找到的最小数和未排序的第一个数交换
a[i],a[minIndex]=a[minIndex],a[i]
print(a)
插入排序算法
3
插入排序基本思路：每次取出一个待排序的数据元素，按其大小插入到之前已经排好序的数据集中，直到全部待排序元素插入完毕。具体实现方法为：从左边开始取值，然后和它左边的所有元素值进行比较，如果取的值比它左边的值小就与其交换，重复以上操作。
插入排序算法
3
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}7
4
5
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}4
7
5
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}4
5
7
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}4
5
7
9
8
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}4
5
7
8
9
2
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}2
4
5
7
8
9
1
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}1
2
4
5
7
8
9
初始状态：
第1轮：
第2轮：
第3轮：
第4轮：
第5轮：
第6轮：
插入排序算法
3
假设排序列表为a，数据个数为n。
a=[7,4,5,9,8,2,1]
for i in range(1,len(a)): #从第二个数开始
for j in range(i-1,-1,-1): #从外层循环的下标值比较到第一个数
if a[j+1] a[j+1],a[j]=a[j],a[j+1] #较小的值左移
print(a)
Python功能库
4
Python既有内置函数和标准库，又有第三方库和工具，可用于文件读写、网络抓取和解析、数据库连接、音视频处理、数据挖掘、机器学习等，灵活运用 Python功能库，能够扩展程序功能，提高编程效率。
通常用 import命令就可以引Python功能库，例如，要与 MySQL数据库建立连接，就要使用第三方库 pymysql，引入这个库的语句为:
import pymysql
实践体验
5
编写篮球比赛积分排名程序。
课后拓展
6
采用插入排序算法，对某一字符列表进行降序排序。
操作提示：字符排序是按照字符的ASCII码顺序，且相同字母的大小写其ASCII码不相同。
02
巩固提高
01
讨论与交流
通过网络查阅并讨论其他排序算法。
任务 2
运用查找算法
顺序查找算法
1
顺序查找也称线性查找，即从数据结构线性表的一端开始，顺序扫描，依次将扫描到的关键字与给定值相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于给定值的数据，表示查找失败。顺序查找多用于查找对象的排列无规律时。假设查找列表为a，对象个数为n，算法流程图如图所示。
流程图
顺序查找算法
1
a=['B','A','E','F','D','C']
target='E' #查找目标
i=0 #初始查找位置
found=False #查找是否成功标志
while i if a[i]==target: #查找匹配对象
found=True
else:
i+=1 #未找到继续扫描下一个对象
print(found)
示例代码
二分查找算法
2
二分查找也称折半查找，比顺序查找的效率高，但它要求待查数据结构是有序排列的，适用于不经常变动且查找频率较高的有序数据。二分查找从数据结构的中间位置开始，如果中间元素正好与查找关键字相等，则查找成功；否则利用中间位置将数据分成前、后两个部分，如果中间元素大于查找关键字，则继续在前一半数据中查找，否则继续在后一半数据中查找，重复这样的操作，每一次比较都使搜索范围缩小一半。
二分查找算法
2
如要在序列“10,20,40,60,70,80,90”中查找70，查找过程示意图如图所示。
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}10
20
40
60
70
80
90
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}70
80
90
{5C22544A-7EE6-4342-B048-85BDC9FD1C3A}70
第1轮：
第2轮：
第3轮：
偏小
偏大
正确
二分查找算法
2
假设查找列表a，对象个数为n。
a=[10,20,40,60,70,80,90] #有序列表
target=70 #查找目标
i=0 #初始查找位置
j=len(a)-1
while i<=j:
m=(i+j)//2 #取中间值
if a[m]==target:
print("所查对象位置下标:",m)
break
elif a[m]>target:
j=m-1
else:
i=m+1
流程图
示例代码
实践体验
3
编写英语单词默写程序。
课后拓展
4
02
巩固提高
01
讨论与交流
通过网络查阅并讨论其他查找算法，讨论5.2任务2中猜数字游戏，用哪种查找方式速度最快。
某公司举行新产品发布会，参会客户都进行了登记，采用二分查找算法，在登记表中查找是否有某一客户参会。操作提示:需要先按照客户名称排序。
课后拓展
5
03
探究与合作
1.玩转“汉诺塔”游戏——递归算法
“汉诺塔”是一个古老的益智游戏，如图所示，木板上有3根柱子，分别是原始柱、借力柱和目标柱，原始柱上有若干个圆盘，规定每次只能移动一个圆盘，且小的圆盘只能叠在大的圆盘上面。请设计算法，用尽可能少的次数把所有圆盘从原始柱全部移动到目标柱上。
操作提示：递归算法是一种直接或者间接调用自身的算法(如函数的自调用)，它体现了“以此类推” “用同样的步骤重复”的思想，可以使算法的描述简洁，易于理解，其实质是把问题转换为规模缩小了的同类问题。
课后拓展
5
03
探究与合作
2.绘制递归图形
Python程序中内置了大量的函数，turtle模块是其中一个绘制图形的函数库，就像一只小乌龟，在一个横轴为x、纵轴为y的坐标系原点(0,0)位置开始，根据一组函数指令的控制，在这个平面坐标系中移动，从而在它爬行的路径上绘制了图形。尝试绘制一个自己喜欢的递归图形。
单元小结
6
本单元主要学习了算法的基本概念，计算机程序、程序设计语言、程序基本结构、Python基本语法及排序算法、查找算法等典型算法的基础知识，初步掌握了程序设计的方法，能使用程序设计工具编辑、运行和调试简单的程序，具备了运用程序设计解决简单问题的初步能力。
谢谢观看！

展开更多......

收起↑