中学联盟山西省霍州市煤电第一中学人教版高中数学必修3课件：1.3算法案例 (共14张PPT).ppt

第一章 算法初步 1.3 算法案例 3 5 9 15 [问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？ 〖创设情景，揭示课题〗 18 30 2 3 ∴18和30的最大公约数是2×3=6. 先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来. 案例1 辗转相除法与更相减损术 〖创设情景，揭示课题〗 [问题2]:我们都是利用找公约数的方法来求 最大公约数，如果两个数比较大而且根据我 们的观察又不能得到一些公约数，我们又应 该怎样求它们的最大公约数？比如求8251与 6105的最大公约数? 1.辗转相除法: 例1 求两个正数8251和6105的最大公约数。 解：8251＝6105×1＋2146; 6105＝2146×2＋1813; 2146＝1813×1＋333; 1813＝333×5＋148; 333＝148×2＋37; 148＝37×4＋0. 则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。 求18与30的最大公约数 解∵30=18×1+12 18=12×1+6 12=6×2 ∴18与30的最大公约数是6 练习 用辗转相除法求下列两个正整数的最大公约数 ①225 135 ②98 196 ③72 168 ④153 119 答案：45 98 24 17 总结辗转相除法方法 用大数除以小数得到商和余数，接着用除数除以余数得到商和余数，依次计算下去，直到余数为零，最后式子的除数是所求的最大公约数。 2.更相减损术: 我国早期也有解决求最大公约数问题的算法，就是更相减损术。 更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。 翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。 例题 用更相减损术求两个正整数的最大公约数 18与30 解 ∵18÷2=9 30÷2=15 15－9=6 9－6=3 6－3=3 ∴18与30的最大公约数是3×2=6 例2 用更相减损术求98与63的最大公约数. 解：由于63不是偶数，把98和63以大数减小数，并辗转相减， 即：98－63＝35; 63－35＝28; 35－28＝7; 28－7＝21; 21－7＝14; 14－7＝7. 所以，98与63的最大公约数是7。 练习2：用更相减损术求两个正数84与72的最大公约数。 (12) 练习 用更相减损术法求下列两个正整数的最大公约数 ①225 135 ②98 196 ③72 168 ④153 119 第一步,给定两个正整数m,n(m＞n) 第二步,计算m除以n所得到余数r 第三步,m=n,n=r 第四步,若r=0,则m,n的最大公约数等于m;否则返回第二步 辗转相除法求最大公约数算法步骤：