Найдите свой НОД с помощью РЕКУРСИИ!!!
Наибольший общий делитель (GCD), также называемый наибольшим общим делителем (HCF), определяется как наибольшее положительное целое число, которое делит два целых числа (a, b).
НОД можно вычислить с помощью рекурсии. Алгоритм такой:
1. НОД(a,0) = a, можно остановиться.
2.НОД(a,b) = НОД(b,a mod b), где мод b — это остаток от деления b на a.
Рассмотрим пример. Найти НОД(48,18):
Q — частное, а R — остаток
Шаг-1: НОД(48,18)=> Q=2,R=12
Шаг-2: НОД(18,12)=> Q=1,R=6
Шаг-3: НОД(12,6)=> Q=2,R=0
Шаг 4: НОД(6,0)=6
Таким образом, 6 является НОД 48 и 18.
Реализация алгоритма Евклида на Python выглядит следующим образом:
Почему этот подход работает для нахождения НОД?
Алгоритм Евклида работает на том факте, что если мы попытаемся уменьшить большее число (a, b), вычитая меньшее число из большего , то НОД меньшего числа и результат вычитания будут такими же, как НОД(a,b). Точно так же, если мы попытаемся разделить меньшее число на 0, то алгоритм может быть быстро остановлен.
