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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
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 можно сократить следующим образом.

1
2
3
4
int gcd (int a, int b)
{
    return b ? gcd (b, a % b) : a;
}

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

1
2
3
4
5
6
7
8
9
10
int gcd (int a, int b)
{
    while (b)
    {
        a %= b;
        swap (a, b);
    }

    return a;
}
  • Infinity

    Спасибо!

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

  • на Delphi

  • на Java

  • на C++