Нахождение наименьшего общего кратного (НОК) при помощи рекурсии

Описание задачи

Программа принимает на вход два числа и находит наименьшее общее кратное (НОК) при помощи рекурсии.

Решение задачи

  1. Принимаем два числа и записываем их в отдельные переменные.
  2. Вводим переменную, которая в начале работы функции принимает значение наибольшей из двух переменных.
  3. Проверяем, делится ли без остатка число, содержащееся во вновь введенной переменной, на оба данных нам числа одновременно.
  4. Если делится, то функция прекращает свою работу и выводит это число, которое и будет наименьшим общим кратным (НОК).
  5. Если нет, то опять вызывается эта рекурсивная функция, в которой значение переменной еще раз увеличивается на величину наибольшего из данных в задаче чисел. И так будет повторяться, пока не выполнится условие делимости без остатка на оба числа.
  6. После того как функция завершит свою работу, значение наименьшего общего кратного (НОК) выводится на экран.

Исходный код

Ниже дан исходный код, который осуществляет нахождение наименьшего общего кратного (НОК) с использованием рекурсии. Результаты работы программы также даны ниже.

def lcm(a, b):
    lcm.multiple = lcm.multiple + b
    if ((lcm.multiple % a == 0) and (lcm.multiple % b == 0)):
        return lcm.multiple;
    else:
        lcm(a, b)
    return lcm.multiple
lcm.multiple = 0
a = int(input("Введите первое число:"))
b = int(input("Введите второе число:"))
if (a > b):
    LCM = lcm(b, a)
else:
    LCM = lcm(a, b)
print("НОК:")
print(LCM)

Объяснение работы программы

  1. Пользователь вводит два числа и они записываются в переменные a и b.
  2. Также вводится еще одна переменная, lcm.multiple, которая для начала инициируется нулем.
  3. Далее проверяется, какое из введенных чисел больше, чтобы передать их в рекурсивную функцию lcm() в порядке возрастания.
  4. В функции lcm() на первом шаге значение переменной увеличивается на величину наибольшего из введенных пользователем чисел. То есть при первом вызове функции значение переменной становится равным этому числу.
  5. Затем происходит проверка, делится ли значение переменной lcm.multiple без остатка на оба наших числа одновременно. Если делится, то функция прекращает свою работу и выводит в качестве результата значение переменной lcm.multiple.
  6. Если нет, то опять вызывается рекурсивная функция lcm(), в которой значение переменной lcm.multiple еще раз увеличивается на величину наибольшего из данных в задаче чисел. И так будет повторяться, пока не выполнится условие делимости без остатка на оба числа.
  7. После того как функция завершит свою работу, значение наименьшего общего кратного (НОК) выводится на экран.

Результаты работы программы

Пример 1:
Введите первое число:126
Введите второе число:12
НОК: 
252
 
Пример 2:
Введите первое число:25
Введите второе число:5
НОК: 
25