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

Entonces estoy escribiendo un progtwig 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)) 

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

    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. 

    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

    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.

    Intente llamar al GCD() siguiente manera,

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

    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