Олимпиадный тренинг

Задача . Алгоритм Евклида (Python)


Задача

Темы:
Дональд Кнут, автор трактата “Искусство программирования”, считает алгоритм Евклида первым в истории. Потому что, не смотря на то, что алгоритм был придуман и использовался еще до Евклида, который жил в IV-III вв. до нашей эры (он упоминается уже у Аристотеля, жившего веком ранее), Евклид описывает процесс итеративно, что согласуется с современным значением слова "алгоритм".

"Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД."

Сам же алгоритм Евклида знаком любым современным школьникам. Математическое описание можно посмотреть здесь.  Реализуйте классический алгоритм Евклида и оформите его в виде функции nod(a, b), которая принимает на вход 2 числа и возвращает наибольший общий делитель двух этих чисел.

Ничего вводить и выводить не нужно! Вам необходимо только реализовать функцию.

 

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python450
Комментарий учителя