算法案例教学目标:(1)了解秦九韶算法的计算过程,并理解利用秦九韶算法可以减少计算次数,提高计算效率的实质;(2)理解数学算法与计算机算法的区别,理解计算机对数学的辅助作用;(3)体会算法的基本思想;教学重点:秦九韶算法的特点及其程序设计
教学难点:秦九韶算法的先进性理解及其程序设计
教学用具:投影仪教学方法:数形结合的思想方法教学过程:一、复习准备:分别用辗转相除法和更相减损术求出两个正数623和1513的最大公约数
二、讲授新课:例如,设计一个求多项式当时的值的算法
一般的解决方案:将代入多项式进行计算即可;提问:上述算法在计算时共用了多少次乘法运算
多少次加法运算
此方案有何优缺点
(上述算法一共做了4+3+2+1=10次乘法运算,5次加法运算
优点是简单、易懂;缺点是不通用,不能解决任意多项式的求值问题,而且计算效率不高
)另一种做法是先计算的值,然后依次计算的值,这样每次都可以利用上次计算的结果
这时,我们一共做了4次乘法运算,5次加法运算
第二种做法与第一种做法相比,乘法的运算次数减少了,因而能够提高运算效率
对于计算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种做法,计算机能更快地得到结果
那么,有没有更有效的算法呢
1.秦九韶算法例如:求一个n次多项式的值
先把多项式改写为:首先计算最内层括号内一次多项式的值,即,然后由内向外逐层计算一次多项式的值,即,,
这样,求n次多项式f(x)的值就转化为求n个一次多项式的值
结论:这种算法就是“秦九韶算法”
例1、已知一个5次多项式为f(x)=5x5+2x4+3
8用秦九韶算法求这个多项式当x=5时多项式的值
思考:用秦九韶算法求一个n次多项式当x=x0(x0是任意实数)时的值,需要多少次乘法运算,多少次加法运算
分析:秦九韶算法将求次多项式的值转化为求