Knuth 的编程艺术第三版和欧几里德算法示例

Question

我刚刚开始阅读 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;
}

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

Answer 1

这是一个 GCD 函数的例子

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

数字是119和544

Answer 2

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

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

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

  return b;
}

Knuth 的编程艺术第三版和欧几里德算法示例

Knuth's Art of Programming Third Edition and the Euclidean algorithm example

c

algorithm

knuth