Programma C++ per calcolare il massimo comun divisore

Question

Ho iniziato questo programma per calcolare il massimo comun divisore. Questo è quello che ho finora:

#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; 
} 

ho sempre ottenere un 0 per il GCD. Che cosa sto facendo di sbagliato?

Answer 1

Si dovrebbe essere in loop per trovare questo, e può aiutare se si mette, con alcune equazioni, il proprio algoritmo per come dovrebbe funzionare.

Ma si riscontrano due problemi, a meno che non lo si chiami all'interno di un altro ciclo.

Si sta tornando in entrambi i casi, l'if o, quindi si passa solo qui una volta.

Inoltre, questa parte non ha senso, perché modificare il valore b dopo aver eseguito uno return?

  return b; 

      b = b%a; 

Si dovrebbe usare la ricorsione per questo, btw.

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

Answer 2

int getGCD(int a, int b) { 

// qui abbiamo bisogno di controllare se b == 0 il ritorno di un Attuazione

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

algoritmo di Euclide