Вычисление наибольшего общего делителя двух целых чисел

Напишите программу для вычисления наибольшего общего делителя двух целых чисел. Задачу решим двумя способами: используя оператор repeat, используя оператор while.

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

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

Решение

Воспользуемся так называемым алгоритмом Евклида нахождения НОД, который выведен с помощью математических методов. В самом простейшем случае для заданных чисел m и n он выглядит так:

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

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

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

1) Так как 12 > 8, заменим 12 на 12 − 8 = 4;
2) Так как 8 > 4, заменим 8 на 8 − 4 = 4;
3) 4 = 4, конец.

1 способ

С использованием оператора while.

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

1) Ввод m и n;
2) Запуск цикла с предусловием m < > n. В цикле:
   Если m > n, то переменной m присвоить m − n, иначе переменной n присвоить n − m;
3) Вывод m:

Код:

program nod1;
var
   x, y: integer;
   nod: integer;
begin
   writeln (‘m=’);
   readln (m);
   writeln (‘n=’);
   readln (n);
   while m<>n do
     if m>n then m:=m-n
      else n:=n-m;
     nod:=m;
     writeln(‘НОД = ‘, nod)
end.

2 способ

С использованием оператора repeat.
Код:

program nod2;
var
   x, y: integer;
   nod: integer;
begin
   writeln (‘m=’);
   readln (m);
   writeln (‘n=’);
   readln (n);
   repeat
     if m>n then m:=m-n;
     if m<n then n:=n-m
   until m=n;
   nod:=m;
   writeln(‘НОД = ‘, nod)
end.

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

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

2 × четыре =