高中数学新人教A版必修3 131 辗转相除法与更相减损术、秦九韶算法课件

1、1.3 算法案例算法案例第一课时第一课时 辗转相除法与更相减损术辗转相除法与更相减损术 秦九韶算法秦九韶算法自自 学学 导导 引引1.理解辗转相除法与更相减损术的含义理解辗转相除法与更相减损术的含义,了解执行过程了解执行过程.2.掌握秦九韶算法的计算过程掌握秦九韶算法的计算过程,了解它在数学计算中的应用了解它在数学计算中的应用.3.进一步体会算法的基本思想进一步体会算法的基本思想.课课 前前 热热 身身1.辗转相除法是用于求辗转相除法是用于求_的一种方的一种方法法,这种算法由欧几里得在公元前这种算法由欧几里得在公元前300年左右首先提出年左右首先提出,因而又叫因而又叫_.2.所谓辗转相除法所谓

2、辗转相除法,就是对于给定的两就是对于给定的两个数个数,用用_除以除以_,若若余数不为零余数不为零,则将则将_构成构成新的一对数新的一对数,继续上面的除法继续上面的除法,直到大直到大数被小数除尽数被小数除尽,则这时则这时_就是就是原来两个数的最大公约数原来两个数的最大公约数.两个正整数的最大公约数两个正整数的最大公约数欧几里得算法欧几里得算法较大的数较大的数较小的数较小的数除数与余数除数与余数除数除数3.更相减损术是我国古代数学专著更相减损术是我国古代数学专著_中介绍的一中介绍的一种求两数最大公约数的方法种求两数最大公约数的方法.其基本过程是其基本过程是:对于给定的两对于给定的两数数,用用_,接

3、着把所得的接着把所得的_与与_比较比较,并以大数减小数并以大数减小数,继续这个操作继续这个操作,直到所得的数直到所得的数_为止为止,则这个数就是所求的最大公约数则这个数就是所求的最大公约数.4.秦九韶算法是我国南宋数学家秦九韶算法是我国南宋数学家_在他的代表作在他的代表作_中提出的一种用于计算一元中提出的一种用于计算一元n次多项式的值次多项式的值的方法的方法.九章算术九章算术大数减小数大数减小数差差减数减数相等相等秦九韶秦九韶数书九章数书九章名名 师师 讲讲 解解1.辗转相除法辗转相除法(1)辗转相除的原理辗转相除的原理.设设m,n是两个整数是两个整数(不妨设不妨设mn),用用m除以除以n,若

