1、第一章第一章 算法初步算法初步 1.3 1.3 算法案例算法案例3 59 15 问题问题11：在小学，我们已经学过求最大公约数：在小学，我们已经学过求最大公约数的知识，你能求出的知识，你能求出1818与与3030的最大公约数吗？的最大公约数吗？创设情景，揭示课题创设情景，揭示课题18 30231818和和3030的最大公约数是的最大公约数是2 23=6.3=6.先用两个数公有的先用两个数公有的质因数质因数连续去除连续去除,一直除到一直除到所得的商是互质数为止所得的商是互质数为止,然后把所有的除数连然后把所有的除数连乘起来乘起来.案例案例1 1 辗转相除法与更相减损术辗转相除法与更相减损术创设情
2、景，揭示课题创设情景，揭示课题 问题问题2:2:我们都是利用找公约数的方法来求我们都是利用找公约数的方法来求最大公约数，如果两个数比较大而且根据我最大公约数，如果两个数比较大而且根据我们的观察又不能得到一些公约数，我们又应们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求该怎样求它们的最大公约数？比如求82518251与与61056105的最大公约数的最大公约数?1.1.辗转相除法辗转相除法:例例1 1 求两个正数求两个正数82518251和和61056105的最大公约数。的最大公约数。解：解：82518251610561051 12146;2146;61052146218
3、13;214618131333;18133335148;333148237;1483740.则则3737为为82518251与与61056105的最大公约数。的最大公约数。以上我们求最大公约数的方法就是辗转相以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在除法。也叫欧几里德算法，它是由欧几里德在公元前公元前300300年左右首先提出的。年左右首先提出的。求18与30的最大公约数 解30=181+12 18=121+6 12=62 18与30的最大公约数是6练习 用辗转相除法求下列两个正整数的最大公约数 225 135 98 196 72 168 153 119 答案
4、：45 98 24 17人教A版高中数学必修3第一章 算法案例标准课件人教A版高中数学必修3第一章 算法案例标准课件总结辗转相除法方法 用大数除以小数得到商和余数，接着用除数除以余数得到商和余数，依次计算下去，直到余数为零，最后式子的除数是所求的最大公约数。人教A版高中数学必修3第一章 算法案例标准课件人教A版高中数学必修3第一章 算法案例标准课件2.2.更相减损术更相减损术:我国早期也有解决求最大公约数问题的算我国早期也有解决求最大公约数问题的算法，就是更相减损术。法，就是更相减损术。更相减损术求最大公约数的步骤如下：可更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数
5、，以半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。少减多，更相减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用判断它们是否都是偶数。若是，用2 2约简；若不是，约简；若不是，执行第二步。执行第二步。第二步：以较大的数减去较小的数，接着把第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。（等数）
6、就是所求的最大公约数。人教A版高中数学必修3第一章 算法案例标准课件人教A版高中数学必修3第一章 算法案例标准课件例题 用更相减损术求两个正整数的最大公约数 18与30 解 182=9 302=15 159=6 96=3 63=3 18与30的最大公约数是32=6人教A版高中数学必修3第一章 算法案例标准课件人教A版高中数学必修3第一章 算法案例标准课件例例2 2 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数.解：由于解：由于6363不是偶数，把不是偶数，把9898和和6363以大数以大数减小数，并辗转相减，减小数，并辗转相减，即：即：986335;633528;3
7、5287;28721;21714;1477.所以，所以，9898与与6363的最大公约数是的最大公约数是7 7。练习练习2 2：用更相减损术求两个正数：用更相减损术求两个正数8484与与7272的最大的最大公约数。公约数。(12)(12)人教A版高中数学必修3第一章 算法案例标准课件人教A版高中数学必修3第一章 算法案例标准课件练习 用更相减损术法求下列两个正整数的最大公约数 225 135 98 196 72 168 153 119人教A版高中数学必修3第一章 算法案例标准课件人教A版高中数学必修3第一章 算法案例标准课件 第一步第一步,给定两个正整数给定两个正整数m,n(mm,n(mn)第
8、二步第二步,计算计算m m除以除以n n所得到余数所得到余数r r 第三步第三步,m=n,n=r,m=n,n=r 第四步第四步,若若r=0,r=0,则则m,nm,n的最大公约数等于的最大公约数等于m;m;否则返回第二步否则返回第二步辗转相除法求最大公约数算法步骤：辗转相除法求最大公约数算法步骤：人教A版高中数学必修3第一章 算法案例标准课件人教A版高中数学必修3第一章 算法案例标准课件否否开始开始 输入两个正数输入两个正数m,nr=m MOD nr=0?输出输出m结束结束m=nn=r是是程序框图人教A版高中数学必修3第一章 算法案例标准课件人教A版高中数学必修3第一章 算法案例标准课件小结 1、辗转相除法方法 2、更相减损术的步骤：第一步 任意给定两个正整数，判断它们是不是偶数，若是用2约简，若不是执行第二步，第二步 以较大的数减去较小的数，接着把所得差与较小的数比较，并以大数减小数，继续这个操作，直到所得数相等为止，则这个数或者这个数与约简的数的乘积就是所求的最大公约数。人教A版高中数学必修3第一章 算法案例标准课件人教A版高中数学必修3第一章 算法案例标准课件
