我的GCD算法有什么问题?

Question

下面是我计算两个输入数字的GCD的尝试:

int rep;
do{
    system ("cls");
    int a, b, gcd=2, e, d;
    cin >> a >> b;
    if(a % b != 0 || b % a != 0){
        do{
            gcd = gcd + 1;
            d = a % gcd;
            e = b % gcd;        
        } while(d==0 && e==0);
        cout << gcd-1;
    }else if(a == 1 || b == 1){
        gcd=1;
        cout << gcd;
    }else if(a >= b){
        gcd = a;
        cout << gcd;
    }else if(b >= a){
        gcd = b;
        cout << gcd;
    }
    cin >> rep;
} while(rep == 1);

如果我输入8和24，它会给我2作为答案。有人能指出我代码中的问题吗?

Answer 1

问题是该算法在第一次测试GCD失败时放弃。在大多数情况下，找到最大的意味着要越过一些不起作用的值。在这种情况下，工作到8意味着超过3,5和7。

8 % 24 == 8。所以do循环至少运行一次。gcd变成3并被检验，但没有被平均分成8，因此while条件判定为假。然后3 - 1(2)流到cout。但这不是正确的GCD。

你可以修改你的算法，从两个输入中较小的一个开始，然后向下工作，直到成功(这里是8)，然后失败(这里是7)。

Answer 2

这里GCD算法的核心部分只有3行，其余部分用于防止愚蠢。

#include <stdio.h>
unsigned GCD(unsigned x, unsigned y) {
    unsigned z;
    if (x < y) {
        z = x;                  // swap
        x = y;
        y = z;
    }
    if (y == 0)
        return 0;
    while (z = x % y) {         // perform the GCD with implicit 0 test
        x = y;
        y = z;
    }
    return y;
}
int main(void)
{
    printf("GCD of %u, %u = %un", 1, 0, GCD(1, 0));    // billed as C
    printf("GCD of %u, %u = %un", 0, 1, GCD(0, 1));
    printf("GCD of %u, %u = %un", 1, 1, GCD(1, 1));
    printf("GCD of %u, %u = %un", 8, 24, GCD(8, 24));
    return 0;
}

程序输出:

GCD of 1, 0 = 0
GCD of 0, 1 = 0
GCD of 1, 1 = 1
GCD of 8, 24 = 8