4、商为若商为q1,余数为余数为r1(0r1n),则则m=nq1+r1,显然若显然若x是是m和和n的公约数的公约数,即即x能整除能整除m和和n,则则x也必然能整除也必然能整除r1,这样这样x也是也是n和和r1的公约数的公约数,故求故求m和和n的公约数就是求的公约数就是求n和和r1的公约数的公约数;同理同理,用用n除以除以r1,得得n=r1q2+r2(0r2nr1r2,所以到某一步必然有所以到某一步必然有ri=ri+1qi+2,即即ri恰能被恰能被ri+1整除整除,这时这时ri+1是是ri和和ri+1的公约数的公约数,它也必然是它也必然是ri-1和和ri,ri-2和和ri-1,r1与与r2,n和和r

5、1,m和和n的最大公约数的最大公约数. (2)辗转相除法的算法分析辗转相除法的算法分析.由以上辗转相除法的原理可由以上辗转相除法的原理可以发现以发现,辗转相除法的基本步辗转相除法的基本步骤是用较大的数除以较小的骤是用较大的数除以较小的数数,考虑到算法中的赋值语句考虑到算法中的赋值语句可以对同一变量多次赋值可以对同一变量多次赋值,我们可以把较大的数用变量我们可以把较大的数用变量m表示表示,把较小的数用变量把较小的数用变量n表示表示,这样式子这样式子m=nq+r(0rn)就是一个反复执行的步骤就是一个反复执行的步骤,因此可以用循环结构实现算法因此可以用循环结构实现算法.如上图如上图.(3)任何两个

6、数任何两个数,用辗转相除法求其最大公约数的程序框图用辗转相除法求其最大公约数的程序框图.由于辗转相除法总是用较大的数去除以较小的数由于辗转相除法总是用较大的数去除以较小的数,所以首先要对一所以首先要对一开始给定的两数的大小进行判断开始给定的两数的大小进行判断,并将大数赋给并将大数赋给m,小数赋给小数赋给n,然然后再执行下面的过程后再执行下面的过程.程序框图如下图所示程序框图如下图所示:(4)辗转相除法求两个数的最大公约数的程序设计辗转相除法求两个数的最大公约数的程序设计.INPUT “a,b”;a,bIF ab THENt=aa=bb=tEND IFr=a MOD bWHILE r0a=bb=

7、rr=a MOD bWENDPRINT bEND2.更相减损术更相减损术(1)更相减损术求两数最大公约数的过程与算法设计更相减损术求两数最大公约数的过程与算法设计:对于给定的两个数对于给定的两个数,用较大的数减去较小的数用较大的数减去较小的数,接着把得到的差与较接着把得到的差与较小的数比较小的数比较,用这时两个数中的较大的数减去较小的数用这时两个数中的较大的数减去较小的数,继续这样继续这样的操作的操作(大数减小数大数减小数),直到所得的数相等为止直到所得的数相等为止,那么这个数那么这个数(等数等数)就是所求的最大公约数就是所求的最大公约数.显然显然,上述过程中大数减去小数是一个重复执行的过程上

8、述过程中大数减去小数是一个重复执行的过程,因此只需将因此只需将大数赋给变量大数赋给变量m,小数赋给变量小数赋给变量n,那么那么m-n就可以通过循环结构就可以通过循环结构实现算法实现算法. (2)更相减损术求最大公约数的程序设计更相减损术求最大公约数的程序设计:INPUT “a,b”;a,bWHILE abIF ab THENa=a-bELSEb=b-aEND IFWENDPRINT aEND3.秦九韶算法秦九韶算法(1)秦九韶算法过程分析秦九韶算法过程分析:设设Pn(x)=anxn+an-1xn-1+a1x+a0,将其改写为将其改写为Pn(x) =(anxn-1+an-1xn-2+a1)x+a

9、0=(anxn-2+an-1xn-3+a2)x+a1)x+a0=(anx+an-1)x+an-2)x+a1)x+a0令令vk=(anx+an-1)x+an-2)x+an-(k-1)x+an-k,01,k1,2,n.nkkn kvavvxa则有其中这样我们便可由这样我们便可由a0依次求出依次求出v1,v2,vn:v1=v0 x+an-1,v2=v1x+an-2,v3=v2x+an-3,vn=vn-1x+a0.显然显然,用秦九韶算法求用秦九韶算法求n次多项式的值时只需做次多项式的值时只需做n次乘法和次乘法和n次加法次加法运算运算. (2)秦九韶算法程序框图秦九韶算法程序框图:以以5次多项式次多项式

10、f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当当x=x0时为例时为例,如下如下图图:典典 例例 剖剖 析析题型一题型一 求两个数的最大公约数求两个数的最大公约数例例1:分别用辗转相除法和更相减损术逐步列出求分别用辗转相除法和更相减损术逐步列出求(1)98和和63;(2)8251和和6105的最大公约数的步骤的最大公约数的步骤,你有什么发现你有什么发现?对优劣对优劣作出评判作出评判.分析分析:辗转相除法是做两个数的带余除法辗转相除法是做两个数的带余除法,更相减损术是做两个数的更相减损术是做两个数的减法减法.解解:(1)98和和63辗转相除法辗转相除法S1 98=63 1+35,

11、S2 63=35 1+28,S3 35=281+7,S4 28=4 7,最大公约数为最大公约数为7.更相减损术更相减损术S1 98-63=35,S2 63-35=28,S3 35-28=7,S4 28-7=21,S5 21-7=14,S6 14-7=7,故故98和和63的最大公约数为的最大公约数为7. (2)8251和和6105辗转相除法辗转相除法S1 8251=61051+2146,S2 6105=21462+1813,S3 2146=18131+333,S4 1813=3335+148,S5 333=1482+37,S6 148=374,最大公约数为最大公约数为37.辗转相除法和更相减损术

12、本质是一致的辗转相除法和更相减损术本质是一致的,除法运算若用加法与减法除法运算若用加法与减法运算定义运算定义,x(x0)除以除以y(y0)就是从就是从x中一次又一次地减去中一次又一次地减去y,直至直至xy为止为止.所减的次数即为商所减的次数即为商,所减的余数就是所求余数所减的余数就是所求余数.更相减损术更相减损术S1 8251-6105=2146,S2 6105-2146=3959,S3 3959-2146=1813,S4 2146-1813=333,S5 1813-333=1480,S6 1480-333=1147,S7 1147-333=814,S8 814-333=481,S9 481-

