Question

Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида. Питон, не паскаль. НЕ ПАСКАЛЬ. НЕ. ПАСКАЛЬ

Answer 1

def Euclid(a, b):

   a, b = max(a, b) % min(a, b), min(a, b)

   if a == 0:

       return b

   return Euclid(a, b)

print(Euclid(*map(int, input().split())))

Answer 2

Конечно, вот пример рекурсивной функции на Python для вычисления НОД двух натуральных чисел с использованием модифицированного алгоритма Евклида:

pythonCopy code
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

num1 = int(input("Введите первое натуральное число: "))
num2 = int(input("Введите второе натуральное число: "))

result = gcd(num1, num2)
print("НОД чисел", num1, "и", num2, ":", result)

Вызывая функцию gcd(a, b), она будет рекурсивно вызывать себя с аргументами (b, a % b) до тех пор, пока b не станет равным 0. Когда это произойдет, функция вернет значение a, которое и будет НОД двух чисел.

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