ggT und KgV von 2 Zahlen berechnen - absolut keine Ahnung

[wolfgang_SV]

ok.. da hab ich ein wenig voreilig was zusammengehauen
hier gibt es die mathematischen Definitionen..


http://www.iti.fh-flensburg.de/lang/...n/zahlenth.htm

aber hier wird klar, dass a mod b (für a aus Z (ganze Zahlen ) und b aus N ( natürliche Zahlen )) kein negatives Ergebnis liefert
auch wenn a negativ sein sollte.

genauso ist ggt(a,b) per Definition immer positiv..

Ja und die 0 ist natürlich keine natürliche Zahl !!!!

[Amateurprofi]

Zitat von gammatester:

Zitat von wolfgang_SV:

@gammatester

bez. Mathematik und natürliche Zahlen

Die Division mit Rest oder der Divisionsalgorithmus ist ein mathematischer Satz aus der Algebra und der Zahlentheorie. Er besagt, dass es zu zwei Zahlen n und m <>0 aus N ( natürliche Zahlen ) eindeutig bestimmte Zahlen a und b gibt für die gilt :

n=a*m +b ; 0<=b<m

Wenn Du schon Wiki wörtlich zitierst, dann bitte richtig (Quellenangabe könnte nicht schaden) und ohne verfälschende Zusätze. Da steht eben nicht "(natürliche Zahlen)". Mit diesem von Dir frei erfundenen Zusatz ist der Satz nämlich falsch, wie man leicht an der eindeutigen Darstellung der Division 3 durch 5 sieht: 3 = 0*5 + 3. Aber als nächstes willst Du wahrscheinlich noch sagen, daß 0 natürlich eine natürliche Zahl ist.

@gammatester:
Kann es sein, daß du dich hier etwas zu weit aus dem Fenster lehnst?
Bei der obigen Definition steht der Zusatz "(natürliche Zahlen)" so zwar nicht in Wiki, trotzdem ist er korrekt. Der Zusatz, so wie er im Text steht, bezieht sich auf die Zahlen n und m (in deinem Beispiel 3 und 5) und nicht auf die Zahlen a und b (in deinem Beispiel 0 und 3).

[Sir Rufo]

Zitat von 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.

Zitat von 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...

Mir ist es doch völlig wurscht, was a mod b zurückliefert, weil es geht hier um die Definition von ggT und da ist die Definition nun mal so.

Ansonsten musst du dir deine eigene Definition von ggT machen (ggT_SV). Da kann dann meinetwegen alles sein, wie du möchtest.
Auch das wäre mir wurscht

Somit würde die korrekte Version von ggT (nach der gültigen mathematische Definition) wie folgt sein:

Delphi-Quellcode:

function ggT( a, b : integer) : integer;
  var
    aa, ab : integer; 
    r : integer;
  begin

    // ggT( 0, 0 ) ist nicht definiert und somit nicht zulässig

    if ( a = 0 ) and ( b = 0 ) then
      raise Exception.Create( 'Kein Wert darf 0 sein!' );

    // das dürfen wir denn ggT( -a, b ) = ggT( a, b )

    aa := abs( a );

    // auch das dürfen wir, denn es gilt ggT( a, b ) = ggT( b, a )
    // und ggT( -a, b ) = ggT( a, b )
    // daraus folgt ggT( a, -b ) = ggT( a, b )
    // und daraus folgt auch ggT( -a, -b ) = ggT( a, b )

    ab := abs( b );

    if ( aa = 0 ) or ( ab = 0 ) then
      begin
        if ( aa = 0 ) then
          Result := ab
        else
          Result := aa;
      end
    else
      begin
        repeat
          r := aa mod ab;
          aa := ab;
          ab := r;
        until r = 0;

        result := aa;
      end;
  end;

[wolfgang_SV]

Du hast ja vollkommen recht..

das was ich nur zum Ausdruck bringen wollte ist, dass der pascal-befehl
mod negative Ergebnisse liefert, was mathematisch nicht definiert ist.

Deshalb muß der Programm-Code also erweitert werden, damit ein positives Ergebnis herauskommt.

Ob man nun die Eingangsparameter , so wie du es machst, in positive Zahlen umwandelt oder die Ausgabe in eine positive Zahl umwandelt ist eigentlich egal...

