Algoritmo euclideo (GCD) con più numeri?

Question

Quindi sto scrivendo un programma in Python per ottenere il GCD di qualsiasi quantità di numeri.

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 funzione accetta un elenco di numeri. Questo dovrebbe stampare 2. Tuttavia, non capisco come utilizzare l'algoritmo in modo ricorsivo in modo che possa gestire più numeri. Qualcuno può spiegare?

aggiornato, ancora non funziona:

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

def GCD(a, b): 

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

e quindi utilizzare ridurre, come

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

Answer 1

Dal GCD è associativa, GCD(a,b,c,d) è lo stesso di GCD(GCD(GCD(a,b),c),d). In questo caso, la funzione reduce di Python sarebbe un buon candidato per ridurre i casi per cui len(numbers) > 2 a un semplice confronto a 2 numeri.Il codice dovrebbe essere simile a questa:

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

Ridurre applica la funzione data ad ogni elemento della lista, in modo che qualcosa di simile

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

è lo stesso di fare

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

Ora l'unica cosa rimasta è quella di codificare per quando len(numbers) <= 2. Passando solo due argomenti a GCD in reduce si assicura che la funzione ricorra al massimo una volta (dal len(numbers) > 2 solo nella chiamata originale), che ha l'ulteriore vantaggio di non traboccare mai lo stack.

Answer 2

L'operatore MCD è commutativa e associativo. Ciò significa che

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

Quindi una volta che sai come farlo per 2 numeri, è possibile farlo per qualsiasi numero

---

di farlo per due numeri, è sufficiente implementare la formula di Euclide , che è semplicemente:

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

definire tale funzione, dire euclid(a,b). Quindi, è possibile definire come gcd(nums):

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

Questo utilizza la proprietà associativa di MCD() per calcolare la risposta

Answer 3

È possibile utilizzare reduce:

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

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

aiuto su 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 4

Prova chiamando il GCD() come segue,

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

Answer 5

Una soluzione per scoprire la LCM di più di due numeri in PITONE è la seguente:

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

Qui ho aggiunto uno nel l'ultimo argomento di range() funzione perché la funzione stessa inizia da zero (0) a n-1. Fare clic sul collegamento ipertestuale per saperne di più sulla funzione 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))) 

coloro che sono nuovi al pitone può leggere di più su reduce() funzione dal link indicato.