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

[wolfgang_SV]

Du haßt hier was vergessen, was sehr wichtig ist !

Man muß sicherstellen,dass der Divisor die kleinere Zahl ist.
Auf Null überprüfen reicht nicht.

PS. braucht man doch nicht .. mod ist in dem Sinne keine echte Division...
Sie liefert ja lediglich die Restklasse ....

[gammatester]

Zitat von Klaus01:

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

Mag ja sein, aber leider ist er ziemlich falsch. Deine Funktion bietet noch nicht einmal die Symmetrie ggt(a,b)=ggt(b,a), wie man leicht an ggt(2,-2) = 0 und ggt(-2,2) = 2 sieht. Außerdem werden leider wieder einmal völlig falsche Werte für negative Zahlen geliefert, einerseits mit voller Absicht: ggt(a,b) = 0 für b <= 0! (Warum das ganze?). Andererseits (wohl) aus Unkenntnis der mod-Funktion: ggt(-5,2) = -1. Eine verbesserte Version könne so aussehen:

Delphi-Quellcode:

 function ggt(zahl1,zahl2: integer): integer;
var
  rest: integer;
begin
  zahl1 := abs(zahl1);
  zahl2 := abs(zahl2);
  while zahl2>0 do begin
    rest := zahl1 mod zahl2;
    zahl1 := zahl2;
    zahl2 := rest;
  end;
  ggt := zahl1;
end;

[wolfgang_SV]

@gammatester

das was du nun erzählst ist völlig daneben..

nimm die funktion aus meinem ersten Programmbeispiel ..#5

ggt(a,b) liefert dasgleiche wie ggt(b,a)

sollten a oder b negativ sein , was von der mathematischen definition
bez. modulo gar nicht vorgesehen ist ( hier unterscheidet sich mal wieder Mathematik von programmier-sprachen)

dann sollte man so vorgehen :
c:=abs(ggt(a,b));

[wolfgang_SV]

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  StdCtrls;

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Edit2: TEdit;
    Button1: TButton;
    Label1: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

{$R *.DFM}

function ggt(a,b : integer) : integer;
  var r : integer;
  begin
 
  repeat
  r:= a mod b;
  a:=b;
  b:=r;
  until r=0;

  result:=a;
  end;

procedure TForm1.Button1Click(Sender: TObject);
  var a,b,c : integer;
  begin
  a:=strtoint(edit1.text);
  b:=strtoint(edit2.text);

  c:=abs(ggt(a,b));

  label1.caption:=inttostr(c);
  end;

end.

mehr sag ich jetzt nicht...
weil so geht es...
und wenn man jetzt für a oder b den wert 0 eingibt...
ok.. dann kann man das ja abfangen...

[gammatester]

Zitat von wolfgang_SV:

@gammatester

das was du nun erzählst ist völlig daneben..

Was ist völlig daneben? Ein fehlerhaftes Ergebnis meiner Funktion würde mir reichen.

Zitat von wolfgang_SV:

nimm die funktion aus meinem ersten Programmbeispiel ..#5

ggt(a,b) liefert dasgleiche wie ggt(b,a)

Wie man leicht sieht, beziehe ich mich auf Klaus (wer lesen kann, ist klar im Vorteil).

Zitat von wolfgang_SV:

sollten a oder b negativ sein , was von der mathematischen definition
bez. modulo gar nicht vorgesehen ist ( hier unterscheidet sich mal wieder Mathematik von programmier-sprachen)

dann sollte man so vorgehen :
c:=abs(ggt(a,b));

Ich 'erzähle' nichts, sondern zeige nur die Ergebnis von Klaus's letzter Funktion. Wenn Du meinst, daß ist 'daneben". dann stimmen wird ja überein. Wir stimmen allerdings nicht überein in folgenden Punkten:

- der ggt von negativen Zahlen und mod von negativen Zahlen ist selbstverständlich mathematisch vorgesehen

- Programmiersprachen unterscheiden sich darin nicht: mod ist zumindest in Pascal für negative Zahlen definiert. ggt nicht, muß also selbstgeschrieben werden. Aber möglichst richtig. Pascal mod und mathematisches mod unterscheiden sich leider. Pascal: -5 mod 3 = -2, mathematisch ist -5 mod 3 = 1. Der mathematische Rest a mod b für b > 0 ist nämlich: 0 <= a mod b < b. Was bei Pascal nun mal leider nicht der Fall. Wenn man einen mathematisch korrekten ggt via Euklidischem Algorithmus berechnen will muß man das berücksichtigen.

- c:=abs(ggt(a,b)) ist zwar richtig, aber nur wenn ggt schon halbwegs richtig ist, Klaus ' Funktion liefert ggt(-2,-2)=0.

[Sir Rufo]

Zitat von wolfgang_SV:

c:=abs(ggt(a,b));

Wieso von einer positiven Zahl noch den Absolutwert ermitteln?
Per Definition liefert ggT ein Ergebnis aus der Menge der natürlichen Zahlen und damit.

Weiterhin gilt:

Code:

ggT( -a, b ) = ggT( a, b )

Somit ist es absolut richtig von beiden Eingangsparametern die Absolutwerte zu nehmen.

Weiterhin gilt auch, dass keiner der Eingangswerte 0 sein darf, denn dann ist ggT nicht definiert.
In dem Falle müsste also korrekterweise eine Exception ausgelöst werden.

[wolfgang_SV]

falsch Sir Rufo..

gib doch einfach mal eine negative Zahl für a oder b ein..

und schau was a mod b dir zurückliefert...

[wolfgang_SV]

@gammatester

ok.. entschuldigung
habe die procedure von klaus01 soweit nicht getestet.
wenn seine funktion für ggt(a,b) einen anderen wert als ggt(b,a) liefert , abgesehen vom vorzeichen , ist sie natürlich schrott!!!

PS. obwohl auch das Vorzeichen müßte gleich sein

[Klaus01]

.. gut, dass ich mal wieder ein schlechtes Beispiel sein durfte..
Klaus