Модифицированный алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так: нужно заменять большее число на остаток от деления большего на меньшее до тех пор, пока остаток не станет равно нулю; тогда второе число и есть НОД. Напишите программу, которая реализует этот алгоритм. Входные данные: Входная строка содержит два числа, разделённые пробелом – a и b. Выходные данные: Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем – количество шагов цикла, которые были выполнены. Примеры: Входные данные: 21 14 Выходные данные: 7 2 Входные данные: 121 136 Выходные данные: 1 3

Для реализации модифицированного алгоритма Евклида на Python, нужно выполнить следующее:

1. Читаем два числа a и b.

2. Применяем алгоритм Евклида: заменяем большее число на остаток от деления большего на меньшее до тех пор, пока остаток не станет равным нулю.

3. Считаем количество шагов, которое требуется для выполнения алгоритма.

4. Выводим наибольший общий делитель (НОД) и количество шагов.

Пример программы:

python
Копировать
def gcd(a, b):
    steps = 0
    while b != 0:
        a, b = b, a % b
        steps += 1
    return a, steps
# Ввод данных
a, b = map(int, input().split())
# Вывод результата
result, steps = gcd(a, b)
print(result, steps)

Как работает программа:

1. Функция gcd принимает два числа a и b.

2. В цикле while b != 0 выполняется шаг алгоритма Евклида: большее число заменяется на остаток от деления. Каждый шаг цикла увеличивает счетчик steps.

3. Когда остаток от деления становится равным нулю, алгоритм завершен, и мы возвращаем НОД (это значение a) и количество шагов.

4. В главной программе мы получаем два числа, передаем их в функцию и выводим результат.

Примеры:

Пример 1:
Входные данные:

Копировать
21 14

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

Копировать
7 2

Пример 2:
Входные данные:

Копировать
121 136

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

Копировать
1 3