《辗转相除法与更相减损术》导学案.ppt

《《辗转相除法与更相减损术》导学案.ppt》由会员分享，可在线阅读，更多相关《《辗转相除法与更相减损术》导学案.ppt（23页珍藏版）》请在三一办公上搜索。

1、辗转相除法与更相减损术,第8课时,1.理解学习基本算法语句的意义.2.学会循环语句的基本用法.3.理解算法步骤、程序框图和算法语句的关系,学会编写算法语句.,在初中,我们已经学过求最大公约数的方法,你能求出18与30的公约数吗?我们都是利用找公约数的方法来求最大公约数,如果公约数比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数?比如求8251与6105的最大公约数?,在上面的问题中,可以通过 与 求两个正整数的最大公约数.,更相减损术,辗转相除法,辗转相除法:用于求 的一种方法,这种算法是由 欧几里得在公元前300年左右首先提出的,因而又叫.利用辗转相除法求最大公

2、约数的步骤如下:第一步,用较大的数m除以较小的数n得到一个商q0和一个余数r0.第二步,若r0=0,则n为m,n的最大公约数;若r00,则用除数n除以余数r0得到一个商q1和一个余数r1.,两个数的最大公约数,欧几里得算法,第三步,若r1=0,则r1为m,n的最大公约数;若r10,则用除数r0除以余数r1得到一个商q2和一个余数r2.依次计算直至rn=0,此时所得到的rn-1即为所求的最大公约数.,更相减损术:任给两个正整数(若是偶数,先用2约简),以 减去,接着把所得的差与较小的数比较,并以 减,直到所得的数 为止,则这个数(等数)或这个数与约简的数的乘积就是所求的.利用更相减损术求最大公约

3、数的步骤如下:第一步,任意给定两个正整数,判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.,相等,较大的数,大数,较小的数,小数,最大公约数,第二步,把较大的数减去较小的数,把较小的数与所得的差比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.涉及多个正整数寻求最大公约数时,对任意两个正整数运用辗转相除法或更相减损术求出最大公约数,再与第三个正整数继续求最大公约数,直到最后一个正整数.,(1)都是求 的方法,计算上辗转相除法以 为主,更相减损术以 为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较

4、明显的时候.(2)从结果体现形式来看,辗转相除法是以相除余数为 作为判断依据而得到,而更相减损术则由减数与差 而得到的.,减法,最大公约数,0,除法,相等,辗转相除法和更相减损术的区别和联系,45和150的最大公约数和最小公倍数分别是().A.5,150B.15,450C.450,15D.15,150,1,B,【解析】利用辗转相除法求45和150的最大公约数:150=453+15,45=153,所以45和150的最大公约数为15.所以45和150的最小公倍数为15(4515)(15015)=450,故选B.,378与90的最大公约数为().A.20B.12C.18D.16,C,2,【解析】辗转

5、相除法:378=904+18,90=185+0,378与90的最大公约数是18.,3,用更相减损术,求105与30的最大公约数时,需要做减法的次数是.,【解析】105-30=75,75-30=45,45-30=15,30-15=15.,4,4,写出用辗转相除法求下列两组数的最大公约数的过程.(1)8251与6105;(2)6731与2809.,【解析】(1)8251=61051+2146;6105=21462+1813;2146=18131+333;1813=3335+148;333=1482+37;148=374.最后的除数37就是8251和6105的最大公约数.(2)6731=28092+

6、1113;2809=11132+583;1113=5831+530;583=5301+53;530=5310.6731与2809的最大公约数为53.,利用辗转相除法求最大公约数求1734,816,1343的最大公约数.,【解析】用辗转相除法.先求1734和816的最大公约数,1734=8162+102;816=1028;所以1734与816的最大公约数为102.,再求102与1343的最大公约数,1343=10213+17;102=176.所以1343与102的最大公约数为17,即1734,816,1343的最大公约数为17.,7,利用更相减损术求最大公约数用更相减损术求440与556的最大公

7、约数.,【解析】556-440=116,440-116=324,324-116=208,208-116=92,116-92=24,92-24=68,68-24=44,44-24=20,24-20=4,20-4=16,16-4=12,12-4=8,8-4=4,所以440与556的最大公约数为4.,利用辗转相除法求最大公约数并用更相减损术检验用辗转相除法求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、8=12,12-8=4,8-4=4,80和36的最大公约数是4.,【解析】288=1232+42,123=422+39,42=391+3,39=313.288和123的最大公约数3.,试求288和123的最大公约数,求612,396,264的最大公约数.,【解析】两次运用更相减损术得:612-396=216,396-216=180,216-180=36,180-36=144,144-36=108 108-36=72,72-36=36.264-36=228,228-36=192,192-36=156,156-36=120,120-36=84,84-36=48,48-36=12,36-12=24,

9、24-12=12.所以612,396,264的最大公约数是12.,用辗转相除法求294和84的最大公约数,并用更相减损术检验你的结果.,【解析】294=843+42,84=422,即294与84的最大公约数是42.验证:294与84都是偶数可同时除以2,取147与42的最大公约数后再乘以2.147-42=105,105-42=63,63-42=21,42-21=21,294与84的最大公约数为212=42.,1.用更相减损术求459与357的最大公约数,需要做减法的次数为().A.4B.5C.6D.7,【解析】459-357=102,357-102=255,255-102=153,153-10

10、2=51,102-51=51,所以459与357的最大公约数为51,共做减法5次,故选B.,B,2.261和319的最大公约数是().A.3B.7C.29D.31,【解析】319=2611+58,261=584+29,58=292,最大公约数为29.,C,3.1343与816的最大公约数是.,【解析】1343=8161+527,816=5271+289,527=2891+238,289=2381+51,238=514+34,51=341+17,34=172,所以1343和816的最大公约数是17.,17,4.用辗转相除法求840与1764的最大公约数.,【解析】1764=8402+84,840=8410,所以840与1764的最大公约数为84.,