libreria - python math functions list

¿Algoritmo euclídeo(GCD) con números múltiples?

Question

Entonces estoy escribiendo un programa en Python para obtener el GCD de cualquier cantidad de números.

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)

La función toma una lista de números. Esto debería imprimir 2. Sin embargo, no entiendo cómo usar el algoritmo de forma recursiva, por lo que puede manejar múltiples números. ¿Alguien puede explicar?

actualizado, todavía no funciona:

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 resolvelo

def GCD(a, b):

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

y luego usar reducir, como

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

Answer 1

Como GCD es asociativo, GCD(a,b,c,d) es lo mismo que GCD(GCD(GCD(a,b),c),d) . En este caso, la función de reduce de Python sería un buen candidato para reducir los casos para los cuales len(numbers) > 2 a una comparación simple de 2 números. El código se vería algo así:

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

Reducir aplica la función dada a cada elemento de la lista, de modo que algo como

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

es lo mismo que hacer

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

Ahora lo único que queda es codificar cuándo len(numbers) <= 2 . Pasar solo dos argumentos a GCD en reduce asegura que su función recurra como máximo una vez (ya que len(numbers) > 2 solo en la llamada original), lo que tiene el beneficio adicional de no desbordar la pila.

Answer 2

El operador de GCD es conmutativo y asociativo. Esto significa que

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

Así que una vez que sabes cómo hacerlo para 2 números, puedes hacerlo para cualquier número

Para hacerlo con dos números, simplemente necesitas implementar la fórmula de Euclid, que es simplemente:

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

Define esa función como, digamos euclid(a,b) . Entonces, puedes definir gcd(nums) como:

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

Esto usa la propiedad asociativa de gcd () para calcular la respuesta

Answer 3

Intente llamar al GCD() como sigue,

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

Answer 4

Mi forma de resolverlo en Python. Espero eso ayude.

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=[]) # []

Algunas dinámicas como lo entiendo:

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

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

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

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

Answer 5

Puedes usar reduce :

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

que es equivalente a;

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

ayuda en 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.

Answer 6

Una solución para descubrir el MCM de más de dos números en PYTHON es la siguiente:

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

Aquí he agregado +1 en el último argumento de la función range () porque la función en sí misma comienza desde cero (0) hasta n-1. Haga clic en el hipervínculo para saber más sobre la función 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)))

Aquellos que son nuevos en Python pueden leer más sobre la función reduce() mediante el enlace dado.