遞歸GCD邏輯錯誤

據我可以告訴邏輯在這是有道理的。然而，輸出是不正確的，我似乎可以理解它。遞歸GCD邏輯錯誤

#include <stdio.h> 

int gcd(int, int); 

int main() 
{ 
    int n, m; 

    printf("enter two numbers"); 
    scanf("%d%d", &n, &m); 

    printf("The gcd of %d and %d is: %d \n", n, m, gcd(n,m)); 

    return 0; 
} 

int gcd(int x, int y) 
{ 
    while(x!=y){ 
      if(x>y) 
        return (x-y,y); 

      else 
        return(x,y-x); 
    } 
    return x; 
}

來源

2014-01-20 Bradg89

這不是一個遞歸實施gcd，除了它的使用while循環功能不自稱和。一個真正的遞歸方法看起來就像這樣：

int gcd(int x, int y) { 
    if (y == 0) 
     return x; 
    else 
     return gcd(y, x % y); 
}

或者短一點：

int gcd(int x, int y) { 
    return y == 0 ? x : gcd(y, x % y); 
}

以上實現基於歐幾里得算法，是指this瞭解更多詳情。

來源

2014-01-21 00:03:43

它可以寫另一種方式，而不使用？ b：c – Bradg89

當然，'？：'是'if-else'的縮寫。看到我更新的答案。 –

這真棒謝謝。 – Bradg89

return (x-y,y);

將簡單地返回y。該代碼編譯，但可能不是你所期望的。

非遞歸歐幾里得GCD算法是這樣的：

int gcd (int x, int y) 
{ 
    while (y != 0) 
    { 
     int r = x % y; 
     x = y; 
     y = r; 
    } 
    return x; 
}

用遞歸版本相比：

int gcd (int x, int y) 
{ 
    return y == 0 ? x : gcd (y, x%y); 
}

一如往常，在這些瑣碎的例子中，遞歸方法使用較少的源代碼但效率不高。的x和y加上返回地址

副本被傳遞到堆棧，而線性版本簡單地與用於的x/y其餘一箇中間變量r工作。

即使一些編譯器可能足夠聰明以檢測不必要的遞歸併優化它，我認爲理解遞歸編碼的固有成本是有用的。

來源

2014-01-21 00:22:07

遞歸GCD邏輯錯誤

回答

相關問題