必修3-1.3.2算法案例

1、特级教师 王新敞 源头学子 125 九月 2022 王新敞 (必修3)第一 章 算法初步1.3算法案例案例2秦九韶算法特级教师 王新敞 源头学子 2问题提出 1.辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合. 2.对于求n次多项式的值，在我国古代数学中也有一个优秀算法，即秦九韶算法，本节对这个算法作些了解和探究.特级教师 王新敞 源头学子 3怎样求多项式当x=5时的值？计算统计可以得出我们共需要10次乘法运算，5次加法运算 . 再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和

2、5次加法运算即可得出结果。显然少了6次乘法运算。我们把多项式变形为：这种算法就叫秦九韶算法。4+3+2+1=10次乘法运算， 5次加法运算. 特级教师 王新敞 源头学子 4把一个多项式改写为：一般计算步骤如下：秦九韶算法=特级教师 王新敞 源头学子 5对于f(x)=(anx+an-1)x+ an-2)x+a1)x+a0，由内向外逐层计算一次多项式的值，其算法步骤： 第一步，计算v1=anx+an-1. 第二步，计算v2=v1x+an-2.第三步，计算v3=v2x+an-3. 第n步，计算vn=vn-1x+a0.一般计算步骤如下：秦九韶算法这样将求n次多项式f(x)的值转化为求n个一次多项式的值

3、。特级教师 王新敞 源头学子 6秦九韶算法的程序设计及程序框图 用秦九韶算法求多项式的值，其算法步骤设计：第一步，输入多项式的次数n，最高次项的系数an和x的值. 第二步，令v=an，i=n-1. 第三步，输入i次项的系数ai. 第四步，v=vx+ai，i=i-1.第五步，判断i0是否成立.若是，则返回第二步；否则，输出多项式的值v. 开始输入n，an，x的值v=anv=vx+ai输入aii0？i=n-1i=i-1结束是输出v否特级教师 王新敞 源头学子 7秦九韶算法的程序框图对应的程序开始输入n，an，x的值v=anv=vx+ai输入aii0？i=n-1i=i-1结束是输出v否INPUT “

4、n=”；nINPUT “an=”；aINPUT “x=”；x v=ai=n-1WHILE i=0INPUT “ai=”；a v=v*x+ai=i-1 WENDPRINT vENDPRINT “i=”;i秦九韶算法的演示特级教师 王新敞 源头学子 8 练习1 已知一个5次多项式为 用秦九韶算法求f(5)的值.f(x)=(5x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=55+2=27；v2=275+3.5=138.5；v3=138.55-2.6=689.9；v4=689.95+1.7=3451.2；v5=3451.25-0.8=17255.2.所以f(5)= =17255.2.秦九韶算法演示特级教师 王新敞 源头学子 9 练习2 阅读下列程序，说明它解决的实际问题是什么？INPUT “x=”；an=0y=0WHLE n5 y=y+(n+1)*an n=n+1WENDPRINT yEND求多项式 在x=a时的值. 特级教师 王新敞 源头学子 10小结 评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的