ggT und KgV von 2 Zahlen berechnen - absolut keine Ahnung

[Klaus01]

Zitat:

Beim euklidischen Algorithmus wird in aufeinanderfolgenden Schritten jeweils eine Division mit Rest durchgeführt, wobei der Rest im nächsten Schritt zum neuen Divisor wird. Der Divisor, bei dem sich Rest 0 ergibt, ist der größte gemeinsame Teiler der Ausgangszahlen. Beispiel:
1071 : 1029 = 1 Rest 42
1029 : 42 = 24 Rest 21
24 : 21 = 2 Rest 0
Somit ist 21 der größte gemeinsame Teiler von 1071 und 1029.

Aus der Erklärung: "in aufeinanderfolgenden Schritten"
Hört sich nach Schleife an.
Wir wissen aber nicht wie viele Schleifendurchgänge notwendig sind.
Daher kommt die For to Schleife nicht in Betracht.

Bleiben die repeat until und die while do Schleifen zu Auswahl.

Da wir mindestens einmal etwas berechnen müssen bietet sich die repeat until Schleife an.
Die Abbruchbedingung wird hier erst nach einem Schleifendurchlauf ermittelt.

Abbruchbedingung, aus der Erklärung "bei dem sich Rest 0 ergibt".

Delphi-Quellcode:

repeat

until rest = 0;

Was soll gemacht werden: "eine Division mit Rest durchgeführt"
Die Funktion die das in Delphi macht nennt sich mod.

rest := zahl1 mod zahl 2; Die Berechnung bauen wir dann in die Schleife ein;

Delphi-Quellcode:

repeat
  rest := zahl1 mod zahl2;
until rest = 0;

Im nächsten Schritt soll dann zahl2 durch den rest geteilt werden.

Delphi-Quellcode:

repeat
  rest := zahl1 mod zahl2;
  zahl1 := zahl2;
  zahl2 := rest;
until rest = 0;

Bauen wir das Ganze nun in eine Funktion ein:

Delphi-Quellcode:

function ggt(zahl1,zahl2: Integer):Integer;
var
  rest : Integer;
begin
  repeat
    rest := zahl1 mod zahl2;
    zahl1 := zahl2;
    zahl2 := rest;
  until rest = 0;  
end;

Nun benötigt die Funktion noch eine Ausgabe/Rückgabewert.

Wir benötigen den Divisior wenn die Division (zahl1 mod zahl2) den Rest 0 ergibt.
Wir merken uns immer den Divisior (zahl2), wenn der rest = 0 ist
wird result nicht mehr überschrieben.

Delphi-Quellcode:

function ggt(zahl1,zahl2: Integer):Integer;
var
  rest : Integer;
begin
  repeat
    result := zahl2;
    rest := zahl1 mod zahl2;
    zahl1 := zahl2;
    zahl2 := rest;
  until rest = 0;  
end;

Da eine Division durch Null nicht zulässig ist,
muss zahl2 auf 0 geprüft werden.

Delphi-Quellcode:

function ggt(zahl1,zahl2: Integer):Integer;
var
  rest : Integer;
begin
  if zahl2 > 0 then
    repeat
      result := zahl2;
      rest := zahl1 mod zahl2;
      zahl1 := zahl2;
      zahl2 := rest;
    until rest = 0
  else
    result := 0;
end;

Ich hoffe der Lösungsweg ist einigermaßen verständlich.

Grüße
Klaus