算法案例2秦九韶算法

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

2、的两数便为原来两个数的最相等，此时相等的两数便为原来两个数的最大公约数。简言之大公约数。简言之,就是就是辗转相减法.2一、复习：一、复习：案例案例1: 1: 辗转相除法与更相减损术辗转相除法与更相减损术12155=52802+1595 5280=15953+495 1595=4953+110 495=1104+55 110=552 (余数为0时的除数)12155与与5280的最大公约数是的最大公约数是55辗转相除法辗转相除法:1.课本:P50习题1.3A-1(2)求求5280与与12155的最大公约数的最大公约数,3更相减损术更相减损术:12155-5280=68756875-5280=159

3、55280-1595=36853685-1595=20902090-1595=4951595-495=11001100-495=605605-495=110495-110=385385-110=275275-110=165165-110=55110-55=554探究:求324,243,135三个数的最大公约数解:324=2431+81, 243=813+0 324,243的最大公约数是81 135-81=54 81-54=27 54-27=27 135,81的最大公约数是27 324,243,135三个数的最大公约数是2751.3算法案例(2)案例案例2:秦九韶算法秦九韶算法65432( )1

4、f xxxxxx 怎样求多项式当x=5时的值呢?算法算法1:(代入法）代入法）因为因为（） =所以所以（5）=55555= 3906=3125625125255运算次数：乘法运算+（次）加法运算次，总共次运算7算法算法2：借用法：借用法（）计算（）计算5432( )1f xxxxxx 怎样求多项式当x=5时的值呢?（）依次计算：1)(2222222xxxxxxxxxxxxfxxxxxxxxx每次都可以借用上一次的计算结果乘法运算（次），加法运算次8算法：算法：5432( )1f xxxxxx 怎样求多项式当x=5时的值呢?1) 1) 1) 1) 1()(xxxxxxf从内向外依次计算15) 1

5、5) 15) 15) 15()(xf乘法运算4（次），加法运算次（此算法中蕴涵的思想就是著名的秦九韶算法）秦九韶算法）95432543210432543210325432102543210543210( )()()()()fxa xa xa xa xa xaa xa xa xa xaxaa xa xa xaxaxaa xa xaxaxaxaa xaxaxaxaxa1.先计算最内层v1=a5x+a4的值.2.计算v2=v1x+a3的值.3.计算v3=v2x+a2的值.4.计算v4=v3x+a1的值.5.计算v5=v4x+a0的值.这种方法这种方法叫秦九韶叫秦九韶算法算法P3910秦九韶算法秦九韶

6、算法:1.核心思想核心思想:将求一个将求一个n次多项式的值转化为次多项式的值转化为 求求n个一次多项式的值个一次多项式的值 .2.关键步骤:),.,2 , 1(10nkaxvvavknkkn11例例2. 已知一个五次多项式为已知一个五次多项式为f ( x)=5 x5+2x4+3.5x3-2.6x2+1.7x-0.8,用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当x =5 时时的值的值.128 . 07 . 16 . 25 . 325)(2345xxxxxxf解解:根据秦九韶算法根据秦九韶算法,将多项式变形：将多项式变形：8 . 0)7 . 1)6 . 2) 5 . 3)25()(xxxx

7、xxf按由内到外的顺序，依此计算一次多项式当按由内到外的顺序，依此计算一次多项式当x = 5时的值：时的值：272551v50v5 .1385 . 35272v9 .6896 . 255 .1383v2 .34517 . 159 .6894v2 .172558 . 052 .34515v所以，当所以，当x = 5时，多项式的值等于时，多项式的值等于17255.2你从中看到了你从中看到了怎样的规律？怎样的规律？怎么用程序框怎么用程序框图来描述呢？图来描述呢？13练习:利用秦九韶算法分别计算内有无零点。，在区间并判断多项式时的值，与在21)(1212358)(467xfxxxxxxxf12003058)(234567xxxxxxxxf解：1)2)0)0)3)0)58(xxxxxxx1397)2(139712698,6982234834802174,1740287873242,420221