13《算法案例2》（新人教A版必修3）.ppt

《13《算法案例2》（新人教A版必修3）.ppt》由会员分享，可在线阅读，更多相关《13《算法案例2》（新人教A版必修3）.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、v主讲老师 潘学国第二课时第二课时 1、辗转相除法和更相减损术，是求两个、辗转相除法和更相减损术，是求两个正整数的最大公约数的优秀算法，我们将算法正整数的最大公约数的优秀算法，我们将算法转化为程序后，就可以由计算机来执行运算，转化为程序后，就可以由计算机来执行运算，实现了古代数学与现代信息技术的完美结合实现了古代数学与现代信息技术的完美结合. 2、对于求、对于求n次多项式的值，在我国古代次多项式的值，在我国古代数学中有一个优秀算法，即秦九韶算法，我们数学中有一个优秀算法，即秦九韶算法，我们将对这个算法作些了解和探究将对这个算法作些了解和探究.问题提出问题提出 思考思考1：怎样求多项式怎样求多项

2、式f(x)=x5+x4+x3+x2+x+1当当x=5时的值？时的值？ 一个自然的做法是把一个自然的做法是把5代入多项式代入多项式f(x)，计，计算各项的值，然后把它们加起来。这时，我们算各项的值，然后把它们加起来。这时，我们一共做了一共做了1+2+3+4=10次乘法，次乘法，5次加法运算。次加法运算。优点是简单，易懂；缺点是不通用，不能解决优点是简单，易懂；缺点是不通用，不能解决任意多项多求值问题，而且计算效率不高。任意多项多求值问题，而且计算效率不高。新知探究新知探究思考思考2: 在上述问题中，若先计算在上述问题中，若先计算x2的值，然后的值，然后依次计算依次计算x2x，(x2x)x，(x2

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

4、法，来解决任意多项式的求值能否探索更好的算法，来解决任意多项式的求值问题问题?f(x)=x5+x4+x3+x2+x+1=(x4+x3+x2+x+1)x+1=(x3+x2+x+1)x+1)x+1=(x2+x+1)x+1)x+1)x+1=(x+1)x+1)x+1)x+1)x+1v0=1v1=v0 x+1=5+1=6v2=v1x+1=65+1=31v3=v2x+1=315+1=156v4=v3x+1=1565+1=781v5=v4x+1=7815+1=3906所以所以,当当x=5时时,多项式的值是多项式的值是3906.这种求多项式值的方法就叫秦九韶算法这种求多项式值的方法就叫秦九韶算法.4次乘法运算

5、，次乘法运算，5次加法运算次加法运算. 思考思考4: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.思考思考4:对于对于 f(x)=(anx+an-1)x+ an-2)x+a1)x+a0，由，由内向外逐层计算一次多项式的值，其算法步骤如内向外逐层计算一次多项

6、式的值，其算法步骤如何？何？ 第一步，计算第一步，计算v1=anx+an-1. 第二步，计算第二步，计算v2=v1x+an-2.第三步，计算第三步，计算v3=v2x+an-3. 第第n步，计算步，计算vn=vn-1x+a0. 例例1：已知一个：已知一个5次多项式为次多项式为 用秦九韶算法求用秦九韶算法求f(5)的值的值.5432( )523. 52. 61. 70. 8fxxxxxx=+-+-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.

7、2；v5=3451.25-0.8=17255.2.所以所以f(5)= 17255.2.变式：变式：已知一个已知一个5次多项式为次多项式为 用秦九韶算法用秦九韶算法求当求当x=5时，时，V1,V3的值及求的值及求f(5)的值做多少次的值做多少次乘法运算乘法运算.53( )53. 51. 70. 8fxxxx=+-解：解：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.2.所以所以v1=25， v3=6

8、42.5 ，f(5)=16070.2思考思考5:上述求多项式上述求多项式 f(x)=anxn+an-1xn-1+a1x+a0的值的方法称为的值的方法称为秦九韶算法秦九韶算法，利用该算法求，利用该算法求f(x0)的值，一共需的值，一共需要多少次乘法运算，多少次加法运算？要多少次乘法运算，多少次加法运算？ 思考思考6:在秦九韶算法中，记在秦九韶算法中，记v0=an，那么第，那么第k步步的算式是什么？的算式是什么？ vk=vk-1x+an-k (k=1，2，n)n次乘法运算，次乘法运算， n次加法运算次加法运算思考思考6:用秦九韶算法求多项式的值，可以用什么用秦九韶算法求多项式的值，可以用什么逻辑结

9、构来构造算法？其算法步骤如何设计？逻辑结构来构造算法？其算法步骤如何设计？第一步，输入多项式的次数第一步，输入多项式的次数n，最高次项的系，最高次项的系数数an和和x的值的值. 第二步，令第二步，令v=an，i=n-1. 第三步，输入第三步，输入i次项的系数次项的系数ai. 第四步，第四步，v=vx+ai，i=i-1.第五步，判断第五步，判断i0是否成立是否成立.若是，则返回第若是，则返回第 二步；否则，输出多项式的值二步；否则，输出多项式的值v. 思考思考7:该算法的程该算法的程序框图如何表示？序框图如何表示？对应的程序如何表对应的程序如何表述？述？开始开始输入输入n , an , x的值的

10、值v=anv=vx+ai输入输入aii0？i=n-1i=i-1结束结束是是输出输出v否否开始开始输入输入n，an，x的值的值v=anv=vx+ai输入输入aii0？i=n- -1i=i- -1结束结束是是输出输出v否否INPUT “n=”；nINPUT “an=”；aINPUT “x=”；x v=ai=n-1WHILE i=0INPUT “ai=”；b v=v*x+bi=i-1 WENDPRINT vPRINT vENDEND例例3 3: :阅读下阅读下列程序，说列程序，说明它解决的明它解决的实际问题是实际问题是什么？什么？INPUT “x=”；an=0y=0WHLE n5 y=y+(n+1)

11、*an n=n+1WENDPRINT yEND求多项式求多项式 在在x=a时的值时的值. 234( )12345f xxxxx=+课时小结课时小结: : 评价一个算法好坏的一个重要评价一个算法好坏的一个重要标志是运算的次数，如果一个算法标志是运算的次数，如果一个算法从理论上需要超出计算机允许范围从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就内的运算次数，那么这样的算法就只能是一个理论算法只能是一个理论算法. .在多项式求在多项式求值的各种算法中，秦九韶算法是一值的各种算法中，秦九韶算法是一个优秀算法个优秀算法. . 1： P45 练习练习22： P48 A组组 23：资料：资料作业布置作业布置