Hosted by uCoz

Задача № 22. Найти наибольший общий делитель двух натуральных чисел

Формулировка. Даны два натуральных числа. Найти их наибольший общий делитель.

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

Примечание 2: общим делителем двух натуральных чисел называется натуральное число, на которое натуральное число, которое является делителем обоих этих чисел.

Например, найдем НОД(12, 8):

Выпишем все делители числа 12: 1, 2, 3, 4, 6, 12;

Выпишем все делители числа 8: 1, 2, 4, 8;

Выпишем все общие делители чисел 12 и 8: 1, 2, 4. Из них наибольшее число – 4. Это и есть НОД чисел 12 и 8.

Решение. Конечно, при решении мы не будем выписывать делители и выбирать нужный. В принципе, ее можно было бы решить как задачу 15, начав цикл с наименьшего из двух заданных чисел (так как оно тоже может быть НОД, например, НОД(12, 4) = 4). Но мы воспользуемся так называемым алгоритмом Евклида нахождения НОД, который выведен с помощью математических методов. В самом простейшем случае для заданных чисел m и n он выглядит так:

1)          Если m неравно n, перейти к шагу 2, в противном случае вывести m и закончить алгоритм;

2)          Если m > n, заменить m на mn, в противном случае заменить n на nm;

3)          Перейти на шаг 1

Как видим, в шаге 2 большее из двух текущих чисел заменяется разностью большего и меньшего.

Приведем пример для чисел 12 и 8:

a.      Так как 12 > 8, заменим 12 на 12 – 8 = 4;

b.     Так как 8 > 4, заменим 8 на 8 – 4 = 4;

c.      4 = 4, конец.

Не проводя каких-либо рассуждений над алгоритмом и не доказывая его корректности, переведем его описание в более близкую для языка Pascal форму:

Алгоритм на естественном языке:

1)      Ввод m и n;

2)      Запуск цикла с предусловием m < > n. В цикле:

                                1.        Если m > n, то переменной m присвоить mn, иначе переменной n присвоить nm;

3)      Вывод m:

Код:

  1. program GreatestCommonDiv;
  2. var
  3. m, n: word;
  4. begin
  5. readln(m, n);
  6. while m <> n do begin
  7. if m > n then begin
  8. m := m - n
  9. end
  10. else begin
  11. n := n - m
  12. end
  13. end;
  14. writeln(m)
  15. end.