为什么我的 C 语言 GCD 程序不是 运行？

Question

我正在尝试使用 C 中的 Euclid 算法（递归地）找到两个数的 GCD，并且我确实知道在数学上它并不完全完美，因为它忽略了负数条件，但我只是希望这个适用于目前为正数。

#include <stdio.h>

int gcd(int m, int n);

int main() {
    return gcd(60, 24);
}

int gcd(int m, int n) {
    if (m < n) {
        //swapping both a and b
        m = m + n;
        n = m - n;
        m = m - n;
    }
    if (m == n) {
        return m;
    } else {
        return gcd(n, m % n);   
    }
}

Answer 1

gcd(60, 24) -> gcd(24, 12) -> gcd(12, 0).

这意味着您需要添加一张支票。

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

或

if ( m%n == 0 )
{
   return n;
}

您还可以通过对函数的另一个调用删除变量交换代码，并在调用中交换值。

int gcd(int m, int n) {

   if (m < n) {
      return gcd(n, m);
   }

   if (m%n == 0) {
      return n;
   } else {
      return gcd(n, m % n);   
   }
}

Answer 2

递归 GCD 的代码如下所示

int gcd(int m, int n)
{
    if (n==0)
        return m;

    return gcd(n, m % n);
}

不需要交换参数，因为这将由递归处理。例如，考虑 gcd(24, 60)。在这种情况下 n=60 和 m % n = 24%60 = 24。所以递归调用是gcd(60,24)，自动交换参数。