GCD от множествено число - c ++

Знам как да напиша код за намиране на GCD от 2 номера. Въпреки това, аз се опитвам да реша проблема с намирането на GCD на п номер и мисля, че алгоритъмът е малко по-различен от използването на Eucledian алгоритъм. Моят код може да се компилира, но винаги ми дава грешен резултат. Например, когато сложа п = 2 , GCD на 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--;
}
}

Може ли момчета да намерите грешката в моя код?

Отговори:

Вашият код не изчислява най-големия общделител на входния масив - брои колко от тях са равномерно делими от най-малкия елемент d на масива, след това колко са делими на един по-малък и т.н. изобщо.

Един лесен начин - макар и не непременно най-бързият - ще се основава на факта, че 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, Едно от любимите ми е тази обикновена итеративна версия:

int gcd (int a, int b)
{
while (b)
{
int t = b;
b = a % b;
a = b;
}

return a;
}

C # позволява по-кратка формулировка, но на други езици това вероятно няма да работи (например в C ++ това ще доведе до неопределено поведение):

static int gcd (int a, int b)
{
while (b != 0)
b = a % (a = b);

return a;
}

В случай, че някои намират за полезно, тук е реализация на евклидовия алгоритъм в 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