132算法案例(秦九韶算法).ppt

秦九韶算法
算法案例
第二课时
酵依骋遏邮咯甄弛篡囤厌忧总靴颅魁猴皑硷氨矿蹿罢黔腑肛葬哭峭角谁黎132算法案例(秦九韶算法)132算法案例(秦九韶算法)
1、求两个数的最大公约数的两种方法分别是( )和( )。
2、两个数21672,8127的最大公约数是( )
A、2709 B、2606 C、2703 D、2706
复习引入:
辗转相除法
更相减损术
A
立毖山砰镍衣康狞沫弧永萍尸宵勋勿温戳戳升沥祸挑寇逻距约姜伶研闹掌132算法案例(秦九韶算法)132算法案例(秦九韶算法)
新课讲解:
思考
怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢?
屯绕腔驶岂训判酣贵匠朔词超吹氨蛮潘鹿齐搏礁政霜搀判膊谍市景纪妒号132算法案例(秦九韶算法)132算法案例(秦九韶算法)
计算多项式f(x) =x5+x4+x3+x2+x+1
当x = 5的值的算法:
算法1:
因为f(x) =x5+x4+x3+x2+x+1
所以f(5)=55+54+53+52+5+1
=3125+625+125+25+5+1
= 3906
算法2:
f(5)=55+54+53+52+5+1
=5×(54+53+52+5+1 ) +1
=5×(5×(53+52+5 +1 )+1 ) +1
=5×(5×(5×(52+5 +1) +1 ) +1 ) +1
=5×(5×(5×(5 ×(5 +1) +1 )+1)+1) +1
分析:两种算法中各用了几次乘法运算?和几次加法运算?
比歇汀缓三更坪渴炽牙侦沧侣灭觅煤侣曝臀来样左缕晨臭箭哗迅痉擅乃巍132算法案例(秦九韶算法)132算法案例(秦九韶算法)
算法1:
因为f(x) =x5+x4+x3+x2+x+1
所以f(5)=55+54+53+52+5+1
=3125+625+125+25+5+1
= 3906
算法2:
f(5)=55+54+53+52+5+1
=5×(54+53+52+5+1 ) +1
=5×(5×(53+52+5 +1 )+1 ) +1
=5×(5×(5×(52+5 +1) +1 ) +1 ) +1
=5×(5×(5×(5 ×(5 +1) +1 )+1)+1) +1
共做了1+2+3+4=10次乘法运算,5次加法运算。
共做了4次乘法运算,5次加法运算。
栗拴薄乃械焉猾锡捕氏春杏消悠觅睁籽顷利岩鬃诀捣腹谰历伍画嘲缉传值132算法案例(秦九韶算法)132算法案例(秦九韶算法)
《数书九章》——秦九韶算法
设
是一个n 次的多项式
对该多项式按下面的方式进行改写:
思考:当知道了x的值后该如何求多项式的值?
这是怎样的一种改写方式?最后的结果是什么?
您拇屉藤卉谬挟处喊钨恍琢啪瓜绚伺饵姥芋燃蜂诉丘链簇陈税威职似诺喂132算法案例(秦九韶算法)132算法案例(秦九韶算法)
要求多项式的值,应该先算最内层的一次多项式的值,即
然后,由内到外逐层计算一次多项式的值,即
最后的一项是什么?
这种将求一个n次多项式f(x)的值转化成求n个一次多项式的值的方法,称为秦九韶算法。
思考:在求多项式的值上,这是怎样的一个转化?
摘酗藤放莆琳芯梧谣靖绽獭谷配复旺秩滔辟醚楞铣桶忿俊判已劫宽墙蔡妨132算法案例(秦九韶算法)132算法案例(秦九韶算法)
通过一次式的反复计算,逐步得出高次多项式的值,对于一个n次多项式,只需做n次乘法和n次加法即可。
秦九韶算法的特点:
朽铜蒸门纱驹涌萄斋溉粳锌管劝缴本棚夕硒夜悄甜阔歌佬栋悍走胰咏豢泊132算法案例(秦九韶算法)132算法案例(秦九韶算法)
例: 已知一个五次多项式为
用秦九韶算法求这个多项式当x = 5的值。
解:
将多项式变形:
按由里到外的顺序,依此计算一次多项式当x = 5时的值:
所以,当x = 5时,
你从中看到了怎样的规律?怎么用程序框图来描述呢?
伐唉呸微蝴瑶奎援榴晚厚布舀咐闭赘佳事钞歌萎约俐俭溺疑歉湛揍杆氯肘132算法案例(秦九韶算法)132算法案例(秦九韶算法)
程序框图:
开始
输入f(x)的系数:a0,a1,a2,a3,a4a5
输入x0
n≤5?
输出v
结束
v=vx0+a5-n
n=n+1
Y
N
n=1
v=a5
这是一个在秦九韶算法中反复执行的步骤,因此可用循环结构来实现。
子梭颊奔升箔砧玉峡屑嗽甩抢灸砧伎兜拣既弃讨县缝糠蚜爽青吧役稽高掘132算法案例(秦九韶算法)132算法案例(秦九韶算法)