(
课件网) 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 基于解析算法的问题解决 枚举算法需要逐验 证所有可能的情况， 运算量比较大， 解决问题的效率不够高。因此，在应用枚举法求解问题时，需要考虑优化算法，选择恰当的枚举对象，尽量分析出问题中的隐含条件，缩小枚举范围， ... ...
