Как найти нод трех чисел питон - Исправление недочетов и поиск решений вместе с Examum.ru

import math
math.gcd(2, 6, 12)  # 2

math.gcd Changed in version 3.9: Added support for an arbitrary number of arguments. Formerly, only two arguments were supported.

До версии 3.9, но выше 3.5 можно скомбинировать так:

math.gcd(3, math.gcd(6, 12))  # 3

Пример:

from math import gcd
from functools import reduce

reduce(gcd, [3, 12, 6, 18])  # 3

Для версии ниже 3.5:

from functools import reduce

def gcd(a, b):
    return gcd(b, a % b) if b else a

reduce(gcd, [3, 6, 12])  # 3

Источник

So I’m writing a program in Python to get the GCD of any amount of numbers.

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]


    # i'm stuck here, this is wrong
    for i in range(len(numbers)-1):
        print GCD([numbers[i+1], numbers[i] % numbers[i+1]])


print GCD(30, 40, 36)

The function takes a list of numbers.
This should print 2. However, I don’t understand how to use the the algorithm recursively so it can handle multiple numbers. Can someone explain?

updated, still not working:

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]

    gcd = 0

    for i in range(len(numbers)):
        gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])
        gcdtemp = GCD([gcd, numbers[i+2]])
        gcd = gcdtemp

    return gcd

Ok, solved it

def GCD(a, b):

    if b == 0:
        return a
    else:
        return GCD(b, a % b)

and then use reduce, like

reduce(GCD, (30, 40, 36))

asked May 18, 2013 at 19:19

TetramputechtureTetramputechture

2,9112 gold badges32 silver badges47 bronze badges

Since GCD is associative, GCD(a,b,c,d) is the same as GCD(GCD(GCD(a,b),c),d). In this case, Python’s reduce function would be a good candidate for reducing the cases for which len(numbers) > 2 to a simple 2-number comparison. The code would look something like this:

if len(numbers) > 2:
    return reduce(lambda x,y: GCD([x,y]), numbers)

Reduce applies the given function to each element in the list, so that something like

gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])

is the same as doing

gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)

Now the only thing left is to code for when len(numbers) <= 2. Passing only two arguments to GCD in reduce ensures that your function recurses at most once (since len(numbers) > 2 only in the original call), which has the additional benefit of never overflowing the stack.

answered May 18, 2013 at 19:53

alexkonradialexkonradi

7505 silver badges5 bronze badges

You can use reduce:

>>> from fractions import gcd
>>> reduce(gcd,(30,40,60))
10

which is equivalent to;

>>> lis = (30,40,60,70)
>>> res = gcd(*lis[:2])  #get the gcd of first two numbers
>>> for x in lis[2:]:    #now iterate over the list starting from the 3rd element
...    res = gcd(res,x)

>>> res
10

help on reduce:

>>> reduce?
Type:       builtin_function_or_method
reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.

answered May 18, 2013 at 19:27

Ashwini ChaudharyAshwini Chaudhary

243k58 gold badges460 silver badges503 bronze badges

Python 3.9 introduced multiple arguments version of math.gcd, so you can use:

import math
math.gcd(30, 40, 36)

3.5 <= Python <= 3.8.x:

import functools
import math
functools.reduce(math.gcd, (30, 40, 36))

3 <= Python < 3.5:

import fractions
import functools
functools.reduce(fractions.gcd, (30, 40, 36))

answered May 13, 2020 at 16:08

Yam MesickaYam Mesicka

6,2157 gold badges45 silver badges64 bronze badges

A solution to finding out the LCM of more than two numbers in PYTHON is as follow:

#finding LCM (Least Common Multiple) of a series of numbers

def GCD(a, b):
    #Gives greatest common divisor using Euclid's Algorithm.
    while b:      
        a, b = b, a % b
    return a

def LCM(a, b):
    #gives lowest common multiple of two numbers
    return a * b // GCD(a, b)

def LCMM(*args):
    #gives LCM of a list of numbers passed as argument 
    return reduce(LCM, args)

Here I’ve added +1 in the last argument of range() function because the function itself starts from zero (0) to n-1. Click the hyperlink to know more about range() function :

