1:3算法案例
案例1辗转相除法与更相减损术
案例1 辗转相除法与更相减损术
〖创设情景,揭示课题〗 [问题1:在小学,我们已经学过求最大公约数 的知识,你能求出18与30的最大公约数吗? 21830 先用两个数公有的质因数 3915 连续去除一直除到所得 35 18和30的最大公约的商是互质数为止然后 数是2×3=6 把所有的除数连乘起来 [问题2]:我们都是利用找公约数的方法来求最大 公约数,如果公约数比较大而且根据我们的观察 又不能得到一些公约数,我们又应该怎样求它们 的最大公约数?比如求8251与6105的最大公约数?
3 5 9 15 [问题1]：在小学，我们已经学过求最大公约数 的知识，你能求出18与30的最大公约数吗？ 〖创设情景，揭示课题〗 2 18 30 3 ∴18和30的最大公约 数是2×3=6. 先用两个数公有的质因数 连续去除,一直除到所得 的商是互质数为止,然后 把所有的除数连乘起来. [问题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年左右首先提出的