秦九韶算法PPT课件

1、1通过阅读中国古代中的秦九韶算法案例，体会中国数学对世界数学发展的贡献；通过阅读中国古代中的秦九韶算法案例，体会中国数学对世界数学发展的贡献；2知道秦九韶算法，能用秦九韶算法求知道秦九韶算法，能用秦九韶算法求n次多项式的值次多项式的值.第1页/共19页自学教材自学教材P37-P39 解决下列问题解决下列问题一、能用秦九韶算法求一、能用秦九韶算法求n次多项式的值次多项式的值.二、二、学海导航学海导航 P28-P29 “双层练习双层练习” “范例剖析范例剖析”三、教材三、教材 P45 第第2题题第2页/共19页知识探究知识探究( (一一):):秦九韶算法的基本思想秦九韶算法的基本思想 【问题问题1

2、】设计求多项式设计求多项式f(x)=2x5-5x4-4x3+3x2-6x+7当当x=5时的值的算法时的值的算法,并写出程序并写出程序.x=5f=2x5-5x4-4x3+3x2-6x+7PRINT fEND程序：程序：点评点评:上述算法一共做了上述算法一共做了15次乘法运算次乘法运算,5次加法运次加法运算算.优点是简单优点是简单,易懂易懂;缺点是不通用缺点是不通用,不能解决任意不能解决任意多项多求值问题多项多求值问题,而且计算效率不高而且计算效率不高.第3页/共19页思考思考2:在上述问题中，若先计算在上述问题中，若先计算x2的值，然后依次的值，然后依次计算计算x2x，(x2x)x，(x2x)x

3、)x的值，这样每次都的值，这样每次都可以利用上一次计算的结果，再将这些数与可以利用上一次计算的结果，再将这些数与x和和7相相加，那么一共做了多少次乘法运算和多少次加法运加，那么一共做了多少次乘法运算和多少次加法运算？算？ 9次乘法运算，次乘法运算，5次加法运算次加法运算. 第二种做法与第一种做法相比第二种做法与第一种做法相比,乘法的运算次数减少了乘法的运算次数减少了,因而能提高运算效率因而能提高运算效率.而且对而且对于计算机来说于计算机来说,做一次乘法所需的运算时间比做一次加法要长得多做一次乘法所需的运算时间比做一次加法要长得多,因此第二种做法能更快因此第二种做法能更快地得到结果地得到结果.第

4、4页/共19页思考思考3:能否探索更好的算法能否探索更好的算法, ,来解决任意多项式的求值问题来解决任意多项式的求值问题? ?f(x)=2x5-5x4-4x3+3x2-6x+7=(2x4-5x3-4x2+3x-6)x+7=(2x3-5x2-4x+3)x-6)x+7=(2x2-5x-4)x+3)x-6)x+7=(2x-5)x-4)x+3)x-6)x+7v0=2v1=v0 x-5=25-5=5v2=v1x-4=55-4=21v3=v2x+3=215+3=108v4=v3x-6=1085-6=534v5=v4x+7=5345+7=2677所以所以,当当x=5时时,多项式的值是多项式的值是2677.这

5、种求多项式值的方法就叫这种求多项式值的方法就叫秦九韶算法秦九韶算法.5次乘法运算，5次加法运算. 第5页/共19页思考思考4:利用后一种算法求多项式利用后一种算法求多项式f(x)=anxn+an-1xn-1+a1x+a0的值，这个多项式应写成哪种形式？的值，这个多项式应写成哪种形式？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.第6页/共19页思考思考5:对于对于f(x)=(anx+an-1)x+an-2)x+a1

