高中数学第一章算法初步1.3.1辗转相除法与更相减损术秦九韶算法

1.3

算法案例1/29第1课时辗转相除法与更相减损术、秦九韶算法2/293/29一、辗转相除法【问题思索】

1.在小课时,我们利用找条约数方法来求两个正整数最大条约数.你能利用这种方法求出36与60最大条约数是多少吗?提醒首先用两个数公有质因数连续去除,一直除到所得商是互质数为止,然后把全部除数连乘起来即为最大条约数.因为4/292.假如两个正整数条约数比较大,而且依据我们观察又不能一下子得到它们条约数,我们又该怎样求出它们最大条约数?比如,怎样求出8251与6105最大条约数?观察等式8251=6105×1+2146,你发觉8251与6105这两个数条约数和6105与2146条约数有什么关系?提醒8251最大约数是2

146约数,一样6

105与2

146条约数也是8

251约数,故8

251与6

105最大条约数也是6

105与2

146最大条约数.5/293.又6105=2146×2+1813,同理,6105与2146条约数和2146与1813条约数相等.重复上述操作,你能得到8251与6105这两个数最大条约数吗?提醒8251=6

105×1+2

146,6

105=2

146×2+1

813,2

146=1

813×1+333,1

813=333×5+148,333=148×2+37,148=37×4+0.最终除数37是148和37最大条约数,也是8

251与6

105最大条约数.6/294.填空:上述这种求两个正整数最大条约数方法就是辗转相除法,又叫欧几里得算法,是一个求两个正整数最大条约数古老而有效算法.其算法步骤以下:第一步,给定两个正整数m,n.第二步,计算m除以n所得余数r.第三步,m=n,n=r.第四步,若r=0,则m,n最大条约数等于m;不然,返回第二步.5.做一做1:求667与928最大条约数.解:928=667×1+261,667=261×2+145,261=145×1+116,145=116×1+29,116=29×4,所以667与928最大条约数是29.

7/29二、更相减损术【问题思索】

1.设两个不都是偶数正整数m,n(m>n),若m-n=k,则m与n最大条约数和n与k最大条约数相等,重复利用这个原理,可求得98与63最大条约数是多少?提醒98-63=35,63-35=28,35-28=7,28-7=21,21-7=14,14-7=7,∴98与63最大条约数为7.8/292.填空:上述求两个正整数最大条约数方法称为更相减损术.其算法步骤以下:第一步,任意给定两个正整数,判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.第二步,以较大数减去较小数,接着把所得差与较小数比较,并以大数减小数.继续这个操作,直到所得差与减数相等为止,则这个数(等数)或这个数与约简数乘积就是所求最大条约数.3.做一做2:342与589最大条约数为

.

解析:589-342=247,342-247=95,247-95=152,152-95=57,95-57=38,57-38=19,38-19=19.所以342与589最大条约数为19.答案:19

9/29三、秦九韶算法【问题思索】

