25

我正在编写一个混合数字类，需要一个快速简单的“最大公约数”函数。谁能给我代码或代码链接？

4

5 回答 5

57

libstdc++ 算法库有一个隐藏的 gcd 函数（我使用的是 g++ 4.6.3）。

#include <iostream>
#include <algorithm>

int main()
{
  cout << std::__gcd(100,24);
  return 0;
}

不客气 ：）

更新：正如@chema989 所指出的，在 C++17 中，头文件std::gcd()提供了可用的功能。<numeric>

于 2013-12-18T17:05:28.200 回答
43

我很想投票结束——似乎很难相信很难找到一个实现，但谁知道呢。

template <typename Number>
Number GCD(Number u, Number v) {
    while (v != 0) {
        Number r = u % v;
        u = v;
        v = r;
    }
    return u;
}

在 C++ 17 或更高版本中，您可以#include <numeric>使用 , 和使用std::gcd（如果您关心 gcd，那么您很有可能也会对std::lcm添加的内容感兴趣）。

于 2012-06-08T22:10:37.783 回答
19

快速递归版本：

unsigned int gcd (unsigned int n1, unsigned int n2) {
    return (n2 == 0) ? n1 : gcd (n2, n1 % n2);
}

或等效的迭代版本，如果您强烈反对递归(a)：

unsigned int gcd (unsigned int n1, unsigned int n2) {
    unsigned int tmp;
    while (n2 != 0) {
        tmp = n1;
        n1 = n2;
        n2 = tmp % n2;
    }
    return n1;
}

只需用您自己的数据类型、零比较、赋值和取模方法替换（例如，如果您使用一些非基本类型bignum，例如类）。

这个函数实际上来自我的一个较早的答案，用于计算屏幕尺寸的整数纵横比，但原始来源是我很久以前学习的欧几里得算法，如果你想知道它背后的数学，请在 Wikipedia 上详细说明。

(a)一些递归解决方案的问题在于，它们接近答案的速度如此之慢，以至于在到达那里之前往往会用完堆栈空间，例如经过深思熟虑的想法（伪代码）：

def sum (a:unsigned, b:unsigned):
    if b == 0: return a
    return sum (a + 1, b - 1)

sum (1, 1000000000)当您（尝试）使用十亿左右的堆栈帧时，您会发现这非常昂贵。递归的理想用例类似于二进制搜索，每次迭代将解决方案空间减少一半。最大公约数也是解决方案空间迅速减少的公约数，因此对大量堆栈使用的担忧是没有根据的。

于 2012-06-08T22:13:51.273 回答
8

对于 C++17，您可以使用std::gcd在 header 中定义<numeric>：

auto res = std::gcd(10, 20);
于 2017-04-28T23:54:53.117 回答
6

欧几里得算法很容易用 C 语言编写。

int gcd(int a, int b) {
  while (b != 0)  {
    int t = b;
    b = a % b;
    a = t;
  }
  return a;
}
于 2012-06-08T22:16:25.873 回答