Euklidischer Algorithmus (GCD) mit mehreren Zahlen?

Question

Also schreibe ich ein Programm in Python, um die GCD von einer beliebigen Anzahl von Zahlen zu bekommen.

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) 

Die Funktion übernimmt eine Liste mit Zahlen. Dies sollte drucken 2. Allerdings verstehe ich nicht, wie Sie den Algorithmus rekursiv verwenden, so dass es mehrere Zahlen verarbeiten kann. Kann jemand das erklären?

aktualisiert, immer noch nicht funktioniert:

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, löste es

def GCD(a, b): 

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

und dann reduzieren verwenden, wie

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

Answer 1

Da GCD ist assoziativ, ist GCD(a,b,c,d) die gleiche wie GCD(GCD(GCD(a,b),c),d). In diesem Fall wäre Pythons reduce-Funktion ein guter Kandidat für die Reduzierung der Fälle, für die len(numbers) > 2 zu einem einfachen 2-Nummern-Vergleich.Der Code würde wie folgt aussehen:

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

Reduzieren Sie die gegebene Funktion auf jedes Element in der Liste gilt, so dass so etwas wie

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

ist die gleiche wie zu tun

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

Jetzt ist nur noch zu codieren, wenn len(numbers) <= 2. Die Übergabe von nur zwei Argumenten an GCD in reduce stellt sicher, dass Ihre Funktion höchstens einmal rekursiv ist (seit len(numbers) > 2 nur im ursprünglichen Aufruf), was den zusätzlichen Vorteil hat, niemals den Stack zu überlaufen.

Answer 2

Die GCD-Operator ist kommutativ und assoziativ. Das bedeutet, dass

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

Also, wenn Sie wissen, wie es für zwei Zahlen zu tun, können Sie es für eine beliebige Anzahl tun können

---

Um es für zwei Zahlen zu tun, müssen Sie einfach Euklids Formel implementieren , das ist einfach:

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

diese Funktion definieren als, sagen euclid(a,b). Dann können Sie festlegen, wie gcd(nums):

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

Dadurch wird die assoziative Eigenschaft von gcd() verwendet, um die Antwort

Answer 3

Sie können zu berechnen verwenden reduce:

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

, die gleichwertig ist;

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

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

Versuchen Sie, die GCD() Aufruf wie folgt,

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

Answer 5

Eine Lösung für die LCM herauszufinden von mehr als zwei Zahlen in PYTHON ist wie folgt:

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

Hier habe ich ein in das letzte Argument von range() hinzugefügt Funktion, weil die Funktion selbst von Null (0) bis n-1 beginnt. Klicken Sie auf den Hyper-Link mehr über range() Funktion zu wissen:

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

diejenigen, die Python neu sind, können Sie mehr über reduce() Funktion durch den angegebenen Link lesen.