1.3算法案例
1.3 算法案例
案例1辗转相除法与更相减损术 [问题1:在小学,我们已经学过求最大公约数 的知识,你能求出18与30的最大公约数吗? 21830 <? 915 5 18和30的最大公约数是2×3=6 先用两个数公有的质因数连续去除,一直除到所 得的商是互质数为止然后把所有的除数连乘起 来
3 5 9 15 [问题1]：在小学，我们已经学过求最大公约数 的知识，你能求出18与30的最大公约数吗？ 2 18 30 3 ∴18和30的最大公约数是2×3=6. 先用两个数公有的质因数连续去除,一直除到所 得的商是互质数为止,然后把所有的除数连乘起 来. 案例1 辗转相除法与更相减损术
[问题2]:我们都是利用找公约数的方法来求 最大公约数,如果两个数比较大而且根据我 们的观察又不能得到一些公约数,我们又应 该怎样求它们的最大公约数?比如求8251与 6105的最大公约数?
[问题2]:我们都是利用找公约数的方法来求 最大公约数，如果两个数比较大而且根据我 们的观察又不能得到一些公约数，我们又应 该怎样求它们的最大公约数？比如求8251与 6105的最大公约数?
〖研探新知〗 1.辗转相除法: 例1求两个正数8251和6105的最大公约数。 分析:8251与6105两数都比较大,而且没 有明显的公约数,如能把它们都变小一点,根 据已有的知识即可求出最大公约数 解:8251=6105×1+2146 显然8251与6105的最大公约数也必是2146 的约数,同样6105与2146的公约数也必是8251 的约数,所以8251与6105的最大公约数也是 6105与2146的最大公约数
〖研探新知〗 1.辗转相除法: 例1 求两个正数8251和6105的最大公约数。 分析：8251与6105两数都比较大，而且没 有明显的公约数，如能把它们都变小一点，根 据已有的知识即可求出最大公约数. 解：8251＝6105×1＋2146 显然8251与6105的最大公约数也必是2146 的约数，同样6105与2146的公约数也必是8251 的约数，所以8251与6105的最大公约数也是 6105与2146的最大公约数
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年左右首先提出的
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年左右首先提出的