Euklidischer Algorithmus (GGT) mit mehreren Nummern?

Also ich Schreibe ein Programm in Python, um die GCD von jeder Menge von zahlen.

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 nimmt eine Liste von zahlen.
Dies sollte 2 ausgeben. Aber ich verstehe nicht, wie die der Algorithmus rekursiv, so kann es mehrere zahlen. Kann sich das jemand erklären?

aktualisiert, funktioniert immer noch nicht:

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, gelöst es

def GCD(a, b):

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

verwenden und dann zu reduzieren, wie

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

InformationsquelleAutor der Frage Tetramputechture | 2013-05-18

23

Da GCD ist assoziativ, GCD(a,b,c,d) ist das gleiche wie GCD(GCD(GCD(a,b),c),d). In diesem Fall Python ' s reduzieren Funktion wäre ein guter Kandidat für die Verringerung der Fälle, für die len(numbers) > 2 um eine einfache 2-Zahl-Vergleich. Der code würde wie folgt Aussehen:
```
if len(numbers) > 2:
    return reduce(lambda x,y: GCD([x,y]), numbers)
```
Verringern, wendet die angegebene Funktion auf jedes element der Liste, so dass so etwas wie
```
gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])
```
ist dasselbe wie
```
gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)
```
Nun das einzige, was Links ist, um code für wenn len(numbers) <= 2. Weitergabe nur zwei Argumente zu GCD im reduce sorgt dafür, dass Ihre Funktion eine Rekursion höchstens einmal (seit len(numbers) > 2 nur in der original-Aufruf), die hat den zusätzlichen Vorteil der nie überlaufen des Stacks.

InformationsquelleAutor der Antwort alexkonradi

Können Sie reduce:

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

entspricht;

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

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

InformationsquelleAutor der Antwort Ashwini Chaudhary

3

Den GCD-operator ist kommutativ und assoziativ. Dies bedeutet, dass
```
gcd(a,b,c) = gcd(gcd(a,b),c) = gcd(a,gcd(b,c))
```
So, sobald Sie wissen, wie man es für 2 Nummern, die Sie tun können es für eine beliebige Anzahl

Tun es für zwei zahlen, Sie müssen einfach zu implementieren Euklid-Formel, die 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
```
Definieren, wie es funktionieren soll, sagen euclid(a,b). Anschließend können Sie definieren gcd(nums):
```
if (len(nums) == 1)
  return nums[1]
else
  return euclid(nums[1], gcd(nums[:2]))
```
Diese nutzt die assoziative Eigenschaft gcd() zur Berechnung der Antwort

InformationsquelleAutor der Antwort torquestomp

Eine Lösung zu finden LCM 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 +1 in das Letzte argument der Bereich () - Funktion, da die Funktion selbst beginnt von null (0) auf n-1. Klicken Sie auf den hyperlink, um zu wissen, mehr über Bereich() Funktion :

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 neu in python Lesen Sie mehr über verringern() Funktion durch den angegebenen link.

InformationsquelleAutor der Antwort sarfarazit08

Versuchen Sie den Aufruf der GCD() Sie wie folgt vor,

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

InformationsquelleAutor der Antwort Deepu

Meine Lösung in Python. Hoffe, es hilft.

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

Einige Dynamik, wie ich es verstehe:

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

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

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

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

InformationsquelleAutor der Antwort Zoe L

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.