print ("LCM of numbers (1 to 5) : " + str(LCMM(*range(1, 5+1))))
print ("LCM of numbers (1 to 10) : " + str(LCMM(*range(1, 10+1))))
print (reduce(LCMM,(1,2,3,4,5)))

those who are new to python can read more about reduce() function by the given link.

answered May 28, 2015 at 6:22

MD SARFARAZMD SARFARAZ

1172 silver badges17 bronze badges

The GCD operator is commutative and associative. This means that

gcd(a,b,c) = gcd(gcd(a,b),c) = gcd(a,gcd(b,c))

So once you know how to do it for 2 numbers, you can do it for any number

To do it for two numbers, you simply need to implement Euclid’s formula, which is simply:

// Ensure a >= b >= 1, flip a and b if necessary
while b > 0
  t = a % b
  a = b
  b = t
end
return a

Define that function as, say euclid(a,b). Then, you can define gcd(nums) as:

if (len(nums) == 1)
  return nums[1]
else
  return euclid(nums[1], gcd(nums[:2]))

This uses the associative property of gcd() to compute the answer

answered May 18, 2013 at 19:23

torquestomptorquestomp

3,30418 silver badges26 bronze badges

Try calling the GCD() as follows,

i = 0
temp = numbers[i]
for i in range(len(numbers)-1):
        temp = GCD(numbers[i+1], temp)

answered May 18, 2013 at 19:28

DeepuDeepu

7,5844 gold badges25 silver badges47 bronze badges

My way of solving it in Python. Hope it helps.

def find_gcd(arr):
    if len(arr) <= 1:
        return arr
    else:
        for i in range(len(arr)-1):
            a = arr[i]
            b = arr[i+1]
            while b:
                a, b = b, a%b
            arr[i+1] = a
        return a
def main(array):
    print(find_gcd(array))

main(array=[8, 18, 22, 24]) # 2
main(array=[8, 24]) # 8
main(array=[5]) # [5]
main(array=[]) # []

Some dynamics how I understand it:

ex.[8, 18] -> [18, 8] -> [8, 2] -> [2, 0]

18 = 8x + 2 = (2y)x + 2 = 2z where z = xy + 1

ex.[18, 22] -> [22, 18] -> [18, 4] -> [4, 2] -> [2, 0]

22 = 18w + 4 = (4x+2)w + 4 = ((2y)x + 2)w + 2 = 2z

answered Jul 24, 2018 at 2:06

Zoe LZoe L

1,10914 silver badges21 bronze badges

As of python 3.9 beta 4, it has got built-in support for finding gcd over a list of numbers.