13、333=148,S10 333-148=185,S11 185-148=37,S12 148-37=111,S13 111-37=74,S14 74-37=37,最大公约数为最大公约数为37.因此因此(1)中中 S4 28=47 可作四次减法可作四次减法,即即28中可减中可减4次次7. (2)中中 S4 1813=3335+148 在在1813中可减中可减5次次333.从形式上看更相减损术比辗转相除法复杂从形式上看更相减损术比辗转相除法复杂,但计算机更但计算机更“喜欢喜欢”做做加减法加减法.加减法比乘除法快几百倍加减法比乘除法快几百倍.变式训练变式训练1:用辗转相除法求用辗转相除法求80和和3

14、6的最大公约数的最大公约数,并用更相减损术并用更相减损术检验所得结果检验所得结果.分析分析:将将80作为大数作为大数,36作为小数作为小数,执行辗转相除法和更相减损术的执行辗转相除法和更相减损术的步骤即可步骤即可.解解:用辗转相除法用辗转相除法: 80=362+8,36=84+4,8=42+0.故故80和和36的最大公约数是的最大公约数是4.用更相减损术检验用更相减损术检验:80-36=44,44-36=8,36-8=28,28-8=20,20-8=12,12-8=4,8-4=4.80和和36的最大公约数是的最大公约数是4.题型二题型二 求三个数的最大公约数求三个数的最大公约数例例2:求三个数

15、求三个数175 100 75的最大公约数的最大公约数.分析分析:求三个数的最大公约数时求三个数的最大公约数时,可以先求出其中两个数的最大公约可以先求出其中两个数的最大公约数数,用这个最大公约数再与第三个数求最大公约数用这个最大公约数再与第三个数求最大公约数,所得结果就是所得结果就是这三个数的最大公约数这三个数的最大公约数.解解:解法解法1(辗转相除法辗转相除法):先求先求175与与100的最大公约数的最大公约数:175=1001+75,100=751+25,75=253.175与与100的最大公约数是的最大公约数是25.以下再求以下再求25与与75的最大公约数的最大公约数:75=25325和和

16、75的最大公约数是的最大公约数是25.故故25是是75和和25的最大公约数的最大公约数,也就是也就是175 100 75的最大公约数的最大公约数.解法解法2(更相减损术更相减损术):第一步第一步:先从较大数中减去较小的数先从较大数中减去较小的数:175-100=75,100-75=25,得得75,25,75;第二步第二步:重复上面的算法重复上面的算法:75-252=25,75-225=25,得得25,25,25.25,25,25的最大公约数为的最大公约数为25.三个数三个数175,100,75的最大公约数为的最大公约数为25.注注:解法解法2的过程可简记为的过程可简记为(175,100,75)

17、=(175-100,100-75,75)=(75,25,75)=(75-225,25,75-252)=(25,25,25)三个数三个数175,100,25的最大公约数为的最大公约数为25.规律技巧规律技巧:本题的解法可以推广到求多个数的最大公约数本题的解法可以推广到求多个数的最大公约数,只需依次只需依次计算即可计算即可.变式训练变式训练2:求三个数求三个数324,243,108的最大公约数的最大公约数.解解:解法解法1:先求先求324与与243的最大公约数的最大公约数,324=2431+81,243=813,324与与243的最大公约数为的最大公约数为81.下面再求下面再求108与与81的最大

18、公约数的最大公约数:108=81+27,81=273.108与与81的最大公约数是的最大公约数是27.故故324,243,108的最大公约数为的最大公约数为27.解法解法2:(324,243,108)=(324-243,243-108,108)=(81,135,108)=(81,135-108,108-81)=(81,27,27)=(81-227,27,27)=(27,27,27).三个数三个数324,243,108的最大公约数为的最大公约数为27.题型三题型三 秦九韶算法的应用秦九韶算法的应用例例3:用秦九韶算法求多项式用秦九韶算法求多项式f(x)=1+x+0.5x2+0.16667x3+0

19、.04167x4+0.00833x5在在x=-0.2的的值值.分析分析:可根据秦九韶算法原理可根据秦九韶算法原理,将所给多项式改写将所给多项式改写,然后由内到外逐次然后由内到外逐次计算即可计算即可.解解:f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5=(0.00833x+0.04167)x+0.16667)x+0.5)x+1)x+1.而而x=-0.2,所以有所以有v0=a5=0.00833,v1=v0 x+a4=0.04,v2=v1x+a3=0.15867,v3=v2x+a2=0.46826,v4=v3x+a1=0.90635,v5=v4x+a0=0.