6、)x+a0,由内向外逐层计算一次多项式的值，其算法步骤如何由内向外逐层计算一次多项式的值，其算法步骤如何?第一步，计算第一步，计算v1=anx+an-1. 第二步，计算第二步，计算v2=v1x+an-2.第三步，计算第三步，计算v3=v2x+an-3. 第第n步，计算步，计算vn=vn-1x+a0.第7页/共19页思考思考6:上述求多项式上述求多项式f(x)=anxn+an-1xn-1+a1x+a0的的值的方法称为值的方法称为秦九韶算法秦九韶算法，利用该算法求，利用该算法求f(x0)的值，的值，一共需要多少次乘法运算，多少次加法运算？一共需要多少次乘法运算，多少次加法运算？ 思考思考7:在秦九

7、韶算法中，记在秦九韶算法中，记v0=an，那么第，那么第k步的算步的算式是什么？式是什么？ vk=vk-1x+an-k (k=1，2，n)n次乘法运算，次乘法运算， n次加法运算次加法运算第8页/共19页知识探究知识探究( (二二):):秦九韶算法的程序设计秦九韶算法的程序设计 思考思考1:用秦九韶算法求多项式的值，可以用什么逻用秦九韶算法求多项式的值，可以用什么逻辑结构来构造算法？其算法步骤如何设计？辑结构来构造算法？其算法步骤如何设计？第一步第一步: :输入多项式的次数n，最高次项的系数an和x的值. 第二步第二步: :令v=an，i=n-1. 第三步第三步: :输入i次项的系数ai. 第

8、四步第四步: :v=vx+ai，i=i-1.第五步第五步: :判断i0是否成立.若是，则返回第二步；否则，输出多项式的值v. 第9页/共19页思考思考2:该算法的程序框图如何表示？该算法的程序框图如何表示？开始开始输入输入n，an，x的值的值v=anv=vx+ai输入输入aii0？i=n-1i=i-1结束结束是是输出输出v否否第10页/共19页思考思考3:该程序框图对应的程序如何表述？该程序框图对应的程序如何表述？开始输入n，an，x的值v=anv=vx+ai输入aii0？i=n- -1i=i- -1结束是输出v否INPUT “n=”；nINPUT “an=”；aINPUT “x=”；xv=a

9、i=n-1WHILE i=0INPUT “ai=”；bv=v*x+bi=i-1 WENDPRINT yEND第11页/共19页【例例1】已知一个已知一个5次多项式为次多项式为用秦九韶算法求用秦九韶算法求f(5)的值的值.5432( )523. 52. 61. 70. 8f xxxxxx=+-+-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.第12页/共19页

10、例2 已知一个5次多项式为用秦九韶算法求当x=5时，V1,V3的值及求f(5)的值做多少次乘法运算.53( )53. 51. 70. 8f xxxx=+-解：解：f(x)=(5x+0)x+3.5)x+0)x+1.7)x-0.8.v1=55+0=25；v2=255+3.5=128.5；v3=128.55+0=642.5；v4=642.55+1.7=3214.2；v5=3214.25-0.8=16070.8.所以v1=25， v3=642.5 ，f(5)=16070.8.第13页/共19页【例例3】阅读下列程阅读下列程序，说明它解决的序，说明它解决的实际问题是什么？实际问题是什么？INPUT “x

11、=”；an=0y=0WHLE n5 y=y+(n+1)*an n=n+1WENDPRINT yEND求多项式求多项式 在在x=a时的值时的值. 2 23 34 4( ( ) )1 12 23 34 45 5f f x xx xx xx xx x= =+ + + + +第14页/共19页三、教材三、教材 P45 第第2题题第15页/共19页对自己说，你有什么收获？对自己说，你有什么收获？对同学说，你有什么提示？对同学说，你有什么提示？对老师说，你有什么疑惑？对老师说，你有什么疑惑？第16页/共19页 评价一个算法好坏的一个重要标志是运算的次评价一个算法好坏的一个重要标志是运算的次数，如果一个算法从理论上需要超出计算机允许范数，如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理围内的运算次数，那么这样的算法就只能是一个理论算法论算法.在多项式求值的各种