Question

Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида. Пример: Введите два натуральных числа: 7006652 112307574 НОД(7006652,112307574)=1234. Помогите пожалуйста

Answer 1

// PascalABC.NET 3.2, сборка 1385 от 14.02.2017

function Nod(a,b:integer):integer;
begin
  if b=0 then Result:=a
  else Result:=Nod(b,a mod b)
end;

begin
  var a,b:integer; Read(a,b);
  Writeln(Nod(a,b))
end.

Answer 2

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

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

# Пример использования функции
num1 = int(input("Введите первое натуральное число: "))
num2 = int(input("Введите второе натуральное число: "))

gcd = modified_euclidean_algorithm(num1, num2)
print(f"НОД({num1}, {num2}) = {gcd}")

После запуска программы вы можете ввести два натуральных числа, например, 7006652 и 112307574, и она выведет результат: "НОД(7006652, 112307574) = 1234".