20、81873.即即f(-0.2)=0.81873.误区警示误区警示:利用秦九韶算法计算多项式值关键是能正确地将所给多利用秦九韶算法计算多项式值关键是能正确地将所给多项式改写项式改写,然后由内向外逐次计算然后由内向外逐次计算,由于后项计算需用到前项的结由于后项计算需用到前项的结果果,故应认真故应认真 细心细心,确保中间结果的准确性确保中间结果的准确性.变式训练变式训练3:已知已知f(x)=x5-4x4+2x2-5x+1,求求f(3)的值的值.解解:f(x)=x5-4x4+05x3+2x2-5x+1=(x4-4x3+05x2+2x-5)x+1=(x3-4x2+05x+2)x-5)x+1=(x2-4x

21、+0)x+2)x-5)x+1=(x-4)x+0)x+2)x-5)x+1.x=3,v0=a5=1;v1=13-4=-1;v2=-13+0=-3;v3=-33+2=-7;v4=-73-5=-26;v5=-263+1=-77.f(3)=-77. 技技 能能 演演 练练基础强化基础强化 1.用辗转相除法求用辗转相除法求294和和84的最大公约数时的最大公约数时,需要做除法的次数是需要做除法的次数是( )A.1 B.2C.3 D.4解析解析:294=843+42,84=422.故需做故需做2次除法次除法.答案答案:B2.两个整数两个整数490和和910的最大公约数是的最大公约数是( )A.2 B.10C

22、.30 D.70解析解析:910=9110,490=4910,91=491+42,49=421+7,42=76.91与与49的最大公约数为的最大公约数为7.故故910与与490的最大公约数为的最大公约数为70.答案答案:D3.用秦九韶算法计算多项式用秦九韶算法计算多项式f(x)=3x6+4x5+5x4+6x3+7x2+8x+1当当x=0.4时的值时时的值时,需要做乘法和加法的次数分别是需要做乘法和加法的次数分别是( )A.6,6 B.5,6C.5,5 D.6,5解析解析:f(x)的最高次项为的最高次项为3x6,共含有共含有7项项,用秦九韶算法求用秦九韶算法求x=0.4时时的值时的值时,需作乘法

23、和加法各需作乘法和加法各6次次.答案答案:A4.用更相减损术求用更相减损术求459和和357的最大公约数的最大公约数,需作减法的次数为需作减法的次数为( )A.4 B.5C.6 D.7解析解析:459-357=102;357-102=255;255-102=153;153-102=51;102-51=51.共作了共作了5次减法次减法.答案答案:B5.378与与90的最大公约数为的最大公约数为_.解析解析:378=904+18;90=185.378与与90的最大公约数是的最大公约数是18.答案答案:186.用秦九韶算法求多项式用秦九韶算法求多项式f(x)=x4-2x3+3x2-7x-5当当x=4

24、时的值时的值,给出给出如下数据如下数据:0 2 11 37 143其运算过程中其运算过程中(包括最终结果包括最终结果)会出现的数有会出现的数有_(只填序号只填序号).答案答案:解析解析:将多项式写成将多项式写成f(x)=(x-2)x+3)x-7)x-5.其中其中v0=a4=1;v1=14-2=2;v2=24+3=11;v3=114-7=37;v4=374-5=143.解析解析:由秦九韶算法知由秦九韶算法知,应填应填an-k.在程序中可以用循环语句来实现在程序中可以用循环语句来实现.答案答案:an-k 循环循环0n0nkk 17.n,va ,vavvx_ k1,2,n ,_.秦九韶的算法中有 个

25、一次式 若令我们可以得到我们可以利用语句来实现8.请将以下用请将以下用“更相减损术更相减损术”求两个正整数求两个正整数a,b的最大公约数的程的最大公约数的程序补充完整序补充完整:INPUT aINPUT bWHILE abIF ab THENa=a-bELSE_END IFWENDPRINT aEND解析解析:阅读程序知阅读程序知,当当ab时时,作减法作减法a-b,当当ab时时,作减法作减法b-a,因此应因此应填填b=b-a.答案答案:b=b-a能力提升能力提升9.用秦九韶算法求多项式用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1当当x=2时的值时的值.分析分析:注意本题中有几项不存在注意本题中有几项不存在,此时在计算时此时在计算时,我们应该将这些项加我们应该将这些项加上上,比如含比如含x3这一项可看做这一项可看做0 x3.解解:根据秦九韶算法根据秦九韶算法,把多项式改写成如下形式把多项式改写成如下形式:f(x)=8x7+5x6+0 x5+3x4+0 x3+0 x2+2x+1=(8x+5)x+0)x+3)x+0)x+0)x+2)x+1.而而x=2,所以有所以有v0=8v1=82+5=21,v2=212+0=42,v3=422+3=87