辗转相除法与更相减损术课件

算法案例算法案例辗转相除法与更相减损术辗转相除法与更相减损术 算法案例辗转相除法与更相减损术 知识回顾知识回顾n n1 回顾算法的三种表述：回顾算法的三种表述：自然语言自然语言,程序程序框图框图,程序语言程序语言.n n程序框图有三种逻辑结构程序框图有三种逻辑结构:顺序结构顺序结构,条件结条件结构构,循环结构循环结构.n n程序语言有五种基本算法语句程序语言有五种基本算法语句:输入语句输入语句,输输出语句出语句,赋值语句赋值语句,条件语句条件语句,循环语句循环语句.知识回顾1 回顾算法的三种表述：自然语言,程序框图,程序2回顾求两个数的最大公约数的法回顾求两个数的最大公约数的法 先用两个公有的质因数连续去除，一直除到先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除所得的商是互质数为止，然后把所有的除数连乘起来数连乘起来.3.求求24与与30的最大公约数的最大公约数求求210与与462的最大公约数的最大公约数2回顾求两个数的最大公约数的法 先用两个公有的质因数连如何求如何求8251和和6105的最大公约数？的最大公约数？所以，所以，24和和30的最大公约数为的最大公约数为6210和和462的最大公约数为的最大公约数为4224（1）2123015435210（2）2105462231335757711如何求8251和6105的最大公约数？所以，24和30的最1 1、辗转相除法（欧几里得算法）、辗转相除法（欧几里得算法）所谓辗转相除法所谓辗转相除法,就是对于给定的两个数就是对于给定的两个数,用较大的数除以较用较大的数除以较小的数小的数.若余数不为零若余数不为零,则将余数和较小的数构成新的一对数则将余数和较小的数构成新的一对数,继继续上面的除法续上面的除法,直到大数被小数除尽直到大数被小数除尽,则这时较小的数就是原来两则这时较小的数就是原来两个数的最大公约数个数的最大公约数.例例1.用辗转相除法求用辗转相除法求98与与63的最大公约数的最大公约数.98=1633563=1 352835=1 28728=4 70所以，所以，98与与63的最大公约数为的最大公约数为7 7新新 课课1、辗转相除法（欧几里得算法）所谓辗转相除法,就是对探究探究1。用辗转相除法求用辗转相除法求225和和135的最大的最大公约数公约数完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3335+148333=1482+37148=374+0显然显然37是是148和和37的最大的最大公约数，也就是公约数，也就是8251和和6105的最大公约数的最大公约数 显然显然45是是90和和45的最大公约数，的最大公约数，也就是也就是225和和135的最大公约数的最大公约数 探究探究2：辗转相除法的解题步骤：辗转相除法的解题步骤如何？其蕴含的数学原理是什么如何？其蕴含的数学原理是什么？225=1351+90135=901+4590=452探究1。用辗转相除法求225和135的最大完整的过程825 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止的步骤停止的步骤,这实际上是一个循环结构这实际上是一个循环结构m=nqm=nqr r算法步骤算法步骤第一步：输入两个正整数第一步：输入两个正整数m,n(mn).m,n(mn).第二步：计算第二步：计算m m除以除以n n所得的余数所得的余数r.r.第三步：第三步：m=n,n=r.m=n,n=r.第四步：若第四步：若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m;m;否则转到第二步否则转到第二步.第五步：输出最大公约数第五步：输出最大公约数m.m.辗转相除法是一个反复执行直到余数等于0停止的步骤,这程序框图程序框图程程 序序r=m MOD nr=m MOD nm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr=0?r=0?输出输出m m结束结束INPUT“m,n=“;m,nDOLOOP UNTIL r=m MOD nm=nn=rr=0PRINT mEND程序框图程 序r=m MOD nm=n是否n=r开始输入m,程序框图程序框图程程 序序INPUT“m,n=“;m,nWHILE WEND r=m MOD nm=nn=rr0PRINT mENDr=1求求m m除以除以n n的余数的余数r rm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr0?r0?输出输出m m结束结束r=1r=1程序框图程 序INPUT“m,n=“;m,nWHILE W4问题提出：除了用上述算法求两个数的最问题提出：除了用上述算法求两个数的最 大公约数之外还有没有别的算法？大公约数之外还有没有别的算法？5点点拨拨：用用“更更相相减减损损术术”：更更相相减减损损术术，是是我我国国数数学学家家刘刘徽徽的的专专著著九九章章算算术术中中记记载载的的更更相相减减损损术术求求最最大大公公约约数数的的步步骤骤如如下下：可可半半者者半半之之，不不可可半半者者，副副置置分分母母分分子子之之数数，以以少少减减 多多，更更相相减减损损，求求其其等等也也.，以等数约之，以等数约之4问题提出：除了用上述算法求两个数的最 大公约数之外翻译出来为：翻译出来为：第第一一步步：任任意意给给出出两两个个正正数数；判判断断它它们们是是否否都都是是偶偶数若是，用数若是，用2 2约简；若不是，执行第二步约简；若不是，执行第二步第第二二步步：以以较较大大的的数数减减去去较较小小的的数数，接接着着把把较较小小的的数数与与所所得得的的差差比比较较，并并以以大大数数减减小小数数继继续续这这个个操操作作，直直到到所所得得的的数数相相等等为为止止，则则这这个个数数（等等数数）就就是是所所求求的最大公约数的最大公约数例例2 2 用更相减损术求用更相减损术求9191与与4949的最大公约数，的最大公约数，并用并用辗转相除法检验结果辗转相除法检验结果 翻译出来为：例2 用更相减损术求91与49的最大公约数，并解法解法1：（更相减损术）由于更相减损术）由于49不是偶数，把不是偶数，把91和和49以以大数减小数，并辗转相减，大数减小数，并辗转相减，即：即：914942 49427 42735 35728 28721 21714 147791与与49的最大公约数是的最大公约数是7。解法解法2（辗转相除法）辗转相除法）919149149142 4942 494214217 7 42 427676 91与与49的最大公约数是的最大公约数是7。解法1：（更相减损术）由于49不是偶数，把91和49以大数减探究探究探究探究3:3:怎样用更相减损术求怎样用更相减损术求怎样用更相减损术求怎样用更相减损术求182182与与与与9898的最大公约数的最大公约数的最大公约数的最大公约数?n n方法：由于方法：由于 182182与与与与9898 都是偶数，故将它们同除都是偶数，故将它们同除都是偶数，故将它们同除都是偶数，故将它们同除以以以以2 2，得，得，得，得9191与与与与4949，再用上面的方法求得，再用上面的方法求得，再用上面的方法求得，再用上面的方法求得9191与与与与4949的的的的最大公约数为最大公约数为最大公约数为最大公约数为7 7，则，则，则，则72=1472=14为为为为182182与与与与9898的最大公约的最大公约的最大公约的最大公约数数数数.探究3:怎样用更相减损术求182与98的最大公约数?方法INPUT“m,n=”;m,nWHILE mn IF mn THEN m=m-n ELSE n=n-m END IFWENDPRINT nEND程序框图程序框图输入输入m,n开始开始mn？mn？m=m-nn=n-m输出输出n结束结束NYYN算法步骤算法步骤(1)输入两个整数输入两个整数m，n(2)若若mn,转到转到(3),否则转到否则转到(4)(3)若若mn,则则m=m-n,否则否则n=n-m,转到转到(2)(4)输出最大公约数输出最大公约数nINPUT“m,n=”;m,n程序框图输入m,n开始mn探究探究探究探究4:4:4:4:用更相减损术求用更相减损术求用更相减损术求用更相减损术求80808080与与与与36363636的最大公约数，并用的最大公约数，并用的最大公约数，并用的最大公约数，并用辗转相除法检验结果辗转相除法检验结果辗转相除法检验结果辗转相除法检验结果 n n用更相减损术用更相减损术用更相减损术用更相减损术 :用辗转相除法检验用辗转相除法检验用辗转相除法检验用辗转相除法检验:80-36=44 80=362 80-36=44 80=362 80-36=44 80=362 80-36=44 80=3628 8 8 8 44-36=8 44-36=8 44-36=8 44-36=836=8436=8436=8436=844 4 4 4 36-8=28 8=4236-8=28 8=4236-8=28 8=4236-8=28 8=420 0 0 0 28-8=20 28-8=20 28-8=20 28-8=20 20-8=12 80 20-8=12 80 20-8=12 80 20-8=12 80与与与与36363636的最大公约数是的最大公约数是的最大公约数是的最大公约数是4 4 4 4 12-8=4 12-8=4 12-8=4 12-8=4 8-4=4 8-4=4 8-4=4 8-4=4 80 80 80 80与与与与36363636的最大公约数是的最大公约数是的最大公约数是的最大公约数是4 4 4 4探究4:用更相减损术求80与36的最大公约数，并用辗转相除法思考思考:“辗转相除法辗转相除法”与与“更相减损术更相减损术”的区的区别是什么？别是什么？都都是是求求最最大大公公约约数数的的方方法法，辗辗转转相相除除法法以以除除法法为为主主，更更相相减减损损术术以以减减法法为为主主，计计算算次次数数上上辗辗转转相相除除法法计计算算次次数数相相对对较较少少，特特别别当当两两个个数数字字大大小小区区别别较较大大时时计计算算次次数数的的区区别别较较明显明显结结果果上上，辗辗转转相相除除法法体体现现结结果果是是以以相相除除余余数数为为0 0得得到到，而而更更相相减减损损术术则则以以减减数数与与差差相相等等而得到而得到.思考:“辗转相除法”与“更相减损术”的区别是什么？都是板块三：知识拓展板块三：知识拓展n n问题提出：如何求三个正整数的最大公约问题提出：如何求三个正整数的最大公约数？数？n n分析：可以先求出其中两个数的最大公约分析：可以先求出其中两个数的最大公约数，用这两个数的最大公约数再与第三个数，用这两个数的最大公约数再与第三个数求最大公约数，所得结果就是这三个数数求最大公约数，所得结果就是这三个数的最大公约数。的最大公约数。板块三：知识拓展问题提出：如何求三个正整数的最大公约数？例例3求三个数求三个数175、100、75的最大公约数的最大公约数n n解：先求解：先求175与与100的最大公约数：的最大公约数：n n175=1001+75,100=751+25,n n75=253,n n 175与与100的最大公约数是的最大公约数是25.n n再求再求75与与25的最大公约数的最大公约数:由由75=253,n n或或752550，502525，n n得得75与与25的最大公约数是的最大公约数是25，三个数三个数175、100、75的最大公约数是的最大公约数是25例3求三个数175、100、75的最大公约数解：先求175探究探究6:如何求如何求4个正整数的最大公约数个正整数的最大公约数？n n方法方法1:可以先求其中两个数的最大公约数可以先求其中两个数的最大公约数a，再求，再求a与第三个数的公约数与第三个数的公约数b，再求，再求b与第与第四个数的公约数四个数的公约数c，则，则c为这为这4 4个数的最大公约个数的最大公约个数的最大公约个数的最大公约数。数。数。数。n n方法方法2:将将4个数分两组，每组两个数，先求个数分两组，每组两个数，先求每组两个数的最大公约数每组两个数的最大公约数a与与b，再求，再求a与与b的的最大公约数最大公约数c,则则c就是这就是这4 4个数的最大公约数。个数的最大公约数。个数的最大公约数。个数的最大公约数。探究6:如何求4个正整数的最大公约数？方法1:可以先求其中两板块五：课堂总结板块五：课堂总结n n1 1“辗转相除法辗转相除法辗转相除法辗转相除法”与与与与“更相减损术更相减损术更相减损术更相减损术”都是求最大都是求最大都是求最大都是求最大公约数有的效方法；公约数有的效方法；公约数有的效方法；公约数有的效方法；n n2 2计算上辗转相除法以除法为主，更相减损术以计算上辗转相除法以除法为主，更相减损术以计算上辗转相除法以除法为主，更相减损术以计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对减法为主，计算次数上辗转相除法计算次数相对减法为主，计算次数上辗转相除法计算次数相对减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数较少，特别当两个数字大小区别较大时计算次数较少，特别当两个数字大小区别较大时计算次数较少，特别当两个数字大小区别较大时计算次数的区别较明显；从结果体现形式来看，辗转相除的区别较明显；从结果体现形式来看，辗转相除的区别较明显；从结果体现形式来看，辗转相除的区别较明显；从结果体现形式来看，辗转相除法体现结果是以相除余数为法体现结果是以相除余数为法体现结果是以相除余数为法体现结果是以相除余数为0 0则得到，而更相减损则得到，而更相减损则得到，而更相减损则得到，而更相减损术则以减数与差相等而得到术则以减数与差相等而得到术则以减数与差相等而得到术则以减数与差相等而得到n n3 3求三个以上求三个以上求三个以上求三个以上(含三个数含三个数含三个数含三个数)的数的最大公约数时，的数的最大公约数时，的数的最大公约数时，的数的最大公约数时，可依次通过求两个数的最大公约数与第三数的最可依次通过求两个数的最大公约数与第三数的最可依次通过求两个数的最大公约数与第三数的最可依次通过求两个数的最大公约数与第三数的最大公约数来求得大公约数来求得大公约数来求得大公约数来求得 板块五：课堂总结1“辗转相除法”与“更相减损术”都是求最大