-4

我刚开始阅读 Knuth 的编程艺术的第 1 卷，然后到了第 4 页上他描述欧几里得算法的部分。他陈述了求两个数的最大公约数的步骤。你可以在这里阅读更多关于它的信息https://en.wikipedia.org/wiki/Euclidean_algorithm

他逐步介绍了一个找到 199 和 544 的 GCD 的示例，他说 17 作为答案。我很快就实现了算法，但得到了答案 1。使用我的计算器，我也得到了答案 1。

我的代码是。

#import <math.h>
#import <stdio.h>

double GreatestComminDivisor(int m, int n) {

    double r = fmod(m, n);
    if (m < n) {
        int temp = n;
        n = m;
        m = temp;
    }

    while (r != 0) {
        r = fmod(m, n);

        if (r == 0) {
            return n;
        }

        m = n;
        n = r;
    }

    return n;
}

int main(int argc, char const *argv[]) {

  int m = 199;
  int n = 544;
  double answer = GreatestComminDivisor(m, n);

  printf("GCD of %i and %i is %f \n", m, n, answer);

  return 0;
}

我是否在他的示例中遗漏了一些东西，他是否得到了错误的答案。我试图查找本书第三版的勘误表，但没有得到任何结果。只是想确保我不会发疯。

4

2 回答 2

2

这是 GCD 函数的示例

int gcd( int a, int b )
{
    if ( b == 0 )
        return( a );
    else
        return( gcd( b, a % b ) );
}

数字是119和544。

于 2015-08-18T06:49:26.113 回答
1

基于已接受答案的无递归算法：

int gcd (int a, int b)
{
  int mod;

  while((mod = a % b) != 0)
  {
    a = b;
    b = mod;
  }

  return b;
}
于 2015-08-18T12:59:55.573 回答