|
Thema: Größter gemeinsamer Teiler zweier Zahlen
Problem: Der größte gemeinsame Teiler soll mit Hilfe einer Rekursion ermittelt werden.
Programm: FUNCTION ggT(a, b:int64):int64;
BEGIN
IF b=0 THEN
ggT:a
ELSE ggT:=ggT(b, a mod b);
END;
Erklärung: Zunächst legt man in der ersten Zeile die Beiden Parameter fest, die für die beiden Zahlen, deren größter gemeinsamer Teiler gesucht ist, stehen.
Im eigentlichen Programmteil, also der Rekursion, wird zu Beginn abgefragt, ob der Parameter b den Wert "0" hat. Ist dies der Fall so wird Parameter a als ggT der Zahlen a und b ausgegeben. Andernfalls bekommt der Parameter a den Wert des Parameters b zugewiesen und Parameter b den Wert des Divisionsrests von a durch b. Diese Vertauschung wird solange fortgeführt bis Parameter b den Wert "0" beinhaltet und somit Parameter a ausgegeben werden kann.
Diese Vorgehensweise ist eine Beschleunigung des Euklid'schen Algorithmus. Der klassische Algorithmus lautet: Wenn CD aber AB nicht misst, und man nimmt bei AB, CD abwechselnd immer das kleinere vom größeren weg, dann muss (schließlich) eine Zahl übrig bleiben, die die vorangehende misst. (Aus Euklid, Die Elemente)
Man sieht also, dass Euklid damals das Problem geometrisch beschrieb. Er suchte ein gemeinsames Maß für die Längen zweier Linien. Gelöst hat er es, indem er stets die kürzere Linie von der längeren subtrahierte.
Da das Verfahren bei großen Differenzen sehr lange dauern kann, beschreibt man den Rest heutzutage nicht mehr als die Differenz sondern lediglich als Rest bei einer Ganzzahldivision der beiden Längen.
Beispiel: Gegeben seien die Werte a=792 und b=75. Nun wird überprüft, ob b den Wert 0 hat. Da dies nicht der Fall ist, wird b dem Wert a zugewiesen und b wird mit dem Divisionsrest von a und b überschrieben. Dieser Vorgang wird so lange wiederholt, bis b schließlich den Wert 0 zugewiesen bekommt. Jetzt wird a als ggT ausgegeben.
|
