Алгоритм Евклида нахождения НОД двух чисел (реализация на C++)

C++   2 февраля 2012  Автор статьи:  

Приведем реализацию алгоритма Евклида нахождения наибольшего общего делителя двух целых неотрицательных чисел. В качестве аргументов функции gcd передаются 2 числа, в качестве результата она возвращает их НОД. Вычисления производятся с типом данных int (при необходимости, разумеется, можно заменить его на любой другой целочисленный).


#include
using namespace std;

int gcd (int a, int b)
{
if (b == 0)
{
return a;
}
else
{
return gcd (b, a % b);
}
}

int main()
{
int a, b;
cin >> a >> b;

cout << gcd (a, b) << endl; return 0; }

Засчет того, что в C++ имеется тернарный условный оператор, функцию gcd можно сократить следующим образом.


int gcd (int a, int b)
{
return b ? gcd (b, a % b) : a;
}

Очевидно, функцию gcd можно вычислять нерекурсивно, используя следующий код.

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

return a;
}

  • Infinity

    Спасибо!

Научиться программировать

  • на Delphi

  • на Java

  • на C++