Напишите программу для вычисления наибольшего общего делителя двух целых чисел. Задачу решим двумя способами: используя оператор 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.