算法案例2秦九韶算法.ppt

《算法案例2秦九韶算法.ppt》由会员分享，可在线阅读，更多相关《算法案例2秦九韶算法.ppt（14页珍藏版）》请在三一办公上搜索。

1、1.所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数。若余数不为零,则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时较小的数就是原来两个数的最大公约数。,一、复习：案例1:辗转相除法与更相减损术,2.所谓更相减损术，就是对于给定的两个数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，再用较大的数减去较小数，反复执行此步骤直到差数和较小的数相等，此时相等的两数便为原来两个数的最大公约数。简言之,就是辗转相减法.,一、复习：案例1:辗转相除法与更相减损术,12155=52802+1595 5280=15953+495 1595=4953+110

2、495=1104+55 110=552(余数为0时的除数)12155与5280的最大公约数是55,辗转相除法:,1.课本:P50习题1.3A-1(2)求5280与12155的最大公约数,更相减损术:,12155-5280=68756875-5280=15955280-1595=36853685-1595=20902090-1595=4951595-495=11001100-495=605,605-495=110495-110=385385-110=275275-110=165165-110=55110-55=55,探究:求324,243,135三个数的最大公约数,解:324=2431+81,2

3、43=813+0 324,243的最大公约数是81 135-81=54 81-54=27 54-27=27 135,81的最大公约数是27 324,243,135三个数的最大公约数是27,1.3算法案例(2)案例2:秦九韶算法,算法1:(代入法）,因为（）=,所以（5）=55555,=3906,=3125625125255,运算次数：乘法运算+（次）加法运算次，总共次运算,算法2：借用法（）计算,（）依次计算：,每次都可以借用上一次的计算结果乘法运算（次），加法运算次,算法：,乘法运算4（次），加法运算次,（此算法中蕴涵的思想就是著名的秦九韶算法）,1.先计算最内层v1=a5x+a4的值.,2

4、.计算v2=v1x+a3的值.,3.计算v3=v2x+a2的值.,4.计算v4=v3x+a1的值.,5.计算v5=v4x+a0的值.,这种方法叫秦九韶算法P39,秦九韶算法:1.核心思想:将求一个n次多项式的值转化为 求n个一次多项式的值.,2.关键步骤:,例2.已知一个五次多项式为f(x)=5 x5+2x4+3.5x3-2.6x2+1.7x-0.8,用秦九韶算法求这个多项式当x=5 时的值.,解:根据秦九韶算法,将多项式变形：,按由内到外的顺序，依此计算一次多项式当x=5时的值：,所以，当x=5时，多项式的值等于17255.2,你从中看到了怎样的规律？怎么用程序框图来描述呢？,练习:利用秦九韶算法分别计算,P41-理解秦九韶算法,作业本：-；-；-（）监测：.算法案例（）（）（）,