Наибольший общий делитель

Алгоритмизация / Наибольший общий делитель

 

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольшее число, на которое делятся числа m и n. Наибольший общий делитель существует и однозначно определён, если хотя бы одно из чисел m или n не равно нулю.

Алгоритм был придуман Евклидом в Древней Греции более 2000 лет назад и основан на следующем правиле.

Для любых целых чисел x, y > 0 выполняется равенство

НОД (x, y) = НОД (x % y, y)

 
Любое число, которое делит оба числа x и y, делит также и x — y, поэтому

НОД (x, y) ≤ НОД (x — y, y).

 
Аналогично, любое число, которое делит оба числа x − y и y, делит также и их сумму x, поэтому

НОД (x, y) ≥ НОД (x — y, y).

 
Требуемое равенство получается последовательным вычитанием y из x.

Идея алгоритма отыскания наибольшего общего делителя заключается в том, чтобы отнимать от большего меньшее, пока числа не станут равны. Полученное число и является наибольшим общим делителем.

Например, необходимо определить наибольший общий делитель чисел 50 и 20.

  • находим 50-20=30. Из трех чисел 50, 20, 30 отбрасываем наибольшее.
  • находим 30-20=10. Из трех чисел 30, 20, 10 отбрасываем наибольшее.
  • находим 20-10 = 10. Из трех чисел 20, 10, 10 отбрасываем наибольшее.
  • 10=10, значит это число является наибольшим общим делителем исходных.

 
Реализацию указанного алгоритма удобно произвести с использованием рекурсивной процедуры.

 
Реализация на С++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
using namespace std;
// Функция нахождения НОД
int NOD(int n1, int n2)
{
  int div;
  if (n1 == n2)   // если числа равны, НОД найден
    return n1;
  int d = n1 - n2; // Находим разность чисел
  if (d < 0)       // если разность отрицательная,
  {
    d = -d;     // меняем знак
    div = NOD(n1, d); // вызываем функцию NOD() для двух наименьших чисел
  }
  else      // если разность n1-n2 положительная
  {
    div = NOD(n2, d); // вызываем функцию NOD() для двух наименьших чисел
  }
  return div;
}
int main() 
{
  int n1, n2;
  cout << "n1=";
  cin >> n1;
  cout << "n2=";
  cin >> n2;
  cout << NOD(n1, n2);
  cin.get(); cin.get(); return 0;
}


Результат выполнения
Наибольший общий делитель


Назад: Алгоритмизация

Комментариев к записи: 1

  • Не мое, но очень интересное решение))
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include <iostream>
    using namespace std;

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

    int main()
    {
        cout << gcd(10,5);
        return 0;
    }

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *