Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиПоискОблакоVK ComboВсе проекты

Алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так... Python!!!!

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

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

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

Примеры
входные данные
14 21
выходные данные
7 3
_______________________
входные данные
171 3534
выходные данные
57 23
Голосование за лучший ответ
Андрей Высший разум (242293) 2 месяца назад
Вообще-то в Python уже есть встроенная реализация:
 import math
print(math.gcd(*map(int, input().split())))
Но если надо вручную, то:
 def gcd(a, b): return gcd(b, a % b) if b else a
print(gcd(*map(int, input().split())))
И, да - это именно алгоритм Евклида: нормальная реализация через нормальный остаток от деления, а не через кучу бессмысленную вычитаний ради получения этого остатка.

С кол-вом гипотетических итераций:
 def gcd(a, b, c = 0): return gcd(b, a % b, c + a // b) if b else [a, c] 
print(*gcd(*map(int, input().split())))
Похожие вопросы