Euklidischer Algorithmus

[javaner12]

Hallo,

Erstmal Lob an euch, schönes Forum!
Kann mir jemand evtl. den

erklären?

Man soll den Euklidischen Algorithmus programmieren.
Am besten wäre es Zeile für Zeile, besonders interessiert wäre ich daran, was die Buchstaben wie q, r bedeuten.

Vielen Dank!

 

[expensne]

Euklidischen Algorithmus liefert dir den ggT (größter gemeinsamer Teiler). Der klassiche Algorithmus basiert auf einer wiederholten Subtraktion, deiner allerdings, auf einer Division mit Rest, daher das q und r.

a = q * b + r

Erster Schritt: q = a/b und r = a mod b mit a > b
Zweiter Schritt: a wird zu b und b wird zu r
a = q0 * b + r0
b = q1 * r0 + r1

Und dies solange bis r = 0 ist, a = q * b + 0, dann ist b der ggT. Wenn du dann noch einmal Schritt zwei machst wird a wieder zu b und du kannst das a zurück geben.
Hoffe das war jetzt einigermaßen verständlich auch wenn es nicht die korrekte mathematische Schreibweise ist.

Gruß
Fabian