Модифицированный алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так: нужно заменять большее число на остаток от деления большего на меньшее до тех пор, пока остаток не станет равно нулю; тогда второе число и есть НОД. Напишите программу, которая реализует этот алгоритм.
Входные данные:
Входная строка содержит два числа, разделённые пробелом – a и b .
Выходные данные:
Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем – количество шагов цикла, которые были выполнены.
Примеры:
Входные данные:
21 14
Выходные данные:
7 2
Входные данные:
121 136
Выходные данные:
1 3
Var a,b,nod,k:integer;
begin
readln(a,b);
k:=0;
while (a<>0)and(b<>0) do
begin
if a>b then a:=a mod b else b:=b mod a;
k:=k+1;
end;
nod:=a+b;
writeln(nod, ,k);
end.
Пример:
21 14
7 2
Оцени ответ
Подпишись на наш канал в телеграм. Там мы даём ещё больше полезной информации для школьников!