Python 3.9.0b4 (v3.9.0b4:69dec9c8d2, Jul  2 2020, 18:41:53)
[Clang 6.0 (clang-600.0.57)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> A = [30, 40, 36]
>>> print(math.gcd(*A))
2

answered Aug 5, 2020 at 2:24

bigbountybigbounty

16.2k5 gold badges36 silver badges63 bronze badges

One of the issues is that many of the calculations only work with numbers greater than 1. I modified the solution found here so that it accepts numbers smaller than 1. Basically, we can re scale the array using the minimum value and then use that to calculate the GCD of numbers smaller than 1.

# GCD of more than two (or array) numbers - alows folating point numbers
# Function implements the Euclidian algorithm to find H.C.F. of two number 
def find_gcd(x, y): 
    while(y): 
        x, y = y, x % y 
    return x 
          
# Driver Code         
l_org = [60e-6, 20e-6, 30e-6]
min_val = min(l_org)
l = [item/min_val for item in l_org]
  
num1 = l[0] 
num2 = l[1] 
gcd = find_gcd(num1, num2) 
  
for i in range(2, len(l)): 
    gcd = find_gcd(gcd, l[i]) 
      
gcd = gcd * min_val
print(gcd)

answered Aug 10, 2020 at 19:04

Nikhil GuptaNikhil Gupta

1,39612 silver badges15 bronze badges

HERE IS A SIMPLE METHOD TO FIND GCD OF 2 NUMBERS

a = int(input("Enter the value of first number:"))
b = int(input("Enter the value of second number:"))
c,d = a,b
while a!=0:
    b,a=a,b%a
print("GCD of ",c,"and",d,"is",b)

answered Oct 24, 2020 at 5:35

As You said you need a program who would take any amount of numbers
and print those numbers’ HCF.

In this code you give numbers separated with space and click enter to get GCD

num =list(map(int,input().split()))  #TAKES INPUT
def print_factors(x):          #MAKES LIST OF LISTS OF COMMON FACTROS OF INPUT
    list = [ i for i in range(1, x + 1) if x % i == 0 ]
    return list

p = [print_factors(numbers) for numbers in num]
result = set(p[0])        
for s in p[1:]:             #MAKES THE SET OF COMMON VALUES IN LIST OF LISTS
    result.intersection_update(s)

for values in result:
    values = values*values     #MULTIPLY ALL COMMON FACTORS TO FIND GCD
    values = values//(list(result)[-1])  
print('HCF',values)

Hope it helped

answered Nov 11, 2022 at 14:03

Источник

-79 / 0 / 0

Регистрация: 24.02.2019

Сообщений: 34

Функция: нахождения НОД трех чисел

24.02.2019, 22:16. Показов 15962. Ответов 1

Записати програму нахождения НОД трех чисел.

Programming Эксперт 94731 / 64177 / 26122 Регистрация: 12.04.2006 Сообщений: 116,782	24.02.2019, 22:16
1

Arsegg

3484 / 2091 / 560

Регистрация: 02.09.2015

Сообщений: 5,336

24.02.2019, 22:28

Сообщение было отмечено mik-a-el как решение

Решение

Python

def gcd(a, b, c = None):
    return ((a if b == 0 else gcd(b, a % b)) if c is None
            else gcd(gcd(a, b), gcd(a, c)))
 
if __name__ == "__main__":
    a, b, c = (int(input()) for i in range(3))
    print(gcd(a, b, c))

Источник

Ниже описано, как вычислить и получить наибольший общий делитель и наименьшее общее кратное в Python.

Наибольший общий делитель и наименьшее общее кратное двух целых чисел
Наибольший общий делитель и наименьшее общее кратное трех или более целых чисел

Обратите внимание, что спецификации функций, представленных в стандартной библиотеке, отличаются в зависимости от версии Python. Пример реализации функции, не входящей в стандартную библиотеку, также показан в этой статье.

Python 3.4 или более ранняя версия
- GCD:fractions.gcd()(только два аргумента)
Python 3.5 или более поздняя версия
- GCD:math.gcd()(только два аргумента)
Python 3.9 или более поздняя версия
- GCD:math.gcd()(поддерживает более трех аргументов)
- наименьший общий знаменатель:math.lcm()(поддерживает более трех аргументов)

Здесь мы объясним метод с использованием стандартной библиотеки Python; NumPy можно легко использовать для вычисления наибольшего общего делителя и наименьшего общего кратного для каждого элемента нескольких массивов.

Table of Contents

Наибольший общий делитель и наименьшее общее кратное двух целых чисел
- GCD
- наименьший общий знаменатель
Наибольший общий делитель и наименьшее общее кратное трех или более целых чисел
- Python 3.9 или более поздняя версия
- Python 3.8 или более ранняя версия
  - GCD
  - наименьший общий знаменатель

Наибольший общий делитель и наименьшее общее кратное двух целых чисел

GCD

Начиная с Python 3.5, в математическом модуле появилась функция gcd(). gcd() — это аббревиатура, означающая

greatest common divisor

math.gcd() — Mathematical functions — Python 3.10.2 Documentation

Возвращает наибольший общий делитель целого числа, указанного в аргументе.

import math

print(math.gcd(6, 4))
# 2

Обратите внимание, что в Python 3.4 и более ранних версиях функция gcd() находится в модуле fractions, а не в модуле math. fractions должен быть импортирован и fractions.gcd().

fractions.gcd() — Rational numbers — Python 3.10.2 Documentation

наименьший общий знаменатель

Функция lcm(), которая возвращает наименьшее общее кратное, была добавлена в математический модуль в Python 3.9. lcm — это аббревиатура для

least common multiple

math.lcm() — Mathematical functions — Python 3.10.2 Documentation

Возвращает наименьшее общее кратное целого числа, указанного в аргументе.

print(math.lcm(6, 4))
# 12

До версии Python 3.8 функция lcm() не предоставлялась, но ее можно легко вычислить с помощью gcd().

lcm(a, b) = a * b / gcd(a, b)

Пример реализации.

def my_lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(my_lcm(6, 4))
# 12

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

Наибольший общий делитель и наименьшее общее кратное трех или более целых чисел

Python 3.9 или более поздняя версия

Начиная с Python 3.9, все следующие функции поддерживают более трех аргументов.

math.gcd()
math.lcm()

print(math.gcd(27, 18, 9))
# 9

print(math.gcd(27, 18, 9, 3))
# 3

print(math.lcm(27, 9, 3))
# 27

print(math.lcm(27, 18, 9, 3))
# 54

*Если вы хотите вычислить наибольший общий делитель или наименьшее общее кратное элементов списка, укажите аргумент this.

l = [27, 18, 9, 3]
print(math.gcd(*l))
# 3

print(math.lcm(*l))
# 54

Python 3.8 или более ранняя версия

До версии Python 3.8 функция gcd() поддерживала только два аргумента.

Чтобы найти наибольший общий делитель или наименьшее общее кратное трех или более целых чисел, не требуется особенно сложного алгоритма; достаточно вычислить наибольший общий делитель или наименьшее общее кратное для каждого из кратных значений по очереди с помощью функции высшего порядка reduce().

functools — Higher-order functions and operations on callable objects — Python 3.10.2 Documentation

GCD

from functools import reduce

def my_gcd(*numbers):
    return reduce(math.gcd, numbers)

print(my_gcd(27, 18, 9))
# 9

print(my_gcd(27, 18, 9, 3))
# 3

l = [27, 18, 9, 3]
print(my_gcd(*l))
# 3

Опять же, обратите внимание, что до Python 3.4 функция gcd() находилась в модуле fraction, а не в модуле math.

наименьший общий знаменатель

def my_lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def my_lcm(*numbers):
    return reduce(my_lcm_base, numbers, 1)

print(my_lcm(27, 9, 3))
# 27

print(my_lcm(27, 18, 9, 3))
# 54

l = [27, 18, 9, 3]
print(my_lcm(*l))
# 54

Источник

Название: Найдите наибольший общий делитель и наименьшее общее кратное из двух натуральных чисел.
Основные требования: 1. Стиль программы хороший (с использованием пользовательских шаблонов аннотаций), два или более алгоритма решают проблему наибольшего общего делителя и обеспечивают дружественный ввод и вывод.
Увеличьте требования:
1. Более трех алгоритмов решают проблему двух натуральных чисел.
2. Найдите наибольший общий делитель и наименьшее общее кратное из 3 натуральных чисел.

Исходный код выглядит следующим образом:

# Разделить на деление, чтобы найти наибольший общий делитель
#
# a = int (input ("Пожалуйста, введите значение a:"))
# b = int (input ("Пожалуйста, введите значение для b:"))
# c = 0
# if a<b:
#     c = a
#     a = b
#     b = c
# while a%b!=0:
#     c = a%b
#     a = b
#     b = c
# print («Наибольший общий делитель: + str (b))






# Вычитание, чтобы найти наибольший общий делитель


# a = int (input ("Пожалуйста, введите значение a:"))
# b = int (input ("Пожалуйста, введите значение для b:"))
# c = 0
# if a<b:
#     c = a
#     a = b
#     b = c
# while a-b!=0:
#     c = a-b
#     a = b
#     b = c
# print («Наибольший общий делитель: + str (b))





# Третий способ найти наибольший общий делитель

# Введите два числа и пролистайте числа от 1 до минимума двух чисел. Когда это число можно разделить на a и b одновременно, сохраните эти числа в массиве i []
# Используйте sort (), чтобы отсортировать массив i от малого к большому, и использовать i [-1], чтобы вывести максимальное значение массива i [], то есть наибольший общий делитель

# a = int (input ("Пожалуйста, введите значение a:"))
# b = int (input ("Пожалуйста, введите значение для b:"))
# if a>b:
#     t = a
#     a = b
#     b = t
# for n in range(1,a+1):
#     if a%n==0 and b%n==0:
#         i = [n]
#         i.sort()
# print ("Самый большой общий делитель:" + str (i [-1]))
#
#
#
#
#



# Найдите самый большой общий делитель трех чисел: сначала найдите самый большой общий делитель двух чисел, а затем найдите самый большой общий делитель другого числа
# a = int (input ("Пожалуйста, введите значение a:"))
# b = int (input ("Пожалуйста, введите значение для b:"))
# c = int (input ("Пожалуйста, введите значение c:"))
# if a>b:
#     t = a
#     a = b
#     b = t
# for n in range(1,a+1):
#     if a%n==0 and b%n==0:
#         i = [n]
#         i.sort()
# m = i[-1]
# print ("Наибольший общий делитель a и b:" + str (m))
# if m>c:
#     l = m
#     m = c
#     c = l
# for n in range(1, m+1):
#     if m%n == 0 and c%n == 0:
#         p = [n]
#         p.sort()
# print ("Самый большой общий делитель a b c:" + str (p [-1]))
#
#



# Первый способ найти наименьшее общее кратное
# Найти наименьшее общее кратное из трех чисел, циклически перебрать кратные трех чисел, найти одно и то же число, поместить его в массив и вывести минимальное значение.
# a = int (input ("Пожалуйста, введите значение a:"))
# b = int (input ("Пожалуйста, введите значение для b:"))
# c = int (input ("Пожалуйста, введите значение c:"))
# d = a * b * c
# m = []
# n = []
# o = []
# for i in range(1, d + 1):
#     if i % a == 0:
#         m.append(i)
# print («Общее кратное от a:» + str (m))
# for j in range(1, d + 1):
#     if j % b == 0:
#         n.append(j)
# print ("Общее кратное b:" + str (n))
# for k in range(1, d + 1):
#     if k % c == 0:
#         o.append(k)
# print ("Общее кратное c:" + str (o)) # Три массива хранят общее кратное abc
# f = []
# for i in m:
#     if (i in n):
#         if (i in o):
#             f.append(i)
#             f.sort()
# print («Все общие кратные a b c:» + str (f [0]))


# Второй способ найти наименьшее общее кратное
# Чтобы найти наименьшее общее кратное из трех чисел, сначала установите число = 1 и цикл, чтобы определить число для взятия остатка abc. Если остаток равен 0 одновременно, выпрыгните из цикла и выведите номер, в противном случае продолжайте цикл номер + = 1
a = int(input(«Пожалуйста, введите значение:»))
b = int(input(«Пожалуйста, введите значение для b:»))
c = int(input(«Пожалуйста, введите значение c:»))
number = 1
while True:
    if number%a==0 and number%b==0 and number%c==0:
        print(«Наименьшее общее кратное abc это:» + str(number))
        break
    else:
        number+=1

Идея алгоритма:
Методы для нахождения наибольшего общего делителя двух целых чисел:
1. Идея алгоритма: скручивание и деление
2. Идея алгоритма: свертывание и вычитание
3. Идея алгоритма: введите два числа и зафиксируйте число между 1 и минимумом из этих двух чисел. Когда это число можно разделить на a и b одновременно, разделите их Числа хранятся в массиве i []. Используйте функцию sort (), чтобы отсортировать массив i [] от малого к большому, а затем вывести i [-1], который является наибольшим общим делителем

Чтобы найти наибольший общий делитель из трех натуральных чисел:
1. Идея алгоритма: на основе описанного выше метода 3 вычислить наибольший общий делитель между двумя парами.

Чтобы найти наименьшее общее кратное из трех натуральных чисел:
1. Идея алгоритма: сначала выведите кратные значения трех чисел в цикле, затем найдите одинаковые числа в трех массивах, поместите эти числа в новый массив и используйте sort () Сортировка и вывод
2. Идея алгоритма: сначала установите число = 1, затем, пока выполняется цикл True, определите число для взятия остатка из abc, разбейте, когда их остаток равен 0, а затем выведите число Значение, иначе число + = 1

Блок-схема системы для нахождения наибольшего общего делителя:

Системная блок-схема поиска наименьшего общего кратного:

Источник