多个数字的GCD
多个数字的GCD
提问于 2016-07-03 22:04:53
我知道如何编写代码来查找2的GCD数字。然而，我正在尝试解决一个寻找n数的GCD的问题，我认为该算法与使用Eucledian算法略有不同。我的代码可以编译，但它总是给我错误的结果。例如，当我输入n = 2，GCD of 16和12时，结果是8。下面是我的代码：
#include<iostream>
using namespace std;
int main()
{
int a,b[100],c,d,e=0;
cin>>a;
for(c=0 ; c<a ; c++)
{
cin>>b[c];
}
for(c=0 ; c<a-1 ; c++)
{
if(c < 1)
{
d = b[c];
}
if(b[c] < d)
{
d = b[c];
}
}
while(d>0)
{
for(c=0 ; c<a ; c++)
{
if(b[c] % d < 1)
{
e++;
}
}
if(e == c)
{
cout<<d;
break;
}
d--;
}
}你们能帮我找出代码中的错误吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2016-07-03 22:20:15
您的代码不计算输入数组的最大公约数-它计算有多少条目可以被数组中最小的元素d整除，然后有多少条目可以被一个较小的元素整除，依此类推，直到d为0。这与GCD一点关系都没有。
一种简单的方法-尽管不一定是最快的-将基于以下事实:三个数字的GCD必须与其中任何一个数字的GCD相同，而其他两个数字的GCD必须相同。
gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(a, gcd(b, c)) = gcd(gcd(a, c), b)扩展到n个输入是基本的：
int result = a[0];
for (int i = 1; i < a.Length; ++i)
result = gcd(result, a[i]);在网上到处都可以找到两个数字的GCD的代码，例如在Rosetta Code。我最喜欢的是这个简单的迭代版本：
int gcd (int a, int b)
{
while (b)
{
int t = b;
b = a % b;
a = t;
}
return a;
}C#允许更简洁的公式，但在其他语言中可能不起作用(例如，在C++中它会调用未定义的行为)：
static int gcd (int a, int b)
{
while (b != 0)
b = a % (a = b);
return a;
}Stack Overflow用户
发布于 2018-06-05 07:48:32
如果有些人觉得它有帮助，这里是欧几里德算法在JavaScript中的一个实现。
function EuclideanGCD(a, b) {
// Make sure a > b, interchange values
if (a < b) {
c = a;
a = b;
b = c
}
// If A = 0 then GCD(A,B) = B and we can stop.
if (a == 0) {
return b;
// If B = 0 then GCD(A,B) = A and we can stop.
} else if (b == 0) {
return a;
} else {
let gdc = 0;
let quotient = Math.floor(a / b); // Get the divisor
let remainder = a % b; // Get the remainder
// Make a recursive call, till we hit 0
gdc = EuclideanGCD(b, remainder);
return gdc;
}
}
var gcd = EuclideanGCD(234, 357);
console.log(gcd); // Outputs: 3
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/38170726
复制相关文章
相似问题