高一数学(1.3-2秦九邵算法)

《高一数学(1.3-2秦九邵算法)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.3算法案例第二课时设计求多项式f(x)=2x5－5x4－4x3+3x2－6x+7当x=5时的值的算法，并写出程序。一般的解决方案INPUT“x=”;xx=5;f=2*x^5–5*x^4–4*x^3+3*x^2–6*x+7;PRINTf上述算法一共做了解15次乘法运算，5次加法运算.优点是简单，易懂;缺点是不通用，不能解决任意多项式的求值问题，而且计算效率不高。有没有更高效的算法？用提取公因式的方法多项式变形为f(x)=2x5－5x4－4x3+3x2－6x+7=x4(2x－5)－4x3+3x2－6x+7=x3((2x－5)－4)+3x2－6x+7…………=

2、((((2x－5)x－4)x+3)x－6)x+7这样共作了5次加法，5次乘法.从内到外，如果把每一个括号都看成一个常数，那么变形后的式子中有哪些“一次式”？x的系数依次是什么？问题提出1.辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合.2.对于求n次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究.秦九韶算法思考3:利用后一种算法求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值，这个多项式应写成哪种

3、形式？f(x)=anxn+an-1xn-1+…+a1x+a0=(anxn-1+an-1xn-2+…+a2x+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=…=(…((anx+an-1)x+an-2)x+…+a1)x+a0.《数书九章》——秦九韶算法设是一个n次的多项式对该多项式按下面的方式进行改写：思考：当知道了x的值后该如何求多项式的值？这是怎样的一种改写方式？最后的结果是什么？要求多项式的值，应该先算最内层的一次多项式的值，即然后，由内到外逐层计算一次多项式的值，即最后的一项是什么？这种将求一个n次多项式f（x）的值转

4、化成求n个一次多项式的值的方法，称为秦九韶算法。思考：在求多项式的值上，这是怎样的一个转化？这种计算方法，称之为秦九韶方法。直到今天，这种算法仍是世界上多项式求值的最先进的算法。这种方法的计算量仅为：乘法n次，加法n次.直接求和法：直接计算P(x)=anxn+an－1xn－1+…+a1x+a0的值需要进行n次加法，而乘法需要1+2+3+……+n=n(n+1)/2次。理论迁移例1已知一个5次多项式为用秦九韶算法求f(5)的值.f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=5×5+2=27；v2=27×5+3.5=138.5；

5、v3=138.5×5-2.6=689.9；v4=689.9×5+1.7=3451.2；v5=3451.2×5-0.8=17255.2.所以f(5)==17255.2.你从中看到了怎样的规律？怎么用程序框图来描述呢？开始输入f(x)的系数：a5、a4、a3、a2、a1、a0输入xn=0v=a5v=v·x+a5-nn=n+1n<5?输出v结束否是注意：要想使用检验功能，请使用前，先要减低宏的安全限制思考4:对于f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0，由内向外逐层计算一次多项式的值，其算法步骤如何？第一步，计算v1=anx+an-

6、1.第二步，计算v2=v1x+an-2.第三步，计算v3=v2x+an-3.…第n步，计算vn=vn-1x+a0.思考5:上述求多项式f(x)=anxn+an-1xn-1+…+a1x+a0的值的方法称为秦九韶算法，利用该算法求f(x0)的值，一共需要多少次乘法运算，多少次加法运算？思考6:在秦九韶算法中，记v0=an，那么第k步的算式是什么？vk=vk-1x+an-k(k=1，2，…，n)知识探究(二):秦九韶算法的程序设计思考1:用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？第一步，输入多项式的次数n，最高次项的系数an和x的

7、值.第二步，令v=an，i=n-1.第三步，输入i次项的系数ai.第四步，v=vx+ai，i=i-1.第五步，判断i≥0是否成立.若是，则返回第二步；否则，输出多项式的值v.思考2:该算法的程序框图如何表示？开始输入n，an，x的值v=anv=vx+ai输入aii≥0？i=n-1i=i-1结束是输出v否思考3:该程序框图对应的程序如何表述？开始输入n，an，x的值v=anv=vx+ai输入aii≥0？i=n-1i=i-1结束是输出v否INPUT“n=”；nINPUT“an=”；aINPUT“x=”；xv=ai=n-1WHILEi>=0INPUT“ai=”；b

8、v=v*x+bi=i-1WENDPRINTvEND例