• 200.50 KB
  • 2023-12-12 16:40:02 发布

湖北省恩施巴东县第一高级中学高中数学 §1.3算法案例(秦九韶算法)教案 新人教A版必修3

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的值,然后依次计算x2·x,(x2·x)·x,((x2·x)·x)·x的值,这样每次都可以利用上一次计算的结果,这时,我们一共做了4次乘法运算,5次加法运算.第二种做法与第一种做法相比,乘法的运算次数减少了,因而能够提高运算效率,对于计算机来说,做一次乘法运算所用的时间比做一次加法运算要长得多,所以采用第二种做法,计算机能更快地得到结果.(2)上面问题有没有更有效的算法呢?我国南宋时期的数学家秦九韶(约1202~1261)在他的著作《数书九章》中提出了下面的算法:把一个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)计算机的一5 个很重要的特点就是运算速度快,但即便如此,算法好坏的一个重要标志仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数,那么这样的算法就只能是一个理论的算法.(三)应用示例例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=5×5+2=27;v2=27×5+3.5=138.5;v3=138.5×5-2.6=689.9;v4=689.9×5+1.7=3451.2;v5=3415.2×5-0.8=17255.2;所以,当x=5时,多项式的值等于17255.2.算法分析:观察上述秦九韶算法中的n个一次式,可见vk的计算要用到vk-1的值,若令v0=an,我们可以得到下面的公式:这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现.算法步骤如下:第一步,输入多项式次数n、最高次的系数an和x的值.第二步,将v的值初始化为an,将i的值初始化为n-1.第三步,输入i次项的系数ai.第四步,v=vx+ai,i=i-1.第五步,判断i是否大于或等于0.若是,则返回第三步;否则,输出多项式的值v.程序框图如下图:程序:INPUT“n=”;nINPUT“an=”;a5 INPUT“x=”;xv=ai=n-1WHILEi>=0PRINT“i=”;iINPUT“ai=”;av=v*x+ai=i-1WENDPRINTvEND点评:本题是古老算法与现代计算机语言的完美结合,详尽介绍了思想方法、算法步骤、程序框图和算法语句,是一个典型的算法案例.变式训练请以5次多项式函数为例说明秦九韶算法,并画出程序框图.解:设f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0首先,让我们以5次多项式一步步地进行改写:f(x)=(a5x4+a4x3+a3x2+a2x+a1)x+a0=((a5x3+a4x2+a3x+a2)x+a1)x+a0=(((a5x2+a4x+a3)x+a2)x+a1)x+a0=((((a5x+a4)x+a3)x+a2)x+a1)x+a0.上面的分层计算,只用了小括号,计算时,首先计算最内层的括号,然后由里向外逐层计算,直到最外层的括号,然后加上常数项即可.程序框图如下图:例2已知n次多项式Pn(x)=a0xn+a1xn-1+…+an-1x+an,如果在一种算法中,计算(k=2,3,4,…,n)的值需要k-1次乘法,计算P3(x0)的值共需要9次运算(6次乘法,3次加法),那么计算P10(x0)的值共需要__________次运算.下面给出一种减少运算次数的算法:P0(x)=a0,Pk+1(x)=xPk(x)+ak+1(k=0,1,2,…,n-1).利用该算法,计算P3(x0)的值共需要6次运算,计算P10(x0)的值共需要___________次运算.答案:6520点评:秦九韶算法适用一般的多项式f(x)=anxn+an-1xn-1+…+a1x+a0的求值问题.直接法乘法运算的次数最多可到达,加法最多n次.秦九韶算法通过转化把乘法运算的次数减少到最多n次,加法最多n次.5 例3已知多项式函数f(x)=2x5-5x4-4x3+3x2-6x+7,求当x=5时的函数的值.解析:把多项式变形为:f(x)=2x5-5x4-4x3+3x2-6x+7=((((2x-5)x-4)x+3)x-6)x+7.计算的过程可以列表表示为:最后的系数2677即为所求的值.算法过程:v0=2;v1=2×5-5=5;v2=5×5-4=21;v3=21×5+3=108;v4=108×5-6=534;v5=534×5+7=2677.点评:如果多项式函数中有缺项的话,要以系数为0的项补齐后再计算.(四)知能训练当x=2时,用秦九韶算法求多项式f(x)=3x5+8x4-3x3+5x2+12x-6的值.解法一:根据秦九韶算法,把多项式改写成如下形式:f(x)=((((3x+8)x-3)x+5)x+12)x-6.按照从内到外的顺序,依次计算一次多项式当x=2时的值.v0=3;v1=v0×2+8=3×2+8=14;v2=v1×2-3=14×2-3=25;v3=v2×2+5=25×2+5=55;v4=v3×2+12=55×2+12=122;v5=v4×2-6=122×2-6=238.∴当x=2时,多项式的值为238.解法二:f(x)=((((3x+8)x-3)x+5)x+12)x-6,则f(2)=((((3×2+8)×2-3)×2+5)×2+12)×2-6=238.(五)拓展提升用秦九韶算法求多项式f(x)=7x7+6x6+5x5+4x4+3x3+2x2+x当x=3时的值.解:f(x)=((((((7x+6)+5)x+4)x+3)x+2)x+1)xv0=7;v1=7×3+6=27;v2=27×3+5=86;v3=86×3+4=262;v4=262×3+3=789;v5=789×3+2=2369;v6=2369×3+1=7108;5 v7=7108×3+0=21324.∴f(3)=21324.(六)课堂小结1.秦九韶算法的方法和步骤.2.秦九韶算法的计算机程序框图.(七)作业已知函数f(x)=x3-2x2-5x+8,求f(9)的值.解:f(x)=x3-2x2-5x+8=(x2-2x-5)x+8=((x-2)x-5)x+8∴f(9)=((9-2)×9-5)×9+8=530.5