《辗转相除法与更相减损术课件.ppt》由会员分享，可在线阅读，更多相关《辗转相除法与更相减损术课件.ppt（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、知识回顾知识回顾n1 回顾算法的三种表述：回顾算法的三种表述：自然语言自然语言,程序程序框图框图,程序语言程序语言.n程序框图有三种逻辑结构程序框图有三种逻辑结构:顺序结构顺序结构,条件结条件结构构,循环结构循环结构.n程序语言有五种基本算法语句程序语言有五种基本算法语句:输入语句输入语句,输输出语句出语句,赋值语句赋值语句,条件语句条件语句,循环语句循环语句.2回顾求两个数的最大公约数的法回顾求两个数的最大公约数的法 先用两个公有的质因数连续去除，一直除到先用两个公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除所得的商是互质数为止，然后把所有的除数连乘起来数连乘起来. 3.
2、 求求24与与30的最大公约数的最大公约数 求求210与与462的最大公约数的最大公约数如何求如何求8251和和6105的最大公约数？的最大公约数？ 所以，所以，24和和30的最大公约数为的最大公约数为6210和和462的最大公约数为的最大公约数为4224（1）2123015435210（2）21054622313357577111 1、辗转相除法（欧几里得算法）、辗转相除法（欧几里得算法） 所谓辗转相除法所谓辗转相除法, ,就是对于给定的两个数就是对于给定的两个数, ,用较大的数除以较用较大的数除以较小的数小的数. .若余数不为零若余数不为零, ,则将余数和较小的数构成新的一对数则将余数和较
3、小的数构成新的一对数, ,继继续上面的除法续上面的除法, ,直到大数被小数除尽直到大数被小数除尽, ,则这时较小的数就是原来两则这时较小的数就是原来两个数的最大公约数个数的最大公约数. .例例1.用辗转相除法求用辗转相除法求98与与63的最大公约数的最大公约数.98=1633563=1 352835=1 28728=4 70所以，所以，98与与63的最大公约数为的最大公约数为7 7新新 课课探究探究1。 用辗转相除法求用辗转相除法求225和和135的最大的最大公约数公约数完整的过程完整的过程8251=61051+2146 6105=21462+1813 2146=18131+3331813=3
4、335+148333=1482+37148=374+0显然显然37是是148和和37的最大的最大公约数，也就是公约数，也就是8251和和6105的最大公约数的最大公约数 显然显然45是是90和和45的最大公约数，的最大公约数，也就是也就是225和和135的最大公约数的最大公约数 探究探究2：辗转相除法的解题步骤：辗转相除法的解题步骤如何？其蕴含的数学原理是什如何？其蕴含的数学原理是什么？么？225=1351+90135=901+4590=452 辗转相除法是一个反复执行直到余数等于辗转相除法是一个反复执行直到余数等于0 0停止的步骤停止的步骤, ,这实际上是一个循环结构这实际上是一个循环结构m
5、=nm=nq qr 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.程序框图程序框图程程 序序r=m MOD nr=m MOD nm=nm=n是是否否n=rn=r开始开始输入输入m,nm,nr=0?r=0? 输出输出m m结束结束INPUT “m,n=“;
6、m,nDOLOOP UNTIL r = m MOD nm = nn = rr=0PRINT mEND程序框图程序框图程程 序序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=14问题提出：除了用上述算法求两个数的最问题提出：除了用上述算法求两个数的最 大公约数之外还有没有别的算法？大公约数之外还有没有别的算法？5点拨：用点拨：用“更相减损术更相减损术”：更相减损术，更相减
7、损术，是我国数学家刘徽的专著是我国数学家刘徽的专著九章算术九章算术中中记载的更相减损术求最大公约数的步骤记载的更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母如下：可半者半之，不可半者，副置分母分子之数，以少减分子之数，以少减 多，更相减损，求其等多，更相减损，求其等也也.，以等数约之，以等数约之翻译出来为：翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶第一步：任意给出两个正数；判断它们是否都是偶数若是，用数若是，用2 2约简；若不是，执行第二步约简；若不是，执行第二步第二步：以较大的数减去较小的数，接着把较小的第二步：以较大的数减去较小的数，接着把较小的数与所得的差
8、比较，并以大数减小数继续这个操作数与所得的差比较，并以大数减小数继续这个操作，直到所得的数相等为止，则这个数（等数）就是所，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数求的最大公约数例例2 2 用更相减损术求用更相减损术求9191与与4949的最大公约数，的最大公约数，并用并用辗转相除法检验结果辗转相除法检验结果 解法解法1：（更相减损术）由于更相减损术）由于49不是偶数，把不是偶数，把91和和49以以大数减小数，并辗转相减，大数减小数，并辗转相减，即：即：914942 49427 42735 35728 28721 21714 147791与与49的最大公约数是的最大公约数是7
9、。解法解法2（辗转相除法）辗转相除法） 919149491 142 4942 4942421 17 7 42 427 76 6 91与与49的最大公约数是的最大公约数是7。探究探究3:怎样用更相减损术求怎样用更相减损术求182与与98的最大公约数的最大公约数? n方法：由于方法：由于 182与与98 都是偶数，故将它们同除都是偶数，故将它们同除以以2，得，得91与与49，再用上面的方法求得，再用上面的方法求得91与与49的最的最大公约数为大公约数为7，则，则72=14为为182与与98的最大公约数的最大公约数.INPUT “m,n=”;m,nWHILE mn IF mn THEN m=m-n
10、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)输出最大公约数输出最大公约数n探究探究4:4:用更相减损术求用更相减损术求8080与与3636的最大公约数，并用的最大公约数，并用辗转相除法检验结果辗转相除法检验结果 n用更相减损术用更相减损术 : : 用辗转相除法检验用辗转相除法检验: : 80-36=44 8
11、0= 36 80-36=44 80= 362 28 8 44-36=8 44-36=836= 836= 84 44 4 36-8=28 8= 436-8=28 8= 42 20 0 28-8=20 28-8=20 20-8=12 80 20-8=12 80与与3636的最大公约数是的最大公约数是4 4 12-8=4 12-8=4 8-4=4 8-4=4 80 80与与3636的最大公约数是的最大公约数是4 4思考思考: : “辗转相除法辗转相除法”与与“更相减损术更相减损术”的区的区别是什么？别是什么？ 都是求最大公约数的方法，辗转相除法以都是求最大公约数的方法，辗转相除法以除法为主，更相减损
12、术以减法为主，计算次除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较两个数字大小区别较大时计算次数的区别较明显明显结果上，辗转相除法体现结果是以相除余结果上，辗转相除法体现结果是以相除余数为数为0 0得到，而更相减损术则以减数与差相等得到，而更相减损术则以减数与差相等而得到而得到. .板块三：知识拓展板块三：知识拓展n问题提出：如何求三个正整数的最大公约问题提出：如何求三个正整数的最大公约数？数？n分析：可以先求出其中两个数的最大公约分析：可以先求出其中两个数的最大公约数，用这两个数的最大公
13、约数再与第三个数，用这两个数的最大公约数再与第三个数求最大公约数，所得结果就是这三个数数求最大公约数，所得结果就是这三个数的最大公约数。的最大公约数。 例例3求三个数求三个数175、100、75的最大公约数的最大公约数n解：先求解：先求175与与100的最大公约数：的最大公约数：n175=1001+75, 100=751+25,n75=253, n 175与与100的最大公约数是的最大公约数是25.n再求再求75与与25的最大公约数的最大公约数:由由75=253, n或或752550，502525，n得得75与与25的最大公约数是的最大公约数是25，三个数三个数175、100、75的最大公约数
14、是的最大公约数是25探究探究6:如何求如何求4个正整数的最大公约数个正整数的最大公约数？n方法方法1:可以先求其中两个数的最大公约数可以先求其中两个数的最大公约数a，再求再求a与第三个数的公约数与第三个数的公约数b，再求，再求b与第四与第四个数的公约数个数的公约数c，则，则c为这为这4个数的最大公约数。个数的最大公约数。n方法方法2:将将4个数分两组，每组两个数，先求个数分两组，每组两个数，先求 每组两个数的最大公约数每组两个数的最大公约数a与与b，再求，再求a与与b的的 最大公约数最大公约数c,则则c就是这就是这4个数的最大公约数。个数的最大公约数。板块五：课堂总结板块五：课堂总结n1“辗转
15、相除法辗转相除法”与与“更相减损术更相减损术”都是求最大都是求最大公约数有的效方法；公约数有的效方法；n2计算上辗转相除法以除法为主，更相减损术以计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数较少，特别当两个数字大小区别较大时计算次数的区别较明显；从结果体现形式来看，辗转相除的区别较明显；从结果体现形式来看，辗转相除法体现结果是以相除余数为法体现结果是以相除余数为0则得到，而更相减损则得到，而更相减损术则以减数与差相等而得到术则以减数与差相等而得到n3求三个以上求三个以上(含三个数含三个数)的数的最大公约数时，的数的最大公约数时，可依次通过求两个数的最大公约数与第三数的最可依次通过求两个数的最大公约数与第三数的最大公约数来求得大公约数来求得