使用Euclid算法查找GCF(GCD)

Question

我正在尝试编写一个函数来查找2个数字的gcd,使用我在这里找到的Euclid算法.

从较大的数字中,尽可能多地减去较小的数字,直到您的数字小于小数字.(或者没有得到否定答案)现在,使用原始的小数字和结果,一个较小的数字,重复该过程.重复此操作直到最后一个结果为零,GCF是倒数第二个小数结果.另请参阅我们的Euclid算法计算器.
示例:找到GCF(18,27)
27 - 18 = 9
18 - 9 = 9
9 - 9 = 0
因此,最大公因子18和27是9,这是我们达到0之前的最小结果.

按照这些说明我写了一个函数:

int hcf(int a, int b)
{
    int small = (a < b)? a : b;
    int big = (a > b)? a : b;
    int res;
    int gcf;

    cout << "small = " << small << "\n";
    cout << "big = " << big << "\n";

    while ((res = big - small) > small && res > 0) {
            cout << "res = " << res << "\n"; 
    }
    while ((gcf = small - res) > 0) {
        cout << "gcf = " << gcf << "\n";
    }


    return gcf;
}

但是,第二个循环似乎是无限的.有谁能解释为什么？

我知道网站实际上显示了代码(PHP),但我正在尝试仅使用它们提供的指令来编写此代码.

Answer 1

当然这个循环是无限的:

while ((gcf = small - res) > 0) {
    cout << "gcf = " << gcf << "\n";
}

small并且res不要在循环中改变,所以gcf也不要改变.该循环相当于:

gcf = small - res;
while (gcf > 0) {
    cout << "gcf = " << gcf << "\n";
}

这可能更清楚.

我会将该算法移植到代码如下:

int gcd(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        }
        else {
            b -= a;
        }
    }
    return a;
}

虽然通常gcd使用mod实现,但它更快:

int gcd(int a, int b) {
    return (b == 0) ? a : gcd(b, a % b);
}