 |
|||
| HSG |
|
Algorithmus von Euklid
Python
def ggt(a,b):
"""
berechnet iterativ den ggt von a und b
"""
while b > 0:
(a,b) = (b,a%b)
return a
def ggtr(a,b):
"""
berechnet rekursiv den ggt von a und b
"""
if b == 0:
return a
else:
return ggtr(b,a%b)
Wieso funktioniert der euklidische Algorithmus?
Ersetzt man a durch a0 und b durch a1, so stellt sich der Algorithmus als eine Folge von Gleichungen dar.
a0 = a1q1 + a2 mit 0 ≤ a2 < a1
a1 = a2q2 + a3 mit 0 ≤ a3 < a2
a2 = a3q3 + a4 mit 0 ≤ a4 < a3
⁝
an-2 = an-1qn-1 + an mit 0 ≤ an < an-1
an-1 = anqn + an+1
Man erhält eine absteigende Folge von Resten a1 > a2 > a3 > ... . Da es unterhalb von a1 nur endlich viele Zahlen ≥ 0 gibt und die Reste alle ≥ 0 sind, muss es ein n mit der Eigenschaft an+1 = 0 geben. Die letzte Gleichung zeigt an|an-1. Damit und mit der vorletzten Gleichung folgt an|an-2. Analog erhält man an|an-3 ,..., an|a1, an|a0 . Damit ist klar, dass (1) an|ggt(a0,a1) gilt. Umgekehrt zeigt die erste Gleichung von oben, dass der ggt(a0,a1) auch a2 teilt. Aus der zweiten Gleichung folgt, dass der ggt(a0,a1) auch a3 teilt. Setzt man die Schlussweise fort, so erhält man schließlich (2) ggt(a0,a1)|an. Aus (1) und (2) folgt
an = ggt(a0,a1).
Delphi
function ggt(a,b : int64) : int64;
var
r : int64;
begin
a := abs(a); b := abs(b);
r := b;
while r > 0 do
begin
r := a mod b;
a := b;
b := r;
end;
result := a;
end;