使用Euclid算法查找GCF(GCD) [英] Using Euclid Algorithm to find GCF(GCD)
问题描述
我正在尝试使用Euclid算法(我发现在此。
I am trying to write a function to find the gcd of 2 numbers, using Euclid's Algorithm which I found here.
从较大的数字中减去尽可能小的数字,直到得到一个小于小数的数字。 (或没有得到否定的答案)现在,使用原始的小数字和结果(小数字)重复该过程。重复此过程,直到最后一个结果为零,并且GCF是倒数第二个小数结果。另请参见我们的Euclid算法计算器。
示例:找到GCF(18,27)
27-18 = 9
18-9 = 9
9-9 = 0
因此,18和27的最大公因数是9,在达到0之前我们得到的最小结果。
From the larger number, subtract the smaller number as many times as you can until you have a number that is smaller than the small number. (or without getting a negative answer) Now, using the original small number and the result, a smaller number, repeat the process. Repeat this until the last result is zero, and the GCF is the next-to-last small number result. Also see our Euclid's Algorithm Calculator.
Example: Find the GCF (18, 27)
27 - 18 = 9
18 - 9 = 9
9 - 9 = 0
So, the greatest common factor of 18 and 27 is 9, the smallest result we had before we reached 0.
按照以下说明,我编写了一个函数:
Following these instructions I wrote a function:
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;
}
但是,第二个循环似乎是无限的。谁能解释为什么?
However, the second loop seems to be infinite. Can anyone explain why?
我知道网站实际上显示了代码(PHP),但是我试图仅使用他们给出的说明来编写此代码。
I know the website actually shows the code(PHP), but I'm trying to write this code using only the instructions they give.
推荐答案
当然,此循环是无限的:
Of course this loop is infinite:
while ((gcf = small - res) > 0) {
cout << "gcf = " << gcf << "\n";
}
small
和 res
不会在循环中更改,因此 gcf
也不会更改。该循环等效于:
small
and res
don't change in the loop, so gcf
doesn't either. That loop is equivalent to:
gcf = small - res;
while (gcf > 0) {
cout << "gcf = " << gcf << "\n";
}
这可能更清楚。
我会将该算法移植为以下代码:
I would port that algorithm to code as follows:
int gcd(int a, int b) {
while (a != b) {
if (a > b) {
a -= b;
}
else {
b -= a;
}
}
return a;
}
虽然通常是 gcd
是使用mod来实现的,因为它要快得多:
Although typically gcd
is implemented using mod, since it's much faster:
int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
这篇关于使用Euclid算法查找GCF(GCD)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!