Как найти наименьшее общее кратное программа

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

НОК в C++ двух целых чисел a и b – это наименьшее положительное целое число, которое делится как на a, так и на b .

#include using namespace std; int main() < int n1, n2, max; cout > n1 >> n2; // maximum value between n1 and n2 is stored in max max = (n1 > n2) ? n1 : n2; do < if (max % n1 == 0 max % n2 == 0) < cout Enter two numbers: 12 18 LCM = 36

В приведенной выше программе пользователя просят ввести два целых числа n1 и n2, и наибольшее из этих двух чисел сохраняется в max .

Проверяется, делится ли max на n1 и n2 , если он делится на оба числа, печатается max и цикл завершается.

Если нет, значение max увеличивается на 1, и тот же процесс продолжается до тех пор, пока max не станет делиться как на n1, так и на n2 .

Пример 2

LCM = (n1 * n2) / HCF

#include using namespace std; int main() < int n1, n2, hcf, temp, lcm; cout > n1 >> n2; hcf = n1; temp = n2; while(hcf != temp) < if(hcf >temp) hcf -= temp; else temp -= hcf; > lcm = (n1 * n2) / hcf; cout

ЧТО ТАКОЕ НОК И НОД? ЧАСТЬ I #математика #shorts #задачиегэ #профильныйегэ #нок #нод

• Преобразование восьмеричного числа в десятичное и наоборот в C++
• Преобразование двоичного числа в восьмеричное и наоборот в C++
• Как перевернуть строку в C++

• Свежие записи

• Функция iscntrl() в C++
• Функция isdigit() в С++
• Функция isblank() в C++
• Функция isgraph() в C++
• Функция islower() в C++

Источник: calmsen.ru

Наименьшее общее кратное

где a и b — это натуральные числа, НОД — наибольший общий делитель.

Решение задачи на языке программирования Python

Из условия задачи ясно, чтобы найти НОК, надо сначала найти НОД. Последний можно вычислить, постепенно находя остаток от деления большего числа из пары на меньшее и присваивая остаток переменной, связанной с большим числом (см. алгоритм Евклида). В какой-то момент значение одной из переменных станет равным 0. Когда это произойдет, другая будет содержать НОД. Если неизвестно, какая именно переменная содержит НОД, то можно просто сложить значения обоих переменных.

В коде ниже используется функция для нахождения НОК, которая принимает два числа и возвращает найденное наименьшее общее кратное.

В основной ветке программы функция вызывается в цикле, который завершается, если то, что было введено, нельзя преобразовать к целому. В этом случае генерируется исключение и поток выполнения переходит к ветке except .

def lcm(a, b): m = a * b while a != 0 and b != 0: if a > b: a %= b else: b %= a return m // (a + b) while 1: try: x = int(input(‘a = ‘)) y = int(input(‘b = ‘)) print(‘НОК:’, lcm(x, y)) except ValueError: break
a = 14 b = 18 НОК: 126 a = 105 b = 305 НОК: 6405 a = stop

В модуле math языка программирования Python есть функция для нахождения наибольшего общего делителя ( gcd — greatest common devisor). При ее использовании наша функция вычисления наименьшего общего кратного lcm (least common multiple) упрощается.

Наименьшее общее кратное. 5 класс.

def lcm(a, b): import math return (a * b) // math.gcd(a, b)
X Скрыть Наверх

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

Источник: younglinux.info

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

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

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

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

Источник: pythonist.ru