Program C++ do obliczenia największego wspólnego dzielnika

Question

Uruchomiłem ten program, aby obliczyć największy wspólny dzielnik. Oto, co mam do tej pory:

#include <iostream> 
#include <math.h> 
using namespace std; 
int getGCD(int a, int b) 
{ 
    a = a % b; 
    if (a == 0) 
    { 
     return b; 
     b = b % a; 
    } 
    if (b == 0) 
    { 
     return a; 
    } 
} 
int main() 

{ 
    int x, y; 
    cout << "Please enter two integers x and y, for GCD calculation" << endl; 
    cin >> x >> y; 
    cout << "The GCD of " << x << "and " << y << " is" << getGCD(x, y) << endl; 
    return 0; 
} 

Zawsze otrzymuję 0 dla GCD. Co ja robię źle?

Answer 1

Powinieneś być w pętli, aby to znaleźć, i może ci to pomóc, jeśli zastosujesz algorytm, w jaki sposób to zadziała, z pewnymi równaniami.

Ale widzisz dwa problemy, chyba że wywołasz to w innej pętli.

Powracasz w obu przypadkach, albo jeśli, albo inaczej, więc przechodzisz tutaj tylko raz.

Ta część nie ma sensu, po co modyfikować wartość b po wykonaniu return?

  return b; 

      b = b%a; 

Powinieneś używać rekursji do tego, przy okazji.

http://rosettacode.org/wiki/Greatest_common_divisor#Recursive_Euclid_algorithm

Answer 2

int getGCD(int a, int b) { 

// tutaj musimy sprawdzić, czy b == 0 zamian implementacji

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

Algorytm Euklidesa