新课标人教A版必修三1.3 算法案例教案2
5页1、 第2课时 案例2 秦九韶算法导入新课 思路1(情境导入) 大家都喜欢吃苹果吧,我们吃苹果都是从外到里一口一口的吃,而虫子却是先钻到苹果里面从里到外一口一口的吃,由此看来处理同一个问题的方法多种多样.怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢?方法也是多种多样的,今天我们开始学习秦九韶算法. 思路2(直接导入) 前面我们学习了辗转相除法与更相减损术, 今天我们开始学习秦九韶算法.推进新课新知探究提出问题(1)求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值有哪些方法?比较它们的特点.(2)什么是秦九韶算法?(3)怎样评价一个算法的好坏?讨论结果:(1)怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢? 一个自然的做法就是把5代入多项式f(x),计算各项的值,然后把它们加起来,这时,我们一共做了1+2+3+4=10次乘法运算,5次加法运算. 另一种做法是先计算x2的值,然后依次计算x2x,(x2x)x,(x2x)x)x的值,这样每次都可以利用上一次计算的结果,这时,我们一共做了4次乘法运算,5次加法运算. 第二种做法与第一种做法
2、相比,乘法的运算次数减少了,因而能够提高运算效率,对于计算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种做法,计算机能更快地得到结果.(2)上面问题有没有更有效的算法呢?我国南宋时期的数学家秦九韶(约12021261)在他的著作数书九章中提出了下面的算法: 把一个n次多项式f(x)=anxn+an-1xn-1+a1x+a0改写成如下形式:f(x)=anxn+an-1xn-1+a1x+a0=(anxn-1+an-1xn-2+a1)x+ a0=(anxn-2+an-1xn-3+a2)x+a1)x+a0=(anx+an-1)x+an-2)x+a1)x+a0.求多项式的值时,首先计算最内层括号内一次多项式的值,即v1=anx+an-1,然后由内向外逐层计算一次多项式的值,即v2=v1x+an-2,v3=v2x+an-3,vn=vn-1x+a0,这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.上述方法称为秦九韶算法.直到今天,这种算法仍是多项式求值比较先进的算法.(3)计算机的一个很重要的特点就是运算速度快,但即便如此,算法好坏的一个重要标志仍然是运算的次数
3、.如果一个算法从理论上需要超出计算机允许范围内的运算次数,那么这样的算法就只能是一个理论的算法.应用示例例1 已知一个5次多项式为f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8, 用秦九韶算法求这个多项式当x=5时的值.解:根据秦九韶算法,把多项式改写成如下形式:f(x)=((5x+2)x+3.5)x-2.6)x+1.7)x-0.8,按照从内到外的顺序,依次计算一次多项式当x=5时的值:v0=5;v1=55+2=27;v2=275+3.5=138.5;v3=138.55-2.6=689.9;v4=689.95+1.7=3 451.2;v5=3 415.25-0.8=17 255.2;所以,当x=5时,多项式的值等于17 255.2.算法分析:观察上述秦九韶算法中的n个一次式,可见vk的计算要用到vk-1的值,若令v0=an,我们可以得到下面的公式:这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现.算法步骤如下:第一步,输入多项式次数n、最高次的系数an和x的值.第二步,将v的值初始化为an,将i的值初始化为n-1.第三步,输入i次项的系数ai.第四步,v
《新课标人教A版必修三1.3 算法案例教案2》由会员工****分享,可在线阅读,更多相关《新课标人教A版必修三1.3 算法案例教案2》请在金锄头文库上搜索。
2023-10-09 5页
2022-09-02 8页
2023-07-19 9页
2023-05-16 3页
2022-08-16 10页
2023-05-23 10页
2023-03-28 16页
2023-08-04 14页
2023-11-29 12页
2023-02-07 6页