2012高一数学 1.3.1 辗转相除法与更相减损术、秦九韶算法课件 新人教A版必修2

1、1.3 算法案例 第一课时 辗转相除法与更相减损术秦九韶算法,自 学 导 引 1.理解辗转相除法与更相减损术的含义,了解执行过程. 2.掌握秦九韶算法的计算过程,了解它在数学计算中的应用. 3.进一步体会算法的基本思想.,课 前 热 身 1.辗转相除法是用于求_的一种方法,这种算法由欧几里得在公元前300年左右首先提出,因而又叫_. 2.所谓辗转相除法,就是对于给定的两个数,用_除以_,若余数不为零,则将_构成新的一对数,继续上面的除法,直到大数被小数除尽,则这时_就是原来两个数的最大公约数.,两个正整数的最大公约数,欧几里得算法,较大的数,较小的数,除数与余数,除数,3.更相减损术是我国古代

2、数学专著_中介绍的一种求两数最大公约数的方法.其基本过程是:对于给定的两数,用_,接着把所得的_与_比较,并以大数减小数,继续这个操作,直到所得的数_为止,则这个数就是所求的最大公约数. 4.秦九韶算法是我国南宋数学家_在他的代表作_中提出的一种用于计算一元n次多项式的值的方法.,九章算术,大数减小数,差,减数,相等,秦九韶,数书九章,名 师 讲 解 1.辗转相除法,(1)辗转相除的原理. 设m,n是两个整数(不妨设mn),用m除以n,若商为q1,余数为r1(0r1nr1r2,所以到某一步必然有ri=ri+1qi+2,即ri恰能被ri+1整除,这时ri+1是ri和ri+1的公约数,它也必然是r

3、i-1和ri,ri-2和ri-1,r1与r2,n和r1,m和n的最大公约数.,(2)辗转相除法的算法分析. 由以上辗转相除法的原理可 以发现,辗转相除法的基本步 骤是用较大的数除以较小的 数,考虑到算法中的赋值语句 可以对同一变量多次赋值,我们可以把较大的数用变量m表示,把较小的数用变量n表示,这样式子m=nq+r(0rn)就是一个反复执行的步骤,因此可以用循环结构实现算法.如上图.,(3)任何两个数,用辗转相除法求其最大公约数的程序框图. 由于辗转相除法总是用较大的数去除以较小的数,所以首先要对一开始给定的两数的大小进行判断,并将大数赋给m,小数赋给n,然后再执行下面的过程.程序框图如下图所

4、示:,(4)辗转相除法求两个数的最大公约数的程序设计.,2.更相减损术 (1)更相减损术求两数最大公约数的过程与算法设计: 对于给定的两个数,用较大的数减去较小的数,接着把得到的差与较小的数比较,用这时两个数中的较大的数减去较小的数,继续这样的操作(大数减小数),直到所得的数相等为止,那么这个数(等数)就是所求的最大公约数. 显然,上述过程中大数减去小数是一个重复执行的过程,因此只需将大数赋给变量m,小数赋给变量n,那么m-n就可以通过循环结构实现算法.,(2)更相减损术求最大公约数的程序设计:,3.秦九韶算法 (1)秦九韶算法过程分析: 设Pn(x)=anxn+an-1xn-1+a1x+a0

5、,将其改写为 Pn(x) =(anxn-1+an-1xn-2+a1)x+a0 =(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,这样我们便可由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次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当x=x0

6、时为例,如下图:,典 例 剖 析 题型一 求两个数的最大公约数,例1:分别用辗转相除法和更相减损术逐步列出求(1)98和63;(2)8251和6105的最大公约数的步骤,你有什么发现?对优劣作出评判. 分析:辗转相除法是做两个数的带余除法,更相减损术是做两个数的减法.,解:(1)98和63 辗转相除法 S1 98=63 1+35, 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、的最大公约数为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.,辗转相除法和更相减损术本质是一致的,除法运算若用加法与减法运算定义,x(x0)除以y(y0)就是从x中一次又一次地减去y,直至xy为止.所减的次数即为商,所减的余数就是所求余数.,更相减损术 S1 8251-6105=2146, S2 6105-2146=3959, S3 3959-2146=1813, S4

8、2146-1813=333, S5 1813-333=1480, S6 1480-333=1147, S7 1147-333=814,S8 814-333=481, S9 481-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. 从形式上看更相减损术比辗转相除法复杂,但计算机更“喜欢”做加减法.加减法比乘除法快几

9、百倍. 变式训练1:用辗转相除法求80和36的最大公约数,并用更相减损术检验所得结果. 分析:将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:求三个数17510075的最大公约数. 分析:求三个数的最大公约数时,可以先求出其中两个数的最大公约数,用这个最大公约数再与第

10、三个数求最大公约数,所得结果就是这三个数的最大公约数.,解:解法1(辗转相除法):先求175与100的最大公约数: 175=1001+75, 100=751+25, 75=253. 175与100的最大公约数是25. 以下再求25与75的最大公约数: 75=253 25和75的最大公约数是25. 故25是75和25的最大公约数,也就是17510075的最大公约数.,解法2(更相减损术): 第一步:先从较大数中减去较小的数: 175-100=75,100-75=25,得75,25,75; 第二步:重复上面的算法:75-252=25,75-225=25,得25,25,25. 25,25,25的最大

11、公约数为25. 三个数175,100,75的最大公约数为25.,注:解法2的过程可简记为 (175,100,75) =(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的最大公约数: 108=81+

12、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.04167x4+0.00833x5在x=-0.2的值. 分析:可根据秦九韶算法原理,将所给多项式改写,然后由

13、内到外逐次计算即可.,解: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.81873. 即f(-0.2)=0.81873.,误区警示:利用秦九韶算法计算多项式值关键是能正确地将所给多项式改写,然后由内向外逐次计算,由于后项计算需用到前项的结果,故应认真

14、细心,确保中间结果的准确性.,变式训练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+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的最大公约数时,需要

15、做除法的次数是( ) A.1 B.2 C.3 D.4 解析:294=843+42,84=422. 故需做2次除法. 答案:B,2.两个整数490和910的最大公约数是( ) A.2 B.10 C.30 D.70 解析:910=9110,490=4910, 91=491+42, 49=421+7, 42=76. 91与49的最大公约数为7. 故910与490的最大公约数为70. 答案:D,3.用秦九韶算法计算多项式f(x)=3x6+4x5+5x4+6x3+7x2+8x+1当x=0.4时的值时,需要做乘法和加法的次数分别是( ) A.6,6 B.5,6 C.5,5 D.6,5 解析:f(x)的最高

16、次项为3x6,共含有7项,用秦九韶算法求x=0.4时的值时,需作乘法和加法各6次. 答案:A,4.用更相减损术求459和357的最大公约数,需作减法的次数为( ) A.4 B.5 C.6 D.7 解析:459-357=102; 357-102=255; 255-102=153; 153-102=51; 102-51=51. 共作了5次减法. 答案:B,5.378与90的最大公约数为_. 解析:378=904+18; 90=185. 378与90的最大公约数是18. 答案:18,6.用秦九韶算法求多项式f(x)=x4-2x3+3x2-7x-5当x=4时的值,给出如下数据: 0 2 11 37 1

17、43 其运算过程中(包括最终结果)会出现的数有_(只填序号). 答案:,解析:将多项式写成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 循环,8.请将以下用“更相减损术”求两个正整数a,b的最大公约数的程序补充完整: INPUT a INPUT b WHILE ab IF ab THEN a=a-b ELSE,_ END IF WEND PRINT a END 解析:阅读程序知,当ab时,作

18、减法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=8 v1=82+5=21, v2=212+0=42, v3=422+3=87,v4=872+0=174, v5=1742+0=