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

1.3 算法案例算法案例第一课时第一课时 辗转相除法与更相减损术辗转相除法与更相减损术 秦九韶算法秦九韶算法2021/8/9 星期一1自自 学学 导导 引引1.理解辗转相除法与更相减损术的含义理解辗转相除法与更相减损术的含义,了解执行过程了解执行过程.2.掌握秦九韶算法的计算过程掌握秦九韶算法的计算过程,了解它在数学计算中的应用了解它在数学计算中的应用.3.进一步体会算法的基本思想进一步体会算法的基本思想.2021/8/9 星期一2课课 前前 热热 身身1.辗转相除法是用于求辗转相除法是用于求_的一种方法的一种方法,这种算法由欧几里得在公元前这种算法由欧几里得在公元前300年年左右首先提出左右首先提出,因而又叫因而又叫_.2.所谓辗转相除法所谓辗转相除法,就是对于给定的两就是对于给定的两个数个数,用用_除以除以_,若余若余数不为零数不为零,则将则将_构成新的构成新的一对数一对数,继续上面的除法继续上面的除法,直到大数被直到大数被小数除尽小数除尽,则这时则这时_就是原来就是原来两个数的最大公约数两个数的最大公约数.两个正整数的最大公约数两个正整数的最大公约数欧几里得算法欧几里得算法较大的数较大的数较小的数较小的数除数与余数除数与余数除数除数2021/8/9 星期一33.更相减损术是我国古代数学专著更相减损术是我国古代数学专著_中介绍的一种中介绍的一种求两数最大公约数的方法求两数最大公约数的方法.其基本过程是其基本过程是:对于给定的两数对于给定的两数,用用_,接着把所得的接着把所得的_与与_比较比较,并以大数减小数并以大数减小数,继续这个操作继续这个操作,直到所得的数直到所得的数_为为止止,则这个数就是所求的最大公约数则这个数就是所求的最大公约数.4.秦九韶算法是我国南宋数学家秦九韶算法是我国南宋数学家_在他的代表作在他的代表作_中提出的一种用于计算一元中提出的一种用于计算一元n次多项式的值的次多项式的值的方法方法.九章算术九章算术大数减小数大数减小数差差减数减数相等相等秦九韶秦九韶数书九章数书九章2021/8/9 星期一4名名 师师 讲讲 解解1.辗转相除法辗转相除法2021/8/9 星期一5(1)辗转相除的原理辗转相除的原理.设设m,n是两个整数是两个整数(不妨设不妨设mn),用用m除以除以n,若商为若商为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和和r1,m和和n的最大公约数的最大公约数.2021/8/9 星期一6(2)辗转相除法的算法分析辗转相除法的算法分析.由以上辗转相除法的原理可由以上辗转相除法的原理可以发现以发现,辗转相除法的基本步辗转相除法的基本步骤是用较大的数除以较小的骤是用较大的数除以较小的数数,考虑到算法中的赋值语句考虑到算法中的赋值语句可以对同一变量多次赋值可以对同一变量多次赋值,我们可以把较大的数用变量我们可以把较大的数用变量m表示表示,把较小的数用变量把较小的数用变量n表示表示,这这样式子样式子m=nq+r(0rn)就是一个反复执行的步骤就是一个反复执行的步骤,因此可以用循环结构实现算法因此可以用循环结构实现算法.如上如上图图.2021/8/9 星期一7(3)任何两个数任何两个数,用辗转相除法求其最大公约数的程序框图用辗转相除法求其最大公约数的程序框图.由于辗转相除法总是用较大的数去除以较小的数由于辗转相除法总是用较大的数去除以较小的数,所以首先要对一开所以首先要对一开始给定的两数的大小进行判断始给定的两数的大小进行判断,并将大数赋给并将大数赋给m,小数赋给小数赋给n,然后再然后再执行下面的过程执行下面的过程.程序框图如下图所示程序框图如下图所示:2021/8/9 星期一82021/8/9 星期一9(4)辗转相除法求两个数的最大公约数的程序设计辗转相除法求两个数的最大公约数的程序设计.INPUT “a,b”;a,bIF ab THENt=aa=bb=tEND IFr=a MOD bWHILE r0a=bb=rr=a MOD bWENDPRINT bEND2021/8/9 星期一102.更相减损术更相减损术(1)更相减损术求两数最大公约数的过程与算法设计更相减损术求两数最大公约数的过程与算法设计:对于给定的两个数对于给定的两个数,用较大的数减去较小的数用较大的数减去较小的数,接着把得到的差与较小接着把得到的差与较小的数比较的数比较,用这时两个数中的较大的数减去较小的数用这时两个数中的较大的数减去较小的数,继续这样的操继续这样的操作作(大数减小数大数减小数),直到所得的数相等为止直到所得的数相等为止,那么这个数那么这个数(等数等数)就是所就是所求的最大公约数求的最大公约数.显然显然,上述过程中大数减去小数是一个重复执行的过程上述过程中大数减去小数是一个重复执行的过程,因此只需将大因此只需将大数赋给变量数赋给变量m,小数赋给变量小数赋给变量n,那么那么m-n就可以通过循环结构实现算就可以通过循环结构实现算法法.2021/8/9 星期一11(2)更相减损术求最大公约数的程序设计更相减损术求最大公约数的程序设计:INPUT “a,b”;a,bWHILE abIF ab THENa=a-bELSEb=b-aEND IFWENDPRINT aEND2021/8/9 星期一123.秦九韶算法秦九韶算法(1)秦九韶算法过程分析秦九韶算法过程分析:设设Pn(x)=anxn+an-1xn-1+a1x+a0,将其改写为将其改写为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,2021/8/9 星期一13这样我们便可由这样我们便可由a0依次求出依次求出v1,v2,vn:v1=v0 x+an-1,v2=v1x+an-2,v3=v2x+an-3,vn=vn-1x+a0.显然显然,用秦九韶算法求用秦九韶算法求n次多项式的值时只需做次多项式的值时只需做n次乘法和次乘法和n次加法运次加法运算算.2021/8/9 星期一14(2)秦九韶算法程序框图秦九韶算法程序框图:以以5次多项式次多项式f(x)=a5x5+a4x4+a3x3+a2x2+a1x+a0当当x=x0时为例时为例,如下图如下图:2021/8/9 星期一152021/8/9 星期一16典典 例例 剖剖 析析题型一题型一 求两个数的最大公约数求两个数的最大公约数2021/8/9 星期一17例例1:分别用辗转相除法和更相减损术逐步列出求分别用辗转相除法和更相减损术逐步列出求(1)98和和63;(2)8251和和6105的最大公约数的步骤的最大公约数的步骤,你有什么发现你有什么发现?对优劣作出评判对优劣作出评判.分析分析:辗转相除法是做两个数的带余除法辗转相除法是做两个数的带余除法,更相减损术是做两个数的减更相减损术是做两个数的减法法.2021/8/9 星期一18解解:(1)98和和63辗转相除法辗转相除法S1 98=63 1+35,S2 63=35 1+28,S3 35=281+7,S4 28=4 7,最大公约数为最大公约数为7.2021/8/9 星期一19更相减损术更相减损术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.2021/8/9 星期一20(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.2021/8/9 星期一21辗转相除法和更相减损术本质是一致的辗转相除法和更相减损术本质是一致的,除法运算若用加法与减法运除法运算若用加法与减法运算定义算定义,x(x0)除以除以y(y0)就是从就是从x中一次又一次地减去中一次又一次地减去y,直至直至xy为止为止.所减的次数即为商所减的次数即为商,所减的余数就是所求余数所减的余数就是所求余数.2021/8/9 星期一22更相减损术更相减损术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,2021/8/9 星期一23S8 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.2021/8/9 星期一24(2)中中 S4 1813=3335+148 在在1813中可减中可减5次次333.从形式上看更相减损术比辗转相除法复杂从形式上看更相减损术比辗转相除法复杂,但计算机更但计算机更“喜欢喜欢”做加做加减法减法.加减法比乘除法快几百倍加减法比乘除法快几百倍.变式训练变式训练1:用辗转相除法求用辗转相除法求80和和36的最大公约数的最大公约数,并用更相减损术检并用更相减损术检验所得结果验所得结果.分析分析:将将80作为大数作为大数,36作为小数作为小数,执行辗转相除法和更相减损术的步执行辗转相除法和更相减损术的步骤即可骤即可.2021/8/9 星期一25解解:用辗转相除法用辗转相除法:80=362+8,36=84+4,8=42+0.故故80和和36的最大公约数是的最大公约数是4.用更相减损术检验用更相减损术检验:80-36=44,2021/8/9 星期一2644-36=8,36-8=28,28-8=20,20-8=12,12-8=4,8-4=4.80和和36的最大公约数是的最大公约数是4.2021/8/9 星期一27题型二题型二 求三个数的最大公约数求三个数的最大公约数例例2:求三个数求三个数175 100 75的最大公约数的最大公约数.分析分析:求三个数的最大公约数时求三个数的最大公约数时,可以先求出其中两个数的最大公约数可以先求出其中两个数的最大公约数,用这个最大公约数再与第三个数求最大公约数用这个最大公约数再与第三个数求最大公约数,所得结果就是这三所得结果就是这三个数的最大公约数个数的最大公约数.2021/8/9 星期一28解解:解法解法1(辗转相除法辗转相除法):先求先求175与与100的最大公约数的最大公约数:175=1001+75,100=751+25,75=253.175与与100的最大公约数是的最大公约数是25.以下再求以下再求25与与75的最大公约数的最大公约数:75=25325和和75的最大公约数是的最大公约数是25.故故25是是75和和25的最大公约数的最大公约数,也就是也就是175 100 75的最大公约数的最大公约数.2021/8/9 星期一29解法解法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.2021/8/9 星期一30注注:解法解法2的过程可简记为的过程可简记为(175,100,75)=(175-100,100-75,75)=(75,25,75)=(75-225,25,75-252)=(25,25,25)三个数三个数175,100,25的最大公约数为的最大公约数为25.规律技巧规律技巧:本题的解法可以推广到求多个数的最大公约数本题的解法可以推广到求多个数的最大公约数,只需依次计只需依次计算即可算即可.2021/8/9 星期一31变式训练变式训练2:求三个数求三个数324,243,108的最大公约数的最大公约数.解解:解法解法1:先求先求324与与243的最大公约数的最大公约数,324=2431+81,243=813,324与与243的最大公约数为的最大公约数为81.下面再求下面再求108与与81的最大公约数的最大公约数:108=81+27,81=273.108与与81的最大公约数是的最大公约数是27.故故324,243,108的最大公约数为的最大公约数为27.2021/8/9 星期一32解法解法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.2021/8/9 星期一33题型三题型三 秦九韶算法的应用秦九韶算法的应用例例3:用秦九韶算法求多项式用秦九韶算法求多项式f(x)=1+x+0.5x2+0.16667x3+0.04167x4+0.00833x5在在x=-0.2的值的值.分析分析:可根据秦九韶算法原理可根据秦九韶算法原理,将所给多项式改写将所给多项式改写,然后由内到外逐次然后由内到外逐次计算即可计算即可.2021/8/9 星期一34解解: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.2021/8/9 星期一35误区警示误区警示:利用秦九韶算法计算多项式值关键是能正确地将所给多项利用秦九韶算法计算多项式值关键是能正确地将所给多项式改写式改写,然后由内向外逐次计算然后由内向外逐次计算,由于后项计算需用到前项的结果由于后项计算需用到前项的结果,故应认真故应认真 细心细心,确保中间结果的准确性确保中间结果的准确性.2021/8/9 星期一36变式训练变式训练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.2021/8/9 星期一37x=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.2021/8/9 星期一38技技 能能 演演 练练基础强化基础强化 2021/8/9 星期一391.用辗转相除法求用辗转相除法求294和和84的最大公约数时的最大公约数时,需要做除法的次数是需要做除法的次数是()A.1 B.2C.3 D.4解析解析:294=843+42,84=422.故需做故需做2次除法次除法.答案答案:B2021/8/9 星期一402.两个整数两个整数490和和910的最大公约数是的最大公约数是()A.2 B.10C.30 D.70解析解析:910=9110,490=4910,91=491+42,49=421+7,42=76.91与与49的最大公约数为的最大公约数为7.故故910与与490的最大公约数为的最大公约数为70.答案答案:D2021/8/9 星期一413.用秦九韶算法计算多项式用秦九韶算法计算多项式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时时的值时的值时,需作乘法和加法各需作乘法和加法各6次次.答案答案:A2021/8/9 星期一424.用更相减损术求用更相减损术求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次减法次减法.答案答案:B2021/8/9 星期一435.378与与90的最大公约数为的最大公约数为_.解析解析:378=904+18;90=185.378与与90的最大公约数是的最大公约数是18.答案答案:182021/8/9 星期一446.用秦九韶算法求多项式用秦九韶算法求多项式f(x)=x4-2x3+3x2-7x-5当当x=4时的值时的值,给出如给出如下数据下数据:0 2 11 37 143其运算过程中其运算过程中(包括最终结果包括最终结果)会出现的数有会出现的数有_(只填序号只填序号).答案答案:2021/8/9 星期一45解析解析:将多项式写成将多项式写成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.2021/8/9 星期一46解析解析:由秦九韶算法知由秦九韶算法知,应填应填an-k.在程序中可以用循环语句来实现在程序中可以用循环语句来实现.答案答案:an-k 循环循环2021/8/9 星期一478.请将以下用请将以下用“更相减损术更相减损术”求两个正整数求两个正整数a,b的最大公约数的程序的最大公约数的程序补充完整补充完整:INPUT aINPUT bWHILE abIF ab THENa=a-bELSE2021/8/9 星期一48_END IFWENDPRINT aEND解析解析:阅读程序知阅读程序知,当当ab时时,作减法作减法a-b,当当ab时时,作减法作减法b-a,因此应填因此应填b=b-a.答案答案:b=b-a2021/8/9 星期一49能力提升能力提升9.用秦九韶算法求多项式用秦九韶算法求多项式f(x)=8x7+5x6+3x4+2x+1当当x=2时的值时的值.分析分析:注意本题中有几项不存在注意本题中有几项不存在,此时在计算时此时在计算时,我们应该将这些项加我们应该将这些项加上上,比如含比如含x3这一项可看做这一项可看做0 x3.2021/8/9 星期一50解解:根据秦九韶算法根据秦九韶算法,把多项式改写成如下形式把多项式改写成如下形式: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,2021/8/9 星期一51v4=872+0=174,v5=1742+0=348,v6=3482+2=698,v7=6982+1=1397.当当x=2时时,多项式的值为多项式的值为1397.2021/8/9 星期一5210.有甲有甲 乙乙 丙三种溶液丙三种溶液,分别为分别为4200毫升毫升,3220毫升和毫升和2520毫升毫升,现现要将它们分别全部装入小瓶中要将它们分别全部装入小瓶中,每个瓶子装入液体的体积相同每个瓶子装入液体的体积相同.问问:要使所有溶液都刚好装满小瓶中且所用瓶子最少要使所有溶液都刚好装满小瓶中且所用瓶子最少.则小瓶的容积应则小瓶的容积应为多少毫升为多少毫升?2021/8/9 星期一53解解:由题意可知由题意可知,就是求这三种溶液体积的最大公约数就是求这三种溶液体积的最大公约数.先求先求4200与与3220的最大公约数的最大公约数4200=32201+980,3220=9803+280,980=2803+140,280=1402.2021/8/9 星期一544200与与3220的最大公约数的最大公约数140.再求再求140与与2520的最大公约数的最大公约数,2520=14018.140与与2520的最大公约数为的最大公约数为140.综上知综上知,4200,3220和和2520的最大公约数为的最大公约数为140.小瓶的容积应为小瓶的容积应为140毫升毫升.2021/8/9 星期一55品味高考品味高考11.(2008宁夏模拟宁夏模拟)用辗转相除法计算用辗转相除法计算60与与48的最大公约数时的最大公约数时,需要需要做的除法次数是做的除法次数是()A.1 B.2C.3 D.4解析解析:60=481+12,48=124+0.仅需要两步运算仅需要两步运算.答案答案:B2021/8/9 星期一5612.(2010山东模拟山东模拟)利用秦九韶算法计算函数利用秦九韶算法计算函数f(x)=x+2x2+3x3+4x4+5x5的值时的值时,需要做加法需要做加法 乘法的次数分别为乘法的次数分别为_ _.解析解析:将函数变形为将函数变形为f(x)=(5x+4)x+3)x+2)x+1)x.由此可知由此可知,共需要做共需要做4次加法次加法,5次乘法次乘法.452021/8/9 星期一57