Модифицированный алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так: нужно заменять большее число на остаток от деления большего на меньшее до тех пор, пока остаток не станет равно нулю; тогда второе число и есть НОД. Напишите программу, которая реализует этот алгоритм.

Входные данные:

Входная строка содержит два числа, разделённые пробелом - a и b.

Выходные данные:

Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем - количество шагов цикла, которые были выполнены.

Примеры:

Входные данные:

21 14

Выходные данные:

7 2

Входные данные:

121 136

Выходные данные:

1 3

Question

Информатика

Мавра

29 апреля, 22:46

Модифицированный алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так: нужно заменять большее число на остаток от деления большего на меньшее до тех пор, пока остаток не станет равно нулю; тогда второе число и есть НОД. Напишите программу, которая реализует этот алгоритм.

Входные данные:

Входная строка содержит два числа, разделённые пробелом - a и b.

Выходные данные:

Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем - количество шагов цикла, которые были выполнены.

Примеры:

Входные данные:

21 14

Выходные данные:

7 2

Входные данные:

121 136

Выходные данные:

1 3

+3

Ответы (1)

Знаете ответ на вопрос?

Анатольич · Answer 1

Var a, b, nod, k:integer;

begin

readln (a, b) ;

k:=0;

while (a0) and (b0) 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