Программирование на Python. Перебор делителей. Поиск НОД и НОК | ЕГЭ 2022
1
2
Что такое наименьшее общее кратное (НОК). Алгоритм для нахождения НОК. Примеры нахождения НОК
3
52мин
решение
PythonВыделить код | ||
|
https://www.cyberforum.ru/python-beginners/thread2591477.html
3
Нахождение наименьшего общего кратного (НОК) при помощи рекурсии
Описание задачи
Программа принимает на вход два числа и находит наименьшее общее кратное (НОК) при помощи рекурсии.
Решение задачи
- Принимаем два числа и записываем их в отдельные переменные.
- Вводим переменную, которая в начале работы функции принимает значение наибольшей из двух переменных.
- Проверяем, делится ли без остатка число, содержащееся во вновь введенной переменной, на оба данных нам числа одновременно.
- Если делится, то функция прекращает свою работу и выводит это число, которое и будет наименьшим общим кратным (НОК).
- Если нет, то опять вызывается эта рекурсивная функция, в которой значение переменной еще раз увеличивается на величину наибольшего из данных в задаче чисел. И так будет повторяться, пока не выполнится условие делимости без остатка на оба числа.
- После того как функция завершит свою работу, значение наименьшего общего кратного (НОК) выводится на экран.
Исходный код
Ниже дан исходный код, который осуществляет нахождение наименьшего общего кратного (НОК) с использованием рекурсии. Результаты работы программы также даны ниже.
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)
Объяснение работы программы
- Пользователь вводит два числа и они записываются в переменные
a
иb
. - Также вводится еще одна переменная,
lcm.multiple
, которая для начала инициируется нулем. - Далее проверяется, какое из введенных чисел больше, чтобы передать их в рекурсивную функцию
lcm()
в порядке возрастания. - В функции
lcm()
на первом шаге значение переменной увеличивается на величину наибольшего из введенных пользователем чисел. То есть при первом вызове функции значение переменной становится равным этому числу. - Затем происходит проверка, делится ли значение переменной
lcm.multiple
без остатка на оба наших числа одновременно. Если делится, то функция прекращает свою работу и выводит в качестве результата значение переменнойlcm.multiple
. - Если нет, то опять вызывается рекурсивная функция
lcm()
, в которой значение переменнойlcm.multiple
еще раз увеличивается на величину наибольшего из данных в задаче чисел. И так будет повторяться, пока не выполнится условие делимости без остатка на оба числа. - После того как функция завершит свою работу, значение наименьшего общего кратного (НОК) выводится на экран.
Результаты работы программы
Пример 1:
Введите первое число:126
Введите второе число:12
НОК:
252
Пример 2:
Введите первое число:25
Введите второе число:5
НОК:
25
https://pythonist.ru/nahozhdenie-naimenshego-obshhego-kratnogo-nok-pri-pomoshhi-rekursii/