Как найти НОК или НОД в python 3.9 в списке из n кол-ва чисел? (Ввод чисел пользователем)
(н: math.gcd([1 , 2 , 3])
задан 26 окт 2021 в 16:22
4
список из нескольких чисел можно получить следующим образом:
data = list(map(int, input().split()))
весь код таким образом будет выглядеть так:
import math
data = list(map(int, input().split()))
gcd = math.gcd(*data)
lcm = math.lcm(*data)
print(gcd, lcm)
ответ дан 26 окт 2021 в 16:42
ZhiharZhihar
36.8k4 золотых знака25 серебряных знаков66 бронзовых знаков
1
print ('a = ', end = '')
a = int (input ())
print ('b = ', end = '')
b = int (input ())
p = a * b
while a != 0 and b != 0:
if a > b:
a = a % b
else:
b = b % a
nod = a + b
nok = p // nod
print ('GCD:', nok)
print ('LDM:', nod)
ответ дан 26 окт 2021 в 16:29
2
0 / 0 / 0 Регистрация: 10.06.2020 Сообщений: 18 |
|
1 |
|
Найти НОК последовательности08.08.2021, 16:36. Показов 1824. Ответов 3
На вход программы поступает последовательность из N целых положительных чисел. Необходимо найти их наименьшее общее кратное.
0 |
7254 / 4043 / 1779 Регистрация: 27.03.2020 Сообщений: 6,869 |
|
08.08.2021, 17:03 |
2 |
Manichka, зфтш мфти?
0 |
Matrix3007 194 / 160 / 41 Регистрация: 13.05.2019 Сообщений: 828 |
||||
08.08.2021, 19:25 |
3 |
|||
0 |
Arsegg 3480 / 2088 / 559 Регистрация: 02.09.2015 Сообщений: 5,332 |
||||
08.08.2021, 19:32 |
4 |
|||
2 |
IT_Exp Эксперт 87844 / 49110 / 22898 Регистрация: 17.06.2006 Сообщений: 92,604 |
08.08.2021, 19:32 |
Помогаю со студенческими работами здесь Найти НОК У меня получается 6n(n+1), но это не верный ответ. Может у вас что-то… Найти b из НОК (a,b)=c Никак не могу придумать, как… Найти НОК Найти НОК Найти НОК найти НОК Искать еще темы с ответами Или воспользуйтесь поиском по форуму: 4 |
В данном уроке мы узнаем, как найти наименьшее общее кратное (НОК) и наибольший общий делитель (НОД) с помощью языка программирования Python.
Но прежде чем мы начнем, давайте разберем, что обозначает Least Common Multiple (LCM) — наименьшее общее кратное.
НОК: наименьшее общее кратное
Это понятие арифметики и системы счисления. НОК двух целых чисел a и b обозначается НОК(a,b). Это наименьшее натуральное число, которое делится и на «а», и на «b».
Например: у нас есть два целых числа 4 и 6. Найдем НОК:
- Кратные 4:
4, 8, 12, 16, 20, 24, 28, 32, 36,... and so on...
- Кратные 6:
6, 12, 18, 24, 30, 36, 42,... and so on....
Общие кратные 4 и 6 — это просто числа, которые есть в обоих списках:
12, 24, 36, 48, 60, 72,.... and so on....
НОК — это наименьший общий множитель, поэтому он равен 12.
Поскольку мы поняли основную концепцию НОК, давайте рассмотрим следующую программу для нахождения НОК заданных целых чисел.
Пример:
# defining a function to calculate LCM def calculate_lcm(x, y): # selecting the greater number if x > y: greater = x else: greater = y while(True): if((greater % x == 0) and(greater % y == 0)): lcm = greater break greater += 1 return lcm # taking input from users num1 = int(input("Enter first number: ")) num2 = int(input("Enter second number: ")) # printing the result for the users print("The L.C.M. of", num1,"and", num2,"is", calculate_lcm(num1, num2))
Выход:
Enter first number: 3 Enter second number: 4 The L.C.M. of 3 and 4 is 12
Объяснение:
Эта программа сохраняет два числа в num1 и num2 соответственно. Эти числа передаются в функцию calculate_lcm(). Функция возвращает НОК двух чисел.
Внутри функции мы сначала определили большее из двух чисел, поскольку наименьшее общее кратное может быть больше или равно наибольшему числу. Затем мы используем бесконечный цикл while, чтобы перейти от этого числа и дальше.
На каждой итерации мы проверяли, идеально ли делят оба числа число. Если это так, мы сохранили число как НОК и вышли из цикла. В противном случае число увеличивается на 1, и цикл продолжается.
НОД: наибольший общий делитель
В этом разделе мы разберем, как найти Highest Common Factor (HCF) — наибольший общий делитель (НОД) в языке программирования Python.
Наибольший общий делитель двух или более целых чисел, когда хотя бы одно из них не равно нулю, является наибольшим положительным целым числом, которое без остатка делит целые числа. Например, НОД 8 и 12 равен 4.
Например:
У нас есть два целых числа 8 и 12. Найдем наибольший общий делитель.
- Делители числа 8:
1, 2, 4, 8
- Делители числа 12:
1, 2, 3, 4, 6, 12
НОД 8 и 12 равны 4.
Теперь давайте рассмотрим пример, основанный на нахождении НОД двух заданных чисел.
Пример:
# defining a function to calculate HCF def calculate_hcf(x, y): # selecting the smaller number if x > y: smaller = y else: smaller = x for i in range(1,smaller + 1): if((x % i == 0) and(y % i == 0)): hcf = i return hcf # taking input from users num1 = int(input("Enter first number: ")) num2 = int(input("Enter second number: ")) # printing the result for the users print("The H.C.F. of", num1,"and", num2,"is", calculate_hcf(num1, num2))
Выход:
Enter first number: 8 Enter second number: 12 The H.C.F. of 8 and 12 is 4
Объяснение:
В приведенном выше фрагменте кода два целых числа, хранящиеся в переменных num1 и num2, передаются в функцию calculate_hcf(). Функция вычисляет НОД для этих двух чисел и возвращает его.
Внутри функции мы должны определить меньшее число, поскольку НОД может быть меньше или равен наименьшему числу. Затем мы использовали цикл for, чтобы перейти от 1 к этому числу.
На каждой итерации мы должны проверять, точно ли число делит оба входных числа. Если это так, мы должны сохранить число как НОД. По завершении цикла мы получаем наибольшее число, которое идеально делит оба числа.
1196-1017cookie-checkНахождение НОК и НОД в Python — примеры
Наименьшее общее кратное
Написать функцию, которая вычисляет наименьшее общее кратное (НОК) пары чисел по формуле
НОК = ab / НОД(a, b),
где 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) упрощается.
def lcm(a, b): import math return (a * b) // math.gcd(a, b)
Больше задач в PDF
you need to find to LCM of the whole list. let “l” be the LCM of the whole array and if we pick any 2 random numbers from array, they will have a LCM say “l1” and so on and so forth “l2″,”l3”,”l4″…. the LCM of these will also be the LCM of the whole array.
# we can find LCM of two numbers by the basic prime factorizing method
# but i will use the idea that GCD(a,b) * LCM(a,b) = a*b
# and it is easy to find the GCD(a,b)=[GCD(a,a%b)or GCD(b,b%a)] depending on if a is bigger or b
# i have used this idea because factoring large numbers take time.
so my idea is you can use divide and conquer
def LCM_of_array(array):
if len(array)==2:
return LCM(a,b)
else:
return LCM( LCM_of_array(n[0:len(array)/2]) , LCM_of_array(n[len(array)/2:len(array)])
you can explicitly define LCM(a,b) or just add a few more line of codes in this only
Edit: Code
def nod(a, b): #to find GCD
if b == 0:
return a
else:
if a>b:
return nod(b, a % b)
else:
return nod(a,b%a)
def nok(a, b): #to find LCM of two numbers
return a * b / nod(a, b)
def nok_of_array(n): #function for LCM of array
if len(n) == 2:
return nok(n[0], n[1])
else:
return nok (nok_of_array(n[ 0:len(n)/2 ]) , nok_of_array( n [ len(n)/2 : len(n)]))