Chương trình C++ để tính ước số chung lớn nhất

Question

Tôi đã bắt đầu chương trình này để tính ước số chung lớn nhất. Đây là những gì tôi có cho đến thời điểm này:

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

Tôi luôn nhận được 0 cho GCD. Tôi đang làm gì sai?

Answer 1

Bạn nên lặp lại để tìm điều này và có thể hữu ích nếu bạn đặt, với một số phương trình, thuật toán của bạn về cách thức hoạt động của tính năng này.

Nhưng bạn có hai vấn đề tôi thấy, trừ khi bạn đang gọi điều này bên trong vòng lặp khác.

Bạn đang quay trở lại trong cả hai trường hợp, nếu là hoặc nếu không, vì vậy bạn chỉ đi qua đây một lần.

Ngoài ra, phần này không có ý nghĩa, tại sao sửa đổi giá trị b sau khi thực hiện return?

  return b; 

      b = b%a; 

Bạn nên sử dụng đệ quy cho điều này, btw.

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

Answer 2

int getGCD(int a, int b) { 

// ở đây chúng ta cần phải kiểm tra xem b == 0 trở lại một thi

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

Euclid Thuật toán