张爽《第二章小结》PPT

1、沈阳市第120中学张爽算 法 与 程 序 设 计第 二 章 小 结排序解析算法枚举算法查找回顾本章内容: 就是按问题本身的性质，一一列举该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否是问题的真正解，如果是，就采纳这个解，否则就抛弃它。枚举算法：基本思想：1. 统计100内偶数的各位数字之和恰好为10的个数 解题思路：解析算法： 1.明确问题的前提条件输入 2.明确要求的解输出 3.寻找前提条件与结果之间的数学表达式处理2. 计算一辆车行驶100公里的油耗 排序是为了把杂乱无章的数据变为有效的数据（递增或递减）。冒泡排序法选择排序法排序算法：3. 将十三张纸牌按从小到大进行排序 排

2、序算法：排序算法：冒泡排序和选择排序的对比： 查找是一种查询数据的技术，其目标是能以比较少的步骤和较短的时间找到所需的对象查找算法：查找算法：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分别得到

3、三位数的百位a，十位b，个位ca3+b3+c3=x开 始x=100 x=999a=int(x/100)c=x%10b=(x-100*a-c)/10a3+b3+c3=x输出xx=x+1结 束YY确定算法：枚举算法NYNY 2：出租车计价。假设出租车的计价情况是：起步价3公里10元，3公里以上到10公里，每公里2元，10公里以上每公里3元，并且最后金额保留到元，请设计算法基础训练：确定表达式：f (x) =确定算法：解析算法10 (0 x=3)10+2(x-3) (3x10)基础训练：开 始输入路程xy 10输出结果yx=10y 10+2(x-3)结 束NYYNx=3y 24+3(x-10) 练习

4、一：公元五世纪末，我国古代数学家张丘健在他编写的“算经”里提出一个百鸡问题：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏各几何？确定研究范围：提升训练：列 举：检 验：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-y5x+3y+1/3z=100 x=x+1 y=34NNNYYY 练习二：输入一元二次方程ax2+bx+c=0的系数a、b、c（a不等于0），计算一元二次方程的根。提升训练： 设：d=b2-4ac当d0时

5、：h1= h2=确定算法：解析算法确定表达式：提升训练：开 始输入a、b、cd b*b-4acd0输出”无实根“d=0输出-b/(2*a)输出：结 束NYYN练习三：在校动会上，有五位跳远选手的成绩依次为6.41，5.85，6.21，5.63，6.01。用冒泡排序将五位选手的成绩进行从小到大的排序。提升训练：原始数据6.415.856.215.636.01第一趟5.63 6.415.85 6.21 6.01 第二趟 5.635.85 6.41 6.01 6.21 第三趟5.63 5.86 6.01 6.41 6.21 第四趟5.63 5.86 6.01 6.21 6.41练习四：用二分法求方程x5-3x+1=0在（0,1）上的近似解，精确到c=0.001，写出算法。画出流程图提升训练：提升训练：开 始输入a、b、cx0= （a+b）f(a)=a5-3a+1f(x0)=x05-3x0+1f(x0)=0f(a)f(x0)0a=x0b=x0 c输出x0结 束YYNNYN百钱买百鸡被涂抹的单据枚举算法并联总电阻值银行储蓄解析算法冒泡排序：小数据上推选择排序：数据换位排序算法顺序查找：可以无序对分查找：有序数据查找算法小 结：确定算法一一列举，逐个检验寻找前提条件与结果之间的数学表达式将无序数据变为有序数据查询技术，查找所需数据分析问题编写程序程序调试使用计算机解