Главная
>>
Каталог задач
>>
Математика
>>
Наибольший общий делитель
Наибольший общий делитель
реализации: C++, количество: 5
Aвтор: this
Дата: 10.07.2003
Просмотров: 42621
Рейтинг:
7/6,4.94(1329)
+
реализации(исходники)
+добавить
Нахождение наибольшего общего делителя 2-х чисел.
Алгоритм Евклида
Медленный но верный алгоритм:
while (i != j)
if (i > j)
i -= j
else
j -= i
return i
Реализации:
C#(3),
C++(5),
pascal(1),
java(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;
printf("BBEDIT6 2 4isla : ");
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;
}
