Евклидовой алгоритм (GCD) с несколькими номерами?

Итак, я пишу программу на Python, чтобы получить GCD любого количества чисел.

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)

Функция принимает список чисел. Это должно печатать 2. Однако я не понимаю, как использовать алгоритм рекурсивно, чтобы он мог обрабатывать несколько чисел. Может кто-нибудь объяснить?

обновлено, все еще не работает:

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

Хорошо, решил это

def GCD(a, b):

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

а затем используйте сокращение, например

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

Ответ 1

Так как GCD ассоциативен, GCD(a,b,c,d) совпадает с GCD(GCD(GCD(a,b),c),d). В этом случае функция Python reduce была бы хорошим кандидатом для сокращения случаев, для которых len(numbers) > 2 для простого сравнения с двумя номерами. Код будет выглядеть примерно так:

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

Уменьшить применяет данную функцию к каждому элементу в списке, так что что-то вроде

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

совпадает с

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

Теперь осталось только код для len(numbers) <= 2. Передача только двух аргументов в GCD в reduce гарантирует, что ваша функция будет повторяться не более одного раза (поскольку len(numbers) > 2 только в исходном вызове), что имеет дополнительное преимущество никогда не переполнять стек.

Ответ 2

Вы можете использовать reduce:

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

что эквивалентно:

>>> 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 на 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.

Ответ 3

Оператор GCD является коммутативным и ассоциативным. Это означает, что

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

Итак, как только вы знаете, как сделать это для 2 чисел, вы можете сделать это для любого числа

Чтобы сделать это для двух чисел, вам просто нужно реализовать формулу Евклида, которая просто:

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

Определите эту функцию как, скажем euclid(a,b). Затем вы можете определить gcd(nums) как:

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

Это использует ассоциативное свойство gcd() для вычисления ответа

Ответ 4

Решение найти LCM более двух чисел в PYTHON выглядит следующим образом:

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

def GCD(a, b):
    #Gives greatest common divisor using Euclid 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)

Здесь я добавил +1 в последний аргумент функции range(), потому что сама функция начинается с нуля (0) до n-1. Нажмите гиперссылку, чтобы узнать больше о range():

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)))

те, кто новичок в python, могут читать дополнительную информацию о reduce() по данной ссылке.

Ответ 5

Попробуйте вызвать GCD() следующим образом:

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