2.4 常见算法的程序实现 课件-2021-2022学年高中信息技术人教 中图版必修1（20张PPT）

(共20张PPT)
2.4 常见算法的程 序实现
主要内容
02
基于枚举算法的问题解决
01
基于解析算法的问题解决
课前回顾
提出问题
分析问题
设计方案
编程调试
解决问题
计算机编程解决问题的一般过程：
1.分析问题
　明确目标、条件等
　抽象建模
　描述问题
2.设计方案
　功能分解（多次分解不唯一）
　详细的步骤设计（算法设计）
3.编程调试
　编写程序（用程序设计语言描述算法）
　调试程序（改正错误，验证结果）
4.解决问题
　检验答案、评估效果，最终
解决问题
绿灯时长的最优设置
行人步行速度4.4km/h，观察到信号灯的反应时间为2s，行人要走过20m的人行横道，则绿灯时长至少设置为多少？
请写出求解绿灯最短时常的计算公式：
2.4.1 基于解析算法的问题解决
解析算法指通过找出解决问题的前提条件与结果之间关系的表达式，并计算表达式来实现问题的求解。
许多问题可以通过分析，抽象成数学模型，借助解析式，用已知条件为变量赋值进行求解。例如行人过街绿灯最短时常公式，t绿=s路/v行+t人，最后只要将已知条件代人公式即可完成该问题求解。
例如:自由落体运动问题。
问题:从离地500 m的高处自由落下一个小球，求从开始落下的时刻起，小球在最后 1s内的位移(重力加速度g=9.8 m/s2)。
例如:自由落体运动问题。
(1)分析问题
已知条件:小球离地高度500m,重力加速度g为9.8 m/s2 ;
求解目标:小球在下落最后1 s内的位移;
已知与未知的关系:可用自由落体运动位移与时间关系的公式h=1/2gt2,求解出下落时 间t,以及最后1 s内小球的位移。
例如:自由落体运动问题。
(2)设计算法
在该问题中，要计算最后1 s内小球的位移，首先要求出小球的落地时间t,由h=1/2gt2,可以得出落地时间t=，=;然后计算前(t-1)s小球下落的高度hx;最后求出总高度h( 500m)与hx的差hh,即为最后1 s内小球的位移。
例如:自由落体运动问题。
开始
H=500，g=9.8
输出最后1s下落的位移hh
t=
hx=g(t-1)(t-1)/2
hh=h-hx
结束
例如:自由落体运动问题。
(3)程序实现
(4)运行调试程序
2.4.2 基于枚举算法的问题解决
枚举法是依据问题的已知条件，确定答案的大致范围，在此范围内列举出它所有可 能情况的方法。在列举过程中，不能遗漏任何一个正确解，通过逐一判断， 验证哪些情况满足问题的条件，从而得到问题的答案。
在枚举算法的编程中，首先，要确定枚举对象和枚举范围，验证问题成立的条件;然后，借助循环语句和条件语句进行相应的程序设计，实现问题解决。
例如:票据中模糊数字推断问题。
问题:一张票据 上有一个由4位数字组成的编号，甲说数字编号的前两位数字相同，但都不是零;乙说数字编号的后两位数字是相同的，但与前两位不同;丙说数字编号是 一个整数的 二次方。试根据以上线索推断出编号。
例如:票据中模糊数字推断问题。
(1)分析问题
已知条件:假设4位数字的编号是AABB,其中A≠0, A≠B,且AABB是一个整数的二次方;
求解目标：票据中的数字；
已知与未知的关系:要求解的4位数字的编号必须同时满足所有的已知条件；
例如:票据中模糊数字推断问题。
(2)设计算法
根据问题分析，只要一一列举 出4位数字A4ABB中A与B的所有可能组合，保证A≠B且A≠0,再验证二次方问题，就可以得到问题的解。因此，该问题可使用枚举算法求解完成，其算法的流程图如下图所示。
例如:票据中模糊数字推断问题。
例如:票据中模糊数字推断问题。
(3)编程实现
例如:票据中模糊数字推断问题。
(4)调试运行
2.4.1 基于解析算法的问题解决
枚举算法需要逐验 证所有可能的情况， 运算量比较大， 解决问题的效率不够高。因此，在应用枚举法求解问题时，需要考虑优化算法，选择恰当的枚举对象，尽量分析出问题中的隐含条件，缩小枚举范围，以提高解决问题的效率。
Add your words here，according to your
need to draw the text box size。
ADD TITLE
Add your words here，according to your
need to draw the text box size。
ADD TITLE
Add your words here，according to your
need to draw the text box size。
ADD TITLE
Add your words here，according to your
need to draw the text box size。
ADD TITLE