《2018-2019学年高中数学第一章算法初步1.3.1辗转相除法与更相减损术秦九韶算法课件新人教a版必修》由会员分享，可在线阅读，更多相关《2018-2019学年高中数学第一章算法初步1.3.1辗转相除法与更相减损术秦九韶算法课件新人教a版必修（29页珍藏版）》请在金锄头文库上搜索。
1、1.3 算法案例,第1课时 辗转相除法与更相减损术、秦九韶算法,一、辗转相除法 【问题思考】 1.在小学时,我们利用找公约数的方法来求两个正整数的最大公约数.你能利用这种方法求出36与60的最大公约数是多少吗? 提示首先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来即为最大公约数.由于,2.如果两个正整数的公约数比较大,并且根据我们的观察又不能一下子得到它们的公约数,我们又该如何求出它们的最大公约数?比如,怎样求出8 251与6 105的最大公约数?观察等式8 251=6 1051+2 146,你发现8 251与6 105这两个数的公约数和6 105与2
2、146的公约数有什么关系? 提示8 251的最大约数是2 146的约数,同样6 105与2 146的公约数也是8 251的约数,故8 251与6 105的最大公约数也是6 105与2 146的最大公约数.,3.又6 105=2 1462+1 813,同理,6 105与2 146的公约数和2 146与1 813的公约数相等.重复上述操作,你能得到8 251与6 105这两个数的最大公约数吗? 提示8 251=6 1051+2 146, 6 105=2 1462+1 813, 2 146=1 8131+333, 1 813=3335+148, 333=1482+37, 148=374+0. 最后的
3、除数37是148和37的最大公约数,也是8 251与6 105的最大公约数.,4.填空:上述这种求两个正整数的最大公约数的方法就是辗转相除法,又叫欧几里得算法,是一种求两个正整数的最大公约数的古老而有效的算法.其算法步骤如下: 第一步,给定两个正整数m,n. 第二步,计算m除以n所得的余数r. 第三步,m=n,n=r. 第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步. 5.做一做1:求667与928的最大公约数. 解:928=6671+261,667=2612+145, 261=1451+116,145=1161+29, 116=294, 所以667与928的最大公约数是29.
4、,二、更相减损术 【问题思考】 1.设两个不都是偶数的正整数m,n(mn),若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.,2.填空:上述求两个正整数的最大公约数的方法称为更相减损术.其算法步骤如下: 第一步,任意给定两个正整数,判断它们是否都是偶数.若是,用2约简;若不是,执行第二步. 第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数.继续这个操作,直到所得的差与减数
5、相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数. 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,三、秦九韶算法 【问题思考】 1.已知多项式函数f(x)=x5+x4+x3+x2+x+1,当x=5时f(5)=55+54+53+52+5+1=3 906.这种计算求值的过程中乘法运算和加法运算的次数分别是多少? 提示乘法运算10次,加法运算5次. 2.如果我们把上述多项式
6、函数的解析式变形为f(x)=(x+1)x+1)x+1)x+1)x+1,计算当x=5时f(5)的值,再统计一下这种计算求值的过程中乘法运算和加法运算的次数分别是多少. 提示乘法运算4次,加法运算5次.,3.填空:问题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. 求多项式的值时,
7、首先计算最内层括号内一次多项式的值,即v1=anx+an-1,然后由内向外逐层计算一次多项式的值,即v2=v1x+an-2,v3=v2x+an-3,vn=vn-1x+a0,这样,求n次多项式f(x)的值就转化为求n个一次多项式的值.,4.做一做3:用秦九韶算法求f(x)=2x3+x-3,当x=3时的值v2= . 解析:f(x)=(2x+0)x+1)x-3, v0=2; v1=23+0=6; v2=63+1=19. 答案:19,思考辨析 判断下列说法是否正确,正确的在后面的括号内打“”,错误的打“”. (1)辗转相除法的基本步骤是用较大的数除以较小的数.( ) (2)用更相减损术求294和84的
8、最大公约数时,需做减法的次数是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时的值时,先求62+5,第二步求2(62+5)+4.( ) 答案:(1) (2) (3) (4),探究一,探究二,思维辨析,【例1】 求下列两数的最大公约数: (1)228与2 223; (2)612与468. 分析228与2 223相差较大,用辗转相除法求最大公约数;612与468相差较小,用更相减损术求最大公约数. 解:(1
9、)用辗转相除法求228与2 223的最大公约数. 2 223=2289+171, 228=1711+57, 171=573. 所以228和2 223的最大公约数为57.,探究一,探究二,思维辨析,(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的最大公约数是922=36.,探究一,探究二,思维辨析,反思感悟1.利用辗转相除法求给定的两个数的最大公约数,即
10、利用带余除法,用数对中较大的数除以较小的数,若余数不为零,则将余数和较小的数构成新的数对,再利用带余除法,直到大数被小数除尽,这时的较小数就是原来两个数的最大公约数. 2.利用更相减损术求两个正整数的最大公约数时,首先判断两个正整数是否都是偶数.若是,用2约简.也可以不除以2,直接求最大公约数,这样不影响最后结果. 3.当两个整数的差较大时,利用辗转相除法计算的次数较少.,探究一,探究二,思维辨析,变式训练1分别用辗转相除法和更相减损术求779与209的最大公约数. 解:辗转相除法: 779=2093+152, 209=1521+57, 152=572+38, 57=381+19, 38=19
11、2. 所以,779与209的最大公约数为19.,探究一,探究二,思维辨析,更相减损术: 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.,探究一,探究二,思维辨析,【例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分别是多少,最后进
12、行计算.,探究一,探究二,思维辨析,解:f(x)=(7x-6)x+0)x+4)x+3)x-2)x+1)x-5, v0=7,v1=73-6=15; v2=153+0=45; v3=453+4=139; v4=1393+3=420; v5=4203-2=1 258; v6=1 2583+1=3 775; v7=3 7753-5=11 320. 当x=3时,多项式的值为11 320.,探究一,探究二,思维辨析,反思感悟利用秦九韶算法计算多项式的值的步骤,探究一,探究二,思维辨析,变式训练2用秦九韶算法求多项式f(x)=2x4-6x3-5x2+4x-6在x=5时的值. 解:由于f(x)=2x4-6x3
13、-5x2+4x-6 =(2x-6)x-5)x+4)x-6. 根据秦九韶算法,我们有 v0=2,v1=2x-6=25-6=4, v2=4x-5=45-5=15, v3=15x+4=155+4=79, v4=79x-6=795-6=389.,探究一,探究二,思维辨析,用秦九韶算法求多项式的值时忽略空项而致误 【典例】 已知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=43+1=13, v3=133+1=40, v4=403+1=120+1=121, 所以当x=3时,f(3
14、)=121. 以上错解中都有哪些错误?出错的原因是什么?你如何订正?你如何防范? 错因分析忽视了函数f(x)中x4项的系数为0这一点,导致结果错误.,探究一,探究二,思维辨析,正解原多项式可化为 f(x)=(x+0)x+1)x+1)x+1)x+1, 当x=3时, v0=1,v1=13+0=3,v2=33+1=10, v3=103+1=31,v4=313+1=94, v5=943+1=283, 所以,当x=3时,f(3)=283. 防范措施当多项式中间出现空项时,用秦九韶算法求函数值要补上系数为0的相应项,即把这些项看成是0xn.,探究一,探究二,思维辨析,变式训练用秦九韶算法求多项式f(x)=
15、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=v00.3+0=0.3, v2=v10.3+0.11=0.2, v3=v20.3+0=0.06, v4=v30.3-0.15=-0.132, v5=v40.3-0.04=-0.079 6. 即x=0.3时,f(x)=x5+0.11x3-0.15x-0.04的值为-0.079 6.,1,2,3,4,1.用辗转相除法求56与264的最大公约数,需要做除
16、法的次数是( ) A.3 B.4 C.5 D.6 解析:264=564+40,56=401+16,40=162+8,16=82.即最大公约数为8,做了4次除法,故选B. 答案:B,1,2,3,4,2.用更相减损术求123和48的最大公约数是( ) A.3 B.7 C.9 D.12 解析:123-48=75,75-48=27,48-27=21,27-21=6,21-6=15,15-6=9,9-6=3,6-3=3,所以123和48的最大公约数是3. 答案:A,1,2,3,4,3.用秦九韶算法求多项式f(x)=12+35x-8x2+79x3+6x4+5x5+3x6当x=-4时的值,v4的值为( ) A.-57 B.220 C.-845 D.3 392 解析:由秦九韶算法有v0=3,v1=v0x+5=-7,v2=-7x+6=34,v3=34x+79=-57