Obwohl ich meine Version favorisiere, denn ein Befehl ist weniger als zwei, denn wir wollen doch möglichst ökonomisch programmieren.

[gammatester]

Zitat von Amateurprofi:

Zitat von gammatester:

@gammatester:
Kann es sein, daß du dich hier etwas zu weit aus dem Fenster lehnst?
Bei der obigen Definition steht der Zusatz "(natürliche Zahlen)" so zwar nicht in Wiki, trotzdem ist er korrekt. Der Zusatz, so wie er im Text steht, bezieht sich auf die Zahlen n und m (in deinem Beispiel 3 und 5) und nicht auf die Zahlen a und b (in deinem Beispiel 0 und 3).

Ich lehne mich nicht aus dem Fenster, schon gar nicht zu weit. Wiki sprich nur von Zahlen, und wenn nichts weiter gesagt wird, nimmt man doch an, daß alle aus der gleichen Menge sind. Der Zusatz kann sich übrigens nicht sinnvoll auf m beziehen, denn warum solche man extra fordern, daß eine natürliche Zahl ungleich 0 ist.

Aber inzwischen scheint ja Einigkeit zu bestehen, auch der genannte Link ist nach erstem Überfliegen brauchbar und er listet sogar ggt(0,a) = abs(a) und ggt(0,0)=0. Dies sind völlig legale Werte und sollten nicht ad hoc ausgeschlossen werden (wie soeben wieder in einem Parallelbeitrag). Das alles wird in meiner Funktion schon gerücksichtigt. (Sie ist leider trotzdem noch nicht perfekt, da der Wert -Maxint-1 nicht richtig behandelt wird).

[Connor Temple]

Delphi-Quellcode:

unit Unit1;

interface

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

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

var
  Form1: TForm1;

implementation

{$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
var Teiler, z1, z2, ggT, kz, gz :Integer;
begin
z1 := StrToInt (Eingabe1.Text);
z2 := StrToInt (Eingabe2.Text);

if z1 < z2
  then
     begin
      kz := z1;          // kleinste und größte Zahl bestimmen
      gz := z2;
     end
  else
    begin
      kz := z2;
      gz := z1;
    end;
  Teiler := kz + 1;      // Teiler Steuervariable

  ggt := 0;
  For Teiler := 1 to kz do
      if (((kz mod Teiler) = 0) and ((gz mod Teiler) = 0))
         then ggT := Teiler;
  Ergebnis.Caption := IntToStr(ggT);

end;

end.

Ist der Code aus der Schule, für den ggT, aber für den KgV, wie müsste ich den da verändern?

[Klaus01]

kgv:= abs(z1*z2) div ggt(z1,z2) Quelle: http://de.wikipedia.org/wiki/Kleinst...mes_Vielfaches

Aus diesem Grund wäre es auch von Vorteil wenn ggt ein Funktion wäre
und nicht wie in Deinem Code vollständig in der ButtonClick Methode deklariert wird.

Grüße
Klaus

[wolfgang_SV]

@Connor

na das ist ja umständlich...

und auch noch fehlerhaft..

gib mal eine negative Zahl ein....

PS Gruß an deinen Mathelehrer !?

[Sir Rufo]

Zitat von wolfgang_SV:

@Connor

na das ist ja umständlich...

und auch noch fehlerhaft..

gib mal eine negative Zahl ein....

PS Gruß an deinen Mathelehrer !?

Das wird hier wohl der Info-Lehrer verbrochen haben, was die Sache an sich aber auch nicht besser macht

[wolfgang_SV]

@Connor

sagen wir mal so :
wenn man den euklidischen Algorithmus nicht kennt, dann ist der Ansatz gar nicht mal so verkehrt, wenn man von der rudimentären Vorstellung des ggT ausgeht. Nämlich : Suche die größtmögliche Zahl, die a und b ohne Rest teilt...
Wenn man dann davon ausgeht, dass a und b positive Zahlen sind, ist euer Programm schon in Ordnung..

Nur mit den negativen Zahlen.. Warum habt ihr nicht den Tip von unserem Sir Rufo übernommen ( abs(a) und abs(b) ) ; dann klappt's auch mit negativen Zahlen ..


nach dem Motto :
kaum macht man's falsch, meldet sich Sir Rufu