2.1.1算法案例分析【荐】.pptVIP

在小品“钟点工”中,赵本山与宋丹丹之间有段对话: 要把大象装冰箱，总共分几步？ 提问： 答：分三步： 第一步：打开冰箱门 第二步：把大象装冰箱 第三步：关上冰箱门 例1 现在一商品,价格在0~1000元之间,采取怎样的策略,才能在较短的时间内说出正确的答案呢？ 分析：可采用二分法求方程的近似解的思想方法。 答: (具体分析见教材) 第一步：确定初始区间(a,b)( 若aC, bC,则进行下一步); 第二步：取[a,b]的中点0.5*(a+b); 第三步：比较中点0.5*(a+b)与C的大小: 若0.5*(a+b)C,则确定新的区间(0.5*(a+b),b);若0.5*(a+b)C,则确定新的区间(a,0.5*(a+b));若0.5*(a+b)=C,则0.5*(a+b)就是所求结果; 第四步：新区间重复第二步和第三步,直到求得结果. 广义地说：为了解决某一问题而采取的方法和步骤，就称之为算法。 问题1：设计算法，将 936 分解成素因数的乘积。 解： 提问：936 的“素因数”有什么特征 ？ 分析：怎样将 936 分解成素因数的乘积？ 1.判断 936 是否为素数： 936 不是素数，开始分解素因数。 2.确定 936 的最小素因数： 936 最小素因数为 2 即 936=2×468. 3.判断 468 是否为素数： 468 不是素数，继续分解素因数。 4.确定 468 的最小素因数： 468 的最小素因数为 2 即 936=2×2×234. · · · · · · 11.判断 13 是否为素数： 13 是素数，结束分解素因数。 分解素因数的结果是： 短除法： 936 =2×2×2×3×3×13. 用来解决某一类数学问题的“一系列计算步骤”就是一种“算法”。 感悟算法: 算法的步骤必须是“有限”的。 问题2：设计算法，求 840 与 1764 的最大公因数。 分析： 最大公因数 公因数 分解素因数 分解因数 第二步. 将 1764 分解成素因数的积： 第一步. 将 840 分解成素因数的积： 第三步. 确定它们的公共素因数： 第四步. 确定公共素因数的指数幂： 第五步. 写出最大公因数： 套用的“算法”称为“程序包”, 我们直接套用问题1 的算法。 我们在解决问题2的过程中, 遇到了分解素因数的问题, 这样做有什么“好处”？ 我们把用“程序包” 解决问题的思想称为“平台思想”。 问题3 现有九枚银元，有一枚略轻的是假银元，你能用天平(不用砝码) 将其找出来吗？设计一种方法，解决这一问题. 方法一:（将银元分成四组，余一枚） 第一步:任取一组银元进行比较,如果天平不平衡,则较轻的一边是假银元;如果天平平衡,则进行第二步. 第二步:取下这两枚银元,再依次放两枚银元进行称量,直到天平不平衡为止,偏轻的那一枚是假银元.若天平一直平衡,则未称的那一枚是假银元. 方法二:(将银元分成两组,每组4枚，余一枚) 第一步:将两组分别放在天平的两边。如果天平不平衡,则假银元在较轻的那一组;如果天平平衡，则未称的那一枚是假银元。 第二步：取出含假银元的那一组，从中各任取两枚银元放在天平的两边。则较轻的那一组中有假银元. 第三步：取出含假银元的那两枚进行比较，则较轻的那一枚就是假银元。 方法三:(将银元分成三组,每组3枚) 第一步:将两组分别放在天平的两边。如果天平不平衡,则假银元在较轻的那一组;如果天平平衡，则假银元在未称的那一组里。 第二步：取出含假银元的那一组，从中任取两枚银元放在天平的两边。如果天平不平衡，则较轻的那一边就是假银元；如果天平平衡，则未称的那一枚是假银元。 对于一元二次方程,可以用熟悉的求根公式来求解.但是,绝大部分方程不存在求根公式. 在实际问题中,通常只要能获得满足一定精确度的近似解就可以了,因此,讨论方程近似解的算法具有重要的现实意义. 请同学们设计出二分法求方程f(x)=0的近似解的算法步骤: y x O a b x* 第五步：判断新的有解区间是否小于精确度。 （1）如果新的有解区间长度大于等于精确度，则在新的有解区间的基础上重复上述步骤。 （2）如果新的有解区间长度小于精确度，则取中点为方程的近似解。 第一步：确定有解区间[a,b] ( ); 第二步：取[a,b]的中点 ; 第三步：计算 ; 第四步：判断 的符号。 1.若 ,则确定新的有解区间(a,(a+b)/2); 2.若