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

《算法案例2秦九韶算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、2155=5280×2+15955280=1595×3+4951595=495×3+110495=110×4+55110=55×2(余数为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=605605-495=11049

3、5-110=385385-110=275275-110=165165-110=55110-55=55探究:求324,243,135三个数的最大公约数解:∵324=243×1+81,243=81×3+0∴324,243的最大公约数是81∵135-81=5481-54=2754-27=27∴135,81的最大公约数是27∴324,243,135三个数的最大公约数是271.3算法案例(2)案例2:秦九韶算法算法1:(代入法）因为ｆ（ｘ）=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ（5）=5５＋5４＋5３＋5２＋

4、5＋１=3906=3125＋625＋125＋25＋5＋１运算次数：乘法运算４+３+２+１＝１０（次）加法运算５次，总共１５次运算．算法2：借用法（１）计算ｘ２（２）依次计算：每次都可以借用上一次的计算结果乘法运算４（次），加法运算５次算法３：乘法运算4（次），加法运算５次（此算法中蕴涵的思想就是著名的秦九韶算法）1.先计算最内层v1=a5x+a4的值.2.计算v2=v1x+a3的值.3.计算v3=v2x+a2的值.4.计算v4=v3x+a1的值.5.计算v5=v4x+a0的值.这种方法叫秦九韶算法P

5、39秦九韶算法:1.核心思想:将求一个n次多项式的值转化为求n个一次多项式的值.2.关键步骤:例2.已知一个五次多项式为f(x)=5x5+2x4+3.5x3-2.6x2+1.7x-0.8,用秦九韶算法求这个多项式当x=5时的值.解:根据秦九韶算法,将多项式变形：按由内到外的顺序，依此计算一次多项式当x=5时的值：所以，当x=5时，多项式的值等于17255.2你从中看到了怎样的规律？怎么用程序框图来描述呢？练习:利用秦九韶算法分别计算P41-４２理解秦九韶算法作业本：Ｐ４７-２；Ｐ５０Ａ-２；Ｐ５２Ａ

6、-１（１）监测：１.３算法案例（１）（２）（４）