作者hightacps (海獭)
看板tutor
标题Re: [解题] 最大公因数
时间Sat Dec 12 17:48:45 2009
※ 引述《firedduck (New-life)》之铭言：
: 1.年级：高一
: 2.科目：第一章
: 3.章节：数与座标
: 4.题目：a = 1271b+2294
: 则(a,b)=(b,2294)
: 5.想法： b=1, a=1271+2294
: (1271+2294,1) = (1,2294) ?
: 看起来不合理 也不是很懂为什麽
: 麻烦一下各位! 感谢
辗转相除法
举例 ()代表最大公因数
(20,15) = ?
|20 |15 | (20,15) = (5,15)
|15 | | ~~~ 因为20除以15余5
---------
| 5 | |
| | |
|5 |15 | (5,15) = (5,0) = 5
| |15 | ~~因为15除以5余0
----------
| | 0 |
其实只是把直行的辗转相除法变成横向而已
<ex> 求(311467,155683,4951)的最大公因数
<sol> (311467,155683,4951) = (101,155683,4951) <---155683除311467余101
= (101,155683,2) <---101除4951余2
= (1,155683,2) <---2除101余1
= 1
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.204.69.131
1F：推 iamvanson:好像没有解释到原理 12/13 13:44
2F：→ hightacps:原理参考书应该都有 要我把证明过程从参考书复制过来吗 12/13 14:04
3F：推 iamvanson:但他这个问题不是就是要问原理吗 12/13 14:59
4F：→ iamvanson:直式的辗转相除反而是横式的进阶应用 这样解释好像有点 12/13 15:00
5F：→ iamvanson:结果论 12/13 15:00