中图版 高中信息技术 必修1 2.4 常见算法的程序实现 课件 （27张PPT）

(共28张PPT)
第2章 算法与程序实现
人教版（2019版） 信息技术（高中）
必修1 数据与计算
2.4 常见算法的程序实现
学习目标
1
2
理解解析算法和枚举算法，根据需要选用这两种算法，
编程实现简单问题求解。
认识问题解决中不同算法的效率，完成项目程序的调试
与运行。
体验探究
绿灯时长的最优设置
通常，行人步行速度约为4.4km/h,观察到信号灯变化后的反应时间约为2s。要保证过街行人能走过长为20m的人行横道，人行过街绿灯时长至少需要设置为多少
思考：
1、写出求解绿灯最短时长的计算公式： 。
2、结合实际道路情况，思考在设置人行过街绿灯时长时需要考虑哪些因素，
试着给出绿灯时长的最优设置模型。
2.4.1 基于解析算法的问题解决
2.4.2 基于枚举算法的问题解决
2.4.3 算法与程序实现的综合应用
目录索引
2.4.1 基于解析算法的问题解决
解析算法指通过找出解决问题的前提条件与结果之间关系的表达式,并计算表达来实现问题的求解.
许多问题可以通过分析,抽象成数学模型,借助解析式,用已知条件为变量赋值进行求解。
例如,在“体验探索“中求解行人过马路最短绿灯时长时,可以应用行程问题相关公式,先计算行人过马路的时间 ,然后建立数学模型,得到行人过街绿灯最短时长公式 最后只要将已知条件代入公式 即可完成该问题求解。
例1:自由落体运动问题
从离地500m的高处自由温下一个小球,求从开始落下的时刻起,小球在最后1s内的位移(重力加速度g以9.8m/s2“计)。
(1)分析问题
已知条件:小球离地高度500m,重力加速度g为9.8m/s2;
求解目标:小球在下湛最后1s内的位移;
已知与未知的关系:可用自由温体运动位移与时间关系的公式h= gt2“,求解出下落时间t,以及最后1s内小球的位移。
(2)设计算法
在该问题中,要计算最后1s内小球的位移,首先要求出小球的落地时间t,
由h= gt2可以得出落地时间t= ;然后计算前(t-1)s小球下落的高度hx；
最后求出总高度h(500m)与hx的差hh,即为最后1s内小球的位移。
(3)编程实现与调试
根据算法设计进行编程实现,程序示例如下:
import math
h=500
g=9.8
t=math.sqrt(2*h/g)
hx=g*（t-1)*(t-1)/2
hh=h-hx
print(“小球最后1s下落的位移是:“,hh,“m“)
体验探究
实践活动
编写程序研究某山地的气温分布
某地区为了开发山区农业,需要了解山地的气候变化。现已知该地山区海拔每升高100m,气温下降约0.5℃,山地最高海拔为1500m,山脚下的年平均气温为22℃(假设山脚海拔力0m)。
思考:
1.依据气温随海拔升高而变化的规律,写出计算该山地不同海拔高度的气温的解析式,并编程实现。
2.某种植物适宜生长在气温为18~20℃的山区,如果要分析这种植物应被种植在该山地多高的地区为宜,需要如何修改算法
枚举法是依据问题的已知条件,确定答秦的大致范图,在此范围内列举出它所有可能情况的方法。在列举过程中,既不能遗漏,也不能重复,通过逐一判断,验证哪些情况满足问题的条件,从而得到问题的答柳。
2.4.2 基于枚举算法的问题解决
例2:票据中模糊数字推断问题
一张票据上有一个由4位数字组成的编号,甲说数字编号的前两位数字相同,但都不是零;乙说数字编号的后两位数字是相同的,但与前两位不同;丙说数字编号是一个整数的二次方。试根据以上线累推断出编号。
(1)分析问题
已知条件:假设4位数字的编号是AABB,其中A≠0,A≠B,旦AABB是一个整数的二次方;求解目标:票据中的数字;
已知与未知的关系:要求解的4位数字的编号必须同时满足所有的已知条件。
(2)设计算法
根据问题分析,只要一一列举出4位数字AABB中A与B的所有可能组合,保证A≠B且A≠0,再验证二次方问题,就可以得到问题的解。因此,该问题可使用枚举算法求解完成。
(3)编程实现与调试
根据算法设计进行编程实现,程序示例如下:
import math
for A inrange(1,10):
for B in range(0,10):
if A !=B:
K=A*1000+A*100+B*10+B
c=int(math.sqrt(k)) #求4位敷字44BB的算术平方根并取其整数部分
if c*c==k: #若k是完全平方数,则找到读票据编号
print(“票据编号是:“,k)
实践活动:寻找1000以内的所有素数
编程求解1000以内的所有素数。素数是在大于1的自然数中,除了1和它本身
以外不再有其他因数的数,如2,3,5,7,11,...
思考:
1.分析该问题的枚举范围和验证条件。
2.用流程图描述问题求解的算法,并编程实现。
2.4.3 算法与程序实现的综合应用
算法设计及其程序实现是用计算机解决问题的核心过程。
在具体的问题解决中,需要综合应用不同的算法思想并编程实现。当程序运行结果不能完全满足问题求解要求时还要对算法和程序进行完善和优化。
例3:查找文稿中高频词的问题
学校开展经典诵读活动,小明在阅读《三国演义》时,为了分析小说的
写作特色,想把小说中出现次数最多的20个词查找出来。想一想小明如何通
过编写程序来实现。
(1)分析问题
已知条件:文本文件《三国演义》；
求解目标:《三国演义》中的高频词(以出现次数最多的20个词为例);
已知与未知的关系:统计《三国演义》文本中词频,找出出现次数最多的20个词。
（2）设计算法
在查找文稿中高频词的问题求解中,除了要完成读取文件和显示输出内容,还要重点实现分词、词频统计和排序等功能。因此,该问题可以分解为以下5个功能。
（1）读取文件:提前准备好《三国演义》文本文件,打开并读取文件内容。
（2）中文分词:在Python语言中利用jieba分词功能,对读取到的《三国演义》
字符串进行分词处理。
（3）词频统计：词频统计的过程主要应用了枚举算法，对于“词汇表”中的每一个
词，依次计算出各自的出现次数，生成一个包含词和次数的“统计表”。
图2.4.7 《三国演义》小说中词语出现次数统计问题求解流程图
（4）词频排序:要找到出现次数最多的20个词,需要对统计出来的词语按次数
从大到小进行排序。在Python语言中直接调用内置的排序函数快速实现序列
排序。
（5）显示输出:降序排序后,序列中的前20个元素可认为是《三国演义》小说
中出现次数最多的20个词。此时,只需要显示输出序列中这前20个元素的值(包括词和对应次数)即可。
（3）编程实现与调试
根据算法设计进行编程实现，程序示例如下：
# 打开“三国演义.txt“文件,读取文件内容
Import jieba #导入jieba分词
if=open(“三国演义.txt“,“r“*,encoding=“utf-8“) #打开文件
txt=f.read( ) #读取文件肉容
# 分词
words=jieba.1cut(txt) #将中文文本拆分为词语保存到列表中
#统计
counts={ } #建立空字典,用于存储词和出现次敷
for word in words:
if len(word)==1: #单字的词语怨略不计
continue
else：
counts[word]=counts.get(word,0)+1 #出现次戴+1
# 排序
items=1ist(counts.items()) #字其转接为列表后才可以排库
items.sort(key=lambda x:x[1],reverse=True) #对列表items接“冲戴“降序排序
#松出前28个元素的值
for i in range(20):
print(items[i][0],items[i][1]) #输出词和出现次敷
断点调试是一种较为直观的程序调试方式,它通过设置断点跟踪变量的取值,观家运行结果,进行程序调试。断点调试的基本方法为:
*进入调试状态;
*设置断点;
*检查运行状态下各个变量的值,确定错误的位置,并进行修改;
*反复调试直至程序运行正确。
实践活动:编程查找小说中的主要人物
修改前面编写的《三国演义》小说高频词查找程序,实现功能:找出小说中出场次数最多的10位人物。
1.在前面已经查找到的20个高频词中,包含有“却说““二人““不能“等
与人名无关的词语。想一想如何去除这些词语,只显示10位出场次数最多的
主要人物的人名 试着修改程序。
2.统计小说中的高频词,不仅可以帮助我们了解其中的主要人物,可以用来
分析人物的主要活动地点及人物间的关系等。试着编程分析自己感兴趣的一
本小说,说一说你的发现。
1、交通信号“绿波带“是根据车辆运行情况对各路口红绿灯进行协调,使车辆
通过路口时能连续获得一路绿灯。某路段启用了“绿波带“技术,如图所示,
全长1.6km,5个灯控路口,提示的“绿波速度“为60km/h,假设5个灯控路口间距相等。在仅考虚一辆车通行的情况下,如果实现“绿波“交通,那么相邻两个路口间绿灯亮起的最大时间间隔应该设置为多少 思考该问题求解的算法并编程实现。
练习提升
2.韩信是汉初著名军事家,传说他统计士兵数目有个独特的方法。例如,先令士兵
排成5列纵队,结果余1人;接着,命令士兵排成列纵队,结果余5人;再命令士兵
排成7列纵队,结果余4人;最后,命令士兵排成11列纵队,结果余10人。这样他
便知道士兵的总人数了。这种计数的方法被后人称为“韩信点兵“。试编写程序计算士兵的数目。
3.编写程序,统计一段文本中分别有多少个汉字、英文字母、数字和其他字符。
谢谢
21世纪教育网（www.21cnjy.com) 中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php