第二章 算法实例 小结课件（21张幻灯片）

课件21张PPT。算 法 与 程 序 设 计
第 二 章 小 结回顾本章内容: 就是按问题本身的性质，一一列举该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，如果是，就采纳这个解，否则就抛弃它。枚举算法：基本思想：1. 统计100内偶数的各位数字之和恰好为10的个数 解题思路： 1.明确问题的前提条件——输入
2.明确要求的解——输出
3.寻找前提条件与结果之间的数学表达式——处理2. 计算一辆车行驶100公里的油耗 排序是为了把杂乱无章的数据变为有效的数据（递增或递减）。冒泡排序法
选择排序法3. 将十三张纸牌按从小到大进行排序 排序算法：排序算法：冒泡排序和选择排序的对比： 查找是一种查询数据的技术，其目标是能以比较少的步骤和较短的时间找到所需的对象查找算法：4. 寻找本年级身高最高的同学查找算法：顺序查找
对分查找范例：数字推算，包装问题2.1枚举算法范例：并联总电阻值，银行储蓄2.2解析算法冒泡排序：小数据上推
选择排序：数据换位2.3排序算法顺序排序：可以无序
对分查找：有序数据2.4查找算法算
法
实
例 1： 若一个三位数x=100a+10b+c（a、b、c都是个位数），满足a3+b3+c3=x，则x称为水仙花数，请设计算法，找出所有的水仙花数。研究范围：列 举：检 验：100<= x <=999分别得到三位数的百位a，十位b，个位ca3+b3+c3=x开 始x=100x<=999a=int(x/100)
c=x%10
b=(x-100*a-c)/10a3+b3+c3=x输出xx=x+1结 束YY确定算法：枚举算法NYNY 2：出租车计价。假设出租车的计价情况是：起步价3公里10元，3公里以上到10公里，每公里2元，10公里以上每公里3元，并且最后金额保留到元，请设计算法确定表达式：f (x) =确定算法：解析算法10 (010)基础训练：开 始输入路程xy ← 10输出结果yx<=10y ← [10+2(x-3)]结 束NYYNx<=3y ← [24+3(x-10)] 练习一：公元五世纪末，我国古代数学家张丘健在他编写的“算经”里提出一个百鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏各几何？确定研究范围：列 举：检 验：x<=20 y<=34公鸡x只，母鸡y只，小鸡z只5x+3y+1/3z=100确定研究方法：枚举算法开 始 x = 1 x<=20 y =1输出结果x、y、zy=y+1结 束N z=100-x-yx=x+1 y<=34NNYY 练习二：输入一元二次方程ax2+bx+c=0的系数a、b、c（a不等于0），计算一元二次方程的根。 设：d=b2-4ac
当d<0时：x1=x2=-b/2a
当d>0时：h1=
h2=确定算法：解析算法确定表达式：提升训练：开 始输入a、b、cd ← b*b-4acd<0输出”无实根“d=0输出-b/(2*a)结 束NYYN练习三：在校动会上，有五位跳远选手的成绩依次为6.41，5.85，6.21，5.63，6.01。用冒泡排序将五位选手的成绩进行从小到大的排序。
提升训练：练习四：用二分法求方程x5-3x+1=0在（0,1）上的近似解，精确到c=0.001，写出算法。画出流程图提升训练：提升训练：开 始输入a、b、cf(a)=a5-3a+1
f(x0)=x05-3x0+1f(x0)=0f(a)f(x0)<0a=x0b=x0输出x0结 束YYNNYN百钱买百鸡
被涂抹的单据并联总电阻值
银行储蓄冒泡排序：小数据上推
选择排序：数据换位排序算法顺序查找：可以无序
对分查找：有序数据确定算法查询技术，查找所需数据分析问题编写程序程序调试使用计算机解决应用问题的一般过程 设计一个算法，在整数边长的直角三角形ABC的直角边a确定，斜边c的最大长度确定的情况下，寻找所有面积超过c2/6的直角三角形的三条边的长度。课后作业：abc谢谢大家！