Модуль: (Python) Подпрограммы: процедуры и функции - 2


4. Алгоритм Евклида

☰ Теория

Алгоритм Евклида

Алгоритм Евклида — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида (III век до н. э.), который впервые описал его в VII и X книгах «Начал». Это один из старейших численных алгоритмов, используемых в наше время.

Вспомним математику.

Наибольший общий делитель двух натуральных чисел (НОД) - это самое большое натуральное число, на которое они делятся нацело.

Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так: НОД(12, 18) = 6

В программировании есть несколько реализаций алгоритма Евклида. Приведем описание одной из них в виде блок-схемы.


Попробуйте реализовать данный алгоритм.

Напишите функцию, которая вычисляет НОД двух чисел.


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

Выходные данные
Программа должна вывести одно натуральное число: НОД заданных чисел.

 

Примеры
№ Входные данные Выходные данные
1 14 21 7


Вставьте недостающие фрагменты кода
Python 
a, b = map(int, input().split())
print(NOD(a,b))
     

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

Комментарий учителя

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!