2020高中数学 1.3算法案例讲解 新人教A版必修3.doc
版权申诉
199 浏览量
2021-10-12
17:44:32
上传
评论
收藏 85KB DOC 举报
2020 高中数学 1.3 算法案例讲解 新人教 A 版必修 3
在初中，我们已经学过求最大公约数的知识，你能求出 18 与 30 的公约数吗？
我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察
又不能得到一些公约数，我们又应 该怎样求它们的最大公约数？比如求 8251 与 6105 的最
大公约数？这就是我们这一堂课所要探讨的内容。
1.辗转相除法
例 1 求两个正数 8251 和 6105 的最大公约数。
（分析：8251 与 6105 两数都比较大，而且没有明显的公约数，如能把它们都变 小一
点，根据已有的知识即可求出最大公约数）
解：8251＝6105×1＋2146
显然 8251 的最大公约数也必是 2146 的约数，同样 6105 与 2146 的公约数也必是
8251 的约数，所以 8251 与 6105 的最大公约数也是 6105 与 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 年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：
第一步：用较大的数 m 除以较小的数 n 得到一个商 q
0
和一个余数 r
0
；
第二步：若 r
0
＝0，则 n 为 m，n 的最大公约数；若 r
0
≠0，则用除数 n 除以余数 r
0
得
到一个商 q
1
和一个余数 r
1
；
第三步：若 r
1
＝0，则 r
1
为 m，n 的最大公约数；若 r
1
≠0，则用除数 r
0
除以余数 r
1
得
到一个商 q
2
和一个余数 r
2
；
……
依次计算直至 r
n
＝0，此时所得到的 r
n-1
即为所求的最大公约数。
练习：利用辗转相除法求两数 4081 与 20723 的最大公约数（答案：53）
评论0
最新资源