Wie bestimmt diese Methode den größten gemeinsamen Teiler?

Question

In der Mathematik ist der größte gemeinsame Teiler (gcd) von zwei oder mehr ganzen Zahlen, wenn mindestens einer von ihnen nicht Null ist, die größte positive ganze Zahl, die die Zahlen ohne einen Rest teilt. Zum Beispiel kann die GCD von 8 und 12 ist 4. Wikipedia

Die folgende Methode in der Lage ist, die GCD zu bestimmen:

def gcd(a, b) 
    if a % b == 0 
    b 
    else 
    gcd(b, a % b) 
    end 
end 
p gcd(4, 12) 
#=> 4 

Wie funktioniert diese Methode?

Es macht Sinn, wenn a % b == 0 dann b die größte Zahl ist, die in a und b gehen kann.

Aber warum die gleiche Methode noch einmal aufrufen, aber die Args umschalten und den Modulus wieder nehmen?

Ich bin nicht die Argumentation hinter dem else Teil grokken.

Edit:

einige puts Aussagen Zusätzlich zu machen es klarer:

def gcd(a, b) 
    puts "Inside gcd, a: #{a}, b: #{b}, a \% b: #{a % b}" 

    if a % b == 0 
    puts "Inside if, a: #{a}, b: #{b}, a \% b: #{a % b}" 
    b 
    else 
    puts "Inside else, a: #{a}, b: #{b}, a \% b: #{a % b}" 
    gcd(b, a % b) 
    end 
end 

p gcd(55, 105) 

stdout:

Inside gcd, a: 55, b: 105, a % b: 55 
Inside else, a: 55, b: 105, a % b: 55 
Inside gcd, a: 105, b: 55, a % b: 50 
Inside else, a: 105, b: 55, a % b: 50 
Inside gcd, a: 55, b: 50, a % b: 5 
Inside else, a: 55, b: 50, a % b: 5 
Inside gcd, a: 50, b: 5, a % b: 0 
Inside if, a: 50, b: 5, a % b: 0 
5 

Answer 1

Dies ist ein euklidischer Algorithmus.

Um zu verstehen, warum Sie die Zahlen tauschen und einen anderen Rekursionsaufruf machen müssen, müssen Sie verstehen, was die eigentliche Mathematik dahinter ist. Überprüfen Sie dieses YouTube video heraus, um zu sehen, wie euklidischer Algorithmus arbeitet. Ansonsten habe ich meine Erklärung des Algorithmus unten geschrieben.

---

Formale Erläuterung des Euklidischen Algorithmus:

Eingangs

• Zwei positive ganze Zahlen sind, a und b.

Ausgabe

• Der größte gemeinsame Teiler, gcd, von a und b.

Interne Berechnung

• Wenn ein < b, Austausch a und b.
• Teilen Sie a durch b und erhalten Sie den Rest, r. Wenn r = 0 ist, melden Sie b als GCD von a und b.
• Ersetzen Sie a durch b und ersetzen Sie b durch r. Kehre zum vorherigen Schritt zurück.

---

Zum Beispiel:

gcd(40,7) 

40 = 7(5) + 5 
7 = 5(1) + 2 
5 = 2(2) + 1 <-- your gcd 
2 = 1(2) + 0 

aber bedeutet dies, dass ...

gcd(40,7) = gcd(7, gcd(40,7)) = 
gcd(7, 5) = gcd(5, gcd(7, 5)) = 
gcd(5, 2) = gcd(2, gcd(5, 2)) = 
gcd(2, 1) = 0 

wenngcd(a,b) = 0, b gleich 1, so dass wir zurück b

Jetzt hier ist der wichtige Teil! Wenn wir die Zahlen nicht austauschen würden, wären wir nicht in der Lage, die notwendigen Berechnungen durchzuführen und schließlich den Ort von b zu verfolgen, was unser gcd ist.

---

Also, der Swap ist im Wesentlichen erforderlich, um die Faktoren auf der rechten Seite zu halten. Versuchen Sie, die Mathematik ohne die Swaps zu tun, und Sie werden schnell sehen, warum es wichtig ist;)

Hoffe, das hilft!

Answer 2

Der Schlüssel Tatsache ist, dass für jeden Divisor g b, Wir haben g teilt ein wenn und nur wenn g ein% b teilt (insbesondere gilt dies für die GCD). Dies geschieht durch die Identität a = (a/b) * b + a% b, wobei/eine ganzzahlige Division ist, da g a (bzw. a% b) dividiert und g alle Vielfachen von b teilt, einschließlich (a/b) * b, daher teilt g a% b (bzw. a). Der rekursive Aufruf gibt somit das korrekte Ergebnis, wenn er endet, und er endet, weil wir immer die Größe der Eingabe reduzieren (außer beim Wurzelaufruf).

Der Grund um die Argumente zu wechseln ist so, dass die größere Zahl das erste Argument ist, da 0 < = a% b < b für positive a und b. Dies stellt sicher, dass die rekursiven Aufrufe Fortschritte machen.