qq_43412960
2019-10-24 02:21
采纳率: 79.1%
浏览 563

这是一个关于C语言求最大公约数的问题

用辗转除法求最大公约数,他的原理是什么呢。我感觉这个好奇怪,直接两个数相除了。好奇怪的表达方法。求大佬们解答下!

  • 写回答
  • 好问题 提建议
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • 智者知已应修善业 2019-10-24 09:28
    已采纳

    而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。
    《九章算术》应当普及,中国很多好东西缺乏普及.

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • threenewbee 2019-10-24 09:09

    比如计算15和12的GCD,拿15/12=1余数是3,然后12/3=4余数0,所以GCD是3
    再比如,计算28和64的GCD,那么大的除以小的,64/28余数8,28/8余数4,8/4=2,没有余数,所以GCD=4
    你自己体会一下。

    这里有证明:https://baike.baidu.com/item/%E7%A2%BE%E8%BD%AC%E7%9B%B8%E9%99%A4%E6%B3%95/10585976

    评论
    解决 无用
    打赏 举报
  • 安全狐 2019-10-24 11:10

    两个整数的最大公约数是能够同时整除它们的最大的正整数。
    辗转相除法基于如下原理:
    两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为252 − 105 = 147,所以147和105的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数就是两数的最大公约数。由辗转相除法也可以推出,两数的最大公约数可以用两数的整数倍相加来表示,如21 = 5 × 105 + (−2) × 252。这个重要的等式叫做贝祖等式。

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题