5.3 运用典型算法（课件）-《信息技术基础模块下册》（高教版）同步精品课堂

5.3 运用典型算法 信息技术基础模块下册 同步精品课堂 高教版 1 一 教学目标 知识目标 （1）了解排序算法和查找算法的基本概念 （2）了解Python中的列表数据结构 （3）了解Python中的功能库概念 （4）了解递归算法的概念 技能目标 （1）掌握使用Python排序查找方法 （2）掌握使用递归算法设计程序的方法 二 教学重难点 教学重点 （1）排序算法的工作原理 （4）Python功能库的引入和使用方法。（2）查找算法的工作原理 （5）递归算法的概念和设计方法 （3）Python列表数据结构的基本操作方法 教学难点 （1）排序算法的时间复杂度分析和最优选择。 （2）查找算法的时间复杂度分析和最优选择。 （3）Python列表数据结构的灵活运用。 （4）Python功能库的合理选择和使用。 （5）递归算法的设计技巧 通过前面的学习，我们知道使用计算机解决问题最重要的一个步骤是“设计算 法”。算法可能是一个计算公式，可能是一个赢得游戏的策略，也可能是一个解决综合 问题的复杂方案。人们在长期实践中，总结出很多算法，为编写程序提供了极大的帮助，并在现实生活各领域广泛应用。随着计算机和人工智能的发展，算法仍然在不断发展。 本节将学习几种典型算法，掌握程序设计的一些技巧。 三 导入新课 排序是数据处理中经常使用的一种算法，即把数据按照从小到大或从大到小的顺序进行排列，如排列体育赛事成绩、员工经营业绩等。 排序算法有很多，如选择排序、插入排序、冒泡排序、堆排序、归并排序等。 下面以选择排序和插入排序为例，介绍排序算法的思路。 四 新知讲授 1.运用排序算法 1. 列表 数据处理通常会涉及很多数据，这些数据需要一个容器进行管理，这个容器就是数 据结构， Python 中的数据结构主要有序列(列表、元组等)、集合和字典。列表 (list)是 Python 最常用的序列，具有可变性，可以追加、插入、删除和替换元素。 四 新知讲授 1.运用排序算法 (1)创建列表 创建列表可以使用方括号“□”将元素括起来，元素之间用逗号分隔，如： a=[12,35,56,23] b=[ '张三','李四，'王五] (2) 追加元素 要在列表中追加单个元素，可使用appendO 方法；要在列表中追加多个元素或另一 个列表，可使用“+=”运算符或 extendO 方法，如： a=[12,35,56,23 a.append(30)#在列表后面追加一个元素 a+=[30,40]# 利用“+=”运算符在列表后面追加多个元素 a.extend([30,40])#利用“extend )”方法在列表后面追加多个元素 四 新知讲授 1.运用排序算法 (3) 插入元素 使用 insert) 方法可以在列表中指定索引位置插入一个元素，如： a=[12,35,56,23] ……………………………………………………… a.insert(2,30)#在列表索引2(第3个元素)位置上插入一个元素 (4) 替换元素 使用“=”运算符可以替换列表的元素，如： a=[12,35,56,23] a[1]=10 #在列表索引1位置上将35替换为10 四 新知讲授 1.运用排序算法 使用文本文档，录入中文文章，将完成时间记录在表 四 新知讲授 运用排序算法 (5) 删除元素 使用 remove)方法或popO方法可以删除列表中的元素。 remove)方法从左至右查找 列表中的元素，删除第一个匹配的元素，如果没有找到则提示错误。pop)方法删除指定索引位置上的元素，如果不指定索引位置，则删除最后元素，如： 图5-18 中示例代码如下。 四 新知讲授 2 选择排序算法 选择排序基本思路：每次从待排序的数据中选出最小元素，顺序放在之前已经排好 序的数据最后，直到全部数据排序完毕。实现方法：取第一个数和后面的数逐一比较， 然后一轮之后得到最小的数放在第一个，然后开始取第二个，重复之前的比较，示意图如图5-18所示。 图5-18 中示例代码如下。 假 设 排 序 列 表 为 a, 数 据 个 数 为 n, 选 择 排 序 算 法 流 程 图 如 图 5 - 1 9 所 示 。 四 新知讲授 四 新知讲授 3. 插入排序算法 插入排序基本思路：每次取出一个待排序的数据元素，按其大小插入到之前已经排 好序的数据集中，直到全部待排序元素插入完毕。具体实现方法为：从左边开始取值然后和它左边的所有元素值进行比较，如果取的值比它左边的值小就与其交换，重复以上操作，如图5 - 20所示。 图5-20 中示例代码如下。 假设排序列表为a,数据个数为n,插入排序算法流程图如图5-21所示。 四.新课讲授 四.新课讲授 4.Python 功能库 Python 既有内置函数和标准库，又有第三方库和工具，可用于文件读写、网络抓取 和解析、数据库连接、音视频处理、数据挖掘、机器学习等，灵活运用Python 功能库， 能够扩展程序功能，提高编程效率。 通常用 import 命令就可以引入 Python 功能库，例如，要与MySQL数据库建立连接， 就要使用第三方库 pymysql, 引入这个库的语句为： import pymysql 师生互动 编写篮球比赛积分排名程序 学校近期举行篮球比赛，需要根据各班级的积分进行排名。 1. 分析问题、设计算法 设各班级积分列表为 “integral”, 排名通常按积分从高到低进行排序，可以使用 上面介绍的任意一种排序算法。注意，因积分需要从高到低排序，在比较两个数时，找到较大的数应往前排。 2. 编写程序 若采用选择排序算法，编写如下程序代码片段。 师生互动 在 Python 中还可以用内置函数 sorted 实现排序功能，使用更加方便，该函数的语法为： sorted(list, reverse =False/True) 其 中 ，reverse 为排序规则， False 为 升 序 ( 默 认 ) ,True 为降序。 因此，本例还可以采用以下代码片段实现积分从高到低排序。 sorted(integral, reverse = True ) print(integral) 2. 创建数据透视图 四.新知讲授 2. 运用查找算法 查找也是经常使用的一种算法，即根据给定的某个值，在一组数据中确定一个关键字的值等于给定值的记录或数据元素，如查找列车车次、航班号、员工姓名等。 查找算法也有很多，如顺序查找、二分查找、插值查找、分块查找、二叉树查找、哈希表查找等。下面以顺序查找和二分查找为例，介绍查找算法的思路。 使用文本文档，录入中文文章，将完成时间记录在表 四.新知讲授 1. 顺序查找算法 顺序查找也称线性查找，即从数据结构线性表的一端开始，顺序扫描，依次将扫描 到的关键字与给定值相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等 于给定值的数据，表示查找失败。顺序查找多用于查找对象的排列无规律时。假设查找列表为a, 对象个数为n, 算法流程图如图5-22所示。 示例代码如下。 使用文本文档，录入中文文章，将完成时间记录在表 四 新知讲授 2. 二分查找算法 二分查找也称折半查找，比顺序查找的效率高，但它要求待查数据结构是有序排 列的，适用于不经常变动且查找频率较高的有序数据。二分查找从数据结构的中间位 置开始，如果中间元素正好与查找关键字相等，则查找成功；否则利用中间位置将数 据分成前、后两个部分，如果中间元素大于查找关键字，则继续在前一半数据中查找， 否则继续在后一半数据中查找，重复这样的操作，每一次比较都使搜索范围缩小一半。如要在序列“10,20,40,60,70,80,90”中查找70,查找过程示意图如图5-23所示。 使用文本文档，录入中文文章，将完成时间记录在表 四.新知讲授 图5-23所示示例的代码如下。 使用文本文档，录入中文文章，将完成时间记录在表 四.新知讲授 假 设 查 找 列 表a, 对 象 个 数 为n, 二分查找算法流程图如图5 - 24所示。 师生互动 编写英语单词默写程序 默写英语单词，和英语生词表对照，看是否正确。 1. 分析问题、设计算法 设英语生词表为 “words”, 输入一个单词，如果正确，则在生词表中能够查找到 该单词，显示“拼写正确”;如果错误，则不能查找到该单词，显示“拼写错误” 可以使用上面介绍的任意一种查找算法。 师生互动 2. 编写程序 若采用顺序查找算法，编写如下程序代码片段。 师生互动 若采用二分查找算法，编写如下程序代码片段。 新知讲授 1. 玩转“汉诺塔”游戏——递归算法 “汉诺塔”是一个古老的益智游戏，如图5-25所示，木板上有3根柱子，分别是原 始柱、借力柱和目标柱，原始柱上有若干个圆盘，规定每次只能移动一个圆盘，且小的 圆盘只能叠在大的圆盘上面。请设计算法，用尽可能少的次数把所有圆盘从原始柱全部移动到目标柱上。 操作提示：递归算法是一种直接或者间接调用自身的算法(如函数的自调用),它体 现了“以此类推”“用同样的步骤重复”的思想，可以使算法的描述简洁，易于理解，其实质是把问题转换为规模缩小了的同类问题。 四.新知讲授 2. 绘制递归图形 Python程序中内置了大量的函数，turtle 模块是其中一个绘制图形的函数库，就像一 只小乌龟，在一个横轴为x 、纵轴为y 的坐标系原点(0,0)位置开始，根据一组函数 指令的控制，在这个平面坐标系中移动，从而在它爬行的路径上绘制了图形。尝试绘制一个自己喜欢的递归图形，效果参考图5-26所示。 课堂小结 布置作业 给定一个包含 n 个整数的数组 arr，请使用冒泡排序算法对其进行排序。假设数组中的整数取值范围在 [-100, 100] 内。 输入： 第一行包含一个整数 n，表示数组 arr 的长度。 第二行包含 n 个整数，表示数组 arr 的元素，整数之间用空格分隔。 输出： 输出一行，包含排序后的数组元素，整数之间用空格分隔。 样例输入： 5 3 6 2 4 1 样例输出： 1 2 3 4 6 提示： 请实现冒泡排序算法，从数组头部开始，逐对相邻元素进行比较，并在必要时进行交换，直至整个数组排序完成。 def bubble_sort(arr): n = len(arr) for i in range(n): for j in range(0, n-i-1): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr n = int(input()) arr = list(map(int, input().split())) arr = bubble_sort(arr) print(" ".join(map(str, arr))) 布置作业 代码模板： 感谢观看 $$