Cel mai mare divizor comun


<< înapoi


Un număr întreg d se numeşte cel mai mare divizor comun a numerelor întregi a şi b dacă şi numai dacă pentru orice divizor comun c al lui a şi b, d este un divizor al lui c.
În cazul în care impunem condiţia d > 0 este relativ simplu de verificat dacă d este unic. Acest număr se notează cu c.m.m.d.c(a,b), sau mai simplu: (a,b).
Folosind principiul bunei ordonări a numerelor naturale, putem deduce că c.m.m.d.c(a,b) este cel mai mic număr pozitiv care poate fi scris ca o combinaţie liniară a lui a şi b, adică cel mai mic număr natural de forma a * x + b * y, unde x,y sunt numere întregi.


Cerinta:
Sa se determine cel mai mare divizor comun din elementele unui vector. Nota: rezolvare cu fisiere.

Implementare c++


#include <fstream>
using namespace std;
ifstream f("date.in");
ofstream g("date.out");
int cmmdc(int a, int b)
{
while(a!=b)
{
if(a>b)
a-=b;
else
b-=a;
}
return a;
}
int main()
{
int i,n, *a,b;
ifstream f("date.in");
ofstream g("date.out");
f>>n;
a = new int[n];
for(i=0;i<n;i++)
{
g << "a[" << i << "]:"; f>> a[i];
}
for(i=1;i<n;i++)
if(i == 1)
b = cmmdc(a[i-1],a[i]);
else
b = cmmdc(b,a[i]);
g << b;
f.close();
g.close();
return 0;
}