1.已知多项式函数f(x)=x5+x4+x3+x2+x+1,当x=5时f(5)=55+54+53+52+5+1=3906.这种计算求值过程中乘法运算和加法运算次数分别是多少?提醒乘法运算10次,加法运算5次.2.假如我们把上述多项式函数解析式变形为f(x)=((((x+1)x+1)x+1)x+1)x+1,计算当x=5时f(5)值,再统计一下这种计算求值过程中乘法运算和加法运算次数分别是多少.提醒乘法运算4次,加法运算5次.10/293.填空:问题2中算法比问题1中算法少了6次乘法运算,大大简化了运算过程.问题2中算法就叫秦九韶算法.普通地,f(x)=anxn+an-1xn-1+an-2xn-2+…+a1x+a0=(anxn-1+an-1xn-2+an-2xn-3+…+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=…=(…((anx+an-1)x+an-2)x+…+a1)x+a0.求多项式值时,首先计算最内层括号内一次多项式值,即v1=anx+an-1,然后由内向外逐层计算一次多项式值,即v2=v1x+an-2,v3=v2x+an-3,…,vn=vn-1x+a0,这么,求n次多项式f(x)值就转化为求n个一次多项式值.

11/294.做一做3:用秦九韶算法求f(x)=2x3+x-3,当x=3时值v2=

.

解析:f(x)=((2x+0)x+1)x-3,v0=2;v1=2×3+0=6;v2=6×3+1=19.答案:1912/29思索辨析判断以下说法是否正确,正确在后面括号内打“√”,错误打“×”.(1)辗转相除法基本步骤是用较大数除以较小数.(

)(2)用更相减损术求294和84最大条约数时,需做减法次数是3.(

)(3)用秦九韶算法计算f(x)=3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时值,需要进行乘法运算和加法运算次数均为6.(

)(4)利用秦九韶算法求f(x)=1+2x+3x2+4x3+5x4+6x5当x=2时值时,先求6×2+5,第二步求2×(6×2+5)+4.(

)答案:(1)√

(2)×

(3)√

(4)√13/29探究一探究二思维辨析【例1】

求以下两数最大条约数:(1)228与2223;(2)612与468.分析228与2

223相差较大,用辗转相除法求最大条约数;612与468相差较小,用更相减损术求最大条约数.解:(1)用辗转相除法求228与2

223最大条约数.2

223=228×9+171,228=171×1+57,171=57×3.所以228和2

223最大条约数为57.14/29探究一探究二思维辨析(2)首先612和468都是偶数,所以用2约简,得到306和234,还是偶数,需要再用2约简,得到153和117,最终用更相减损术计算.153-117=36,117-36=81,81-36=45,45-36=9,36-9=27,27-9=18,18-9=9.所以612和468最大条约数是9×2×2=36.15/29探究一探究二思维辨析反思感悟1.利用辗转相除法求给定两个数最大条约数,即利用带余除法,用数对中较大数除以较小数,若余数不为零,则将余数和较小数组成新数对,再利用带余除法,直到大数被小数除尽,这时较小数就是原来两个数最大条约数.2.利用更相减损术求两个正整数最大条约数时,首先判断两个正整数是否都是偶数.若是,用2约简.也能够不除以2,直接求最大条约数,这么不影响最终结果.3.当两个整数差较大时,利用辗转相除法计算次数较少.16/29探究一探究二思维辨析变式训练1分别用辗转相除法和更相减损术求779与209最大条约数.解:辗转相除法:779=209×3+152,209=152×1+57,152=57×2+38,57=38×1+19,38=19×2.所以,779与209最大条约数为19.17/29探究一探究二思维辨析更相减损术:779-209=570,570-209=361,361-209=152,209-152=57,152-57=95,95-57=38,57-38=19,38-19=19.所以779和209最大条约数为19.18/29探究一探究二思维辨析【例2】

用秦九韶算法求多项式f(x)=7x7-6x6+4x4+3x3-2x2+x-5当x=3时值.分析解答本题时首先要将原多项式化成f(x)=((((((7x-6)x+0)x+4)x+3)x-2)x+1)x-5形式,然后搞清v0,v1,v2,…,v7分别是多少,最终进行计算.19/29探究一探究二思维辨析解:f(x)=((((((7x-6)x+0)x+4)x+3)x-2)x+1)x-5,v0=7,v1=7×3-6=15;v2=15×3+0=45;v3=45×3+4=139;v4=139×3+3=420;v5=420×3-2=1

258;v6=1

258×3+1=3

775;v7=3

775×3-5=11

320.∴当x=3时,多项式值为11

320.20/29探究一探究二思维辨析反思感悟利用秦九韶算法计算多项式值步骤

21/29探究一探究二思维辨析变式训练2用秦九韶算法求多项式f(x)=2x4-6x3-5x2+4x-6在x=5时值.解:因为f(x)=2x4-6x3-5x2+4x-6=(((2x-6)x-5)x+4)x-6.依据秦九韶算法,我们有v0=2,v1=2x-6=2×5-6=4,v2=4x-5=4×5-5=15,v3=15x+4=15×5+4=79,v4=79x-6=79×5-6=389.22/29探究一探究二思维辨析用秦九韶算法求多项式值时忽略空项而致误【典例】

已知f(x)=x5+x3+x2+x+1,用秦九韶算法求f(3)值.错解因为f(x)=(((x+1)x+1)x+1)x+1,所以当x=3时,v0=1,v1=3+1=4,v2=4×3+1=13,v3=13×3+1=40,v4=40×3+1=120+1=121,所以当x=3时,f(3)=121.以上错解中都有哪些错误?犯错原因是什么?你怎样订正?你怎样防范?错因分析忽略了函数f(x)中x4项系数为0这一点,造成结果错误.23/29探究一探究二思维辨析正解原多项式可化为f(x)=((((x+0)x+1)x+1)x+1)x+1,当x=3时,v0=1,v1=1×3+0=3,v2=3×3+1=10,v3=10×3+1=31,v4=31×3+1=94,v5=94×3+1=283,所以,当x=3时,f(3)=283.防范办法当多项式中间出现空项时,用秦九韶算法求函数值要补上系数为0对应项,即把这些项看成是0·xn.24/29探究一探究二思维辨析变式训练用秦九韶算法求多项式f(x)=x5+0.11x3-0.15x-0.04当x=0.3时值.解:依据秦九韶算法,将f(x)改写为f(x)=((((x+0)x+0.11)x+0)x-0.15)x-0.04.按照从内到外次序,依次计算一次多项式当x=0.3时值.v0=1,v1=v0×0.3+0=0.3,v2=v1×0.3+0.11=0.2,v3=v2×0.3+0=0.06,v4=v3×0.3-0.15=-0.132,v5=v4×0.3-0.04=-0.079

6.即x=0.3时,f(x)=x5+0.11x3-0.15x-0.04值为-0.079

6.25/2912341.用辗转相除法求56与264最大条约数,需要做除法次数是(

)A.3 B.4 C.5 D.6解析:264=56×4+40,56=40×1+16,40=16×2+8,16=8×2.即最大条约数为8,做了4次除法,故选B.答案:B26/2912342.用更相减损术求123和48最大条约数是(

)A.3