Главная
>>
Каталог задач
>>
Математика
>>
Наибольший общий делитель
Наибольший общий делитель
реализации: C++, количество: 6
Aвтор: this
Дата: 10.07.2003
Просмотров: 133457
Рейтинг:
3/7,4.93(3619)
+
реализации(исходники)
+добавить
Нахождение наибольшего общего делителя 2-х чисел.
Алгоритм Евклида
Медленный но верный алгоритм:
while (i != j)
if (i > j)
i -= j
else
j -= i
return i
Реализации:
C#(3),
C++(6),
pascal(1),
java(2),
C(1)
+добавить реализацию
1)
Рекурсивный алгоритм Евклида, code #562[автор:-]
int gcd(int x, int y)
{
if (y == 0)
return x;
return gcd(y, x % y);
}
2)
Евклид, быстрый вариант, code #572[автор:-]
int GCD(int i, int j)
{
while(i&&j)
{
if(i<j)
j%=i;
else
i%=j;
}
return i|j;
}
3)
Алгоритм Евклида (нахождение НОД), code #611[аноним:Анка]
int gcd ( int n, int m ){
if(n==m)
return n ;
if (n<m)
return gcd(n,m-n );
return gcd(n-m,m );
}
4)
FEDORHUK DIMA REALISATION CODE Алгоритм Евкліда, code #618[аноним:FEDORHUK DIMA]
#include <stdio.h>
#include <conio.h>
int gcd(int n, int m)
{if (m == 0)
return n;
return gcd(m, n % m);
}
main()
{ int n,m,nsd;
scanf("%d%d",&n,&m);
nsd=gcd(n,m);
printf("NAYBILSHUY SPILNUY DILNUK = %d and %d is %d",n,m,nsd
);
getch();
return 0;
}
// 30 і 18.
//30 - 18 = 12
///18 - 12 = 6
///12 - 6 = 6
////6 – 6 = 0 stop
//(30, 18) = 6
5)
Правильнее будет деление по модулю, code #621[автор:-]
int nod(int a, int b)
{
while (a!=0 && b!=0)
{
if(a>b) a = a%b; // a %= b; - деление по модулю
else b = b%a; // b %= a;
}
return a+b;
}
6)
assd, code #643[автор:-]
#include <iostream>
using namespace std;
int gcd(int x, int y)
{
if (y == 0)
return x;
return gcd(y, x % y);
}
int main ()
{
int a,b;
cin>>a>>b;
cout<<gcd(a,b);
return 0;
}
