《辗转相除法与更相减损术》导学案.ppt
辗转相除法与更相辗转相除法与更相减损术减损术导 学 固 思. . . 1.理解学习基本算法语句的意义.2.学会循环语句的基本用法.3.理解算法步骤、程序框图和算法语句的关系,学会编写算法语句.导 学 固 思. . . 在初中,我们已经学过求最大公约数的方法,你能求出18与30的公约数吗?我们都是利用找公约数的方法来求最大公约数,如果公约数比较大而且根据我们的观察又不能得到一些公约数,我们又应该怎样求它们的最大公约数?比如求8251与6105的最大公约数?导 学 固 思. . . 在上面的问题中,可以通过 与 求两个正整数的最大公约数. 更相减损术问题1 辗转相除法导 学 固 思. . . 问题2辗转相除法:用于求 的一种方法,这种算法是由 欧几里得在公元前300年左右首先提出的,因而又叫 .利用辗转相除法求最大公约数的步骤如下:第一步,用较大的数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约简),以 减去 ,接着把所得的差与较小的数比较,并以 减 ,直到所得的数 为止,则这个数(等数)或这个数与约简的数的乘积就是所求的 .利用更相减损术求最大公约数的步骤如下:第一步,任意给定两个正整数,判断它们是否都是偶数.若是,用2约简;若不是,执行第二步.相等较大的数大数较小的数小数问题3最大公约数导 学 固 思. . . 第二步,把较大的数减去较小的数,把较小的数与所得的差比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.涉及多个正整数寻求最大公约数时,对任意两个正整数运用辗转相除法或更相减损术求出最大公约数,再与第三个正整数继续求最大公约数,直到最后一个正整数. 导 学 固 思. . . (1)都是求 的方法,计算上辗转相除法以 为主,更相减损术以 为主,计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较明显的时候.(2)从结果体现形式来看,辗转相除法是以相除余数为 作为判断依据而得到,而更相减损术则由减数与差 而得到的.减法 最大公约数0除法相等辗转相除法和更相减损术的区别和联系问题问题4 4导 学 固 思. . . 45和150的最大公约数和最小公倍数分别是().A.5,150B.15,450C.450,15D.15,1501B【解析】利用辗转相除法求45和150的最大公约数:150=453+15,45=153,所以45和150的最大公约数为15.所以45和150的最小公倍数为15(4515)(15015)=450,故选B.导 学 固 思. . . 378与90的最大公约数为().A.20B.12C.18D.16C2 【解析】辗转相除法: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+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. 利用更相减损术求最大公约数用更相减损术求440与556的最大公约数.【解析】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=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, 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-102=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. 导 学 固 思. . .
