wie genau programmier i das GGT?

[Scryless]

also,ich schätz zum Programmieren von Brüchenkürzen,benötige ich das GGT,doch wie genau programmier ich das,ist mir total unbekannt,kann mir das jemand in anfänger language erklären und eine Pozedur angeben.

Das GGt (größter gemeinsamer Teiler) würd ich gern bei deisem Bruchrechner einsetzen können und zwar in den Befehl (Clickverfahren) "Kürzen"

THAnKS


P.s (ich sitze hier und bekomme Kürzvorschläge zum Programmieren,doch jedes MAL erscheint ne Fehlermeldung...verdammt!

Ich brauch Hilfe!!

siehe DOWNLOAD..

[Christian S.]

Hallo!

Hiermit berechnest Du den ggT mittels des Euklidischen Algorithmus. Du musst Dir lediglich noch Gedanken drüber machen, was passiert, wenn Zähler oder Nenner kleiner Null sind.

Delphi-Quellcode:

function ggT(zaehler, nenner : Integer) : Integer;
VAR r : INTEGER;
begin
  if nenner = 0 then
  begin
    result := 0;
    exit;
  end;

  while nenner > 0 do
  begin
    r := zaehler mod nenner;
    zaehler := nenner;
    nenner := r;
  end;

  result := zaehler;
end;

MfG
Peter

[Niels]

Ich hab hier noch ne kurze Version von ggT. Ist halt rekursiv und deshalb vieleicht net so einfach verständlich.

Delphi-Quellcode:

function ggt(a,b:longint): longint;
begin
  if b = 0 then result := a;
  else
  result := ggt(b,a mod b);
end ggt;

[evilseven]

Gibt es eigentlich auch eine Möglichkeit, das Ganze ohne Integer zu programmieren? So funktioniert das Kürzen nämlich für größere Zahlen nicht.

[Niels]

Moin,
du kannst int64 benutzen, da sind die Zahlen ein bisschen größer.

MfG Niels

[evilseven]

Das Problem ist nur, dass ich gerade einen Algorithmus habe, der mit SEHR großen Zahlen arbeitet, da nützt Int64 leider auch nichts. Bin noch am Suchen einer Lösung.

[CalganX]

Hi,
da wirst du dir wohl selber einen [dp="Langzahlarithmetik"]Typen für Langzahlarithmetik[/dp] schreiben müssen. Bzw. nach selbigem suchen (bspw. bei Torry).

Chris

[negaH]

@evilseven,

den ggT = GCD = Greatest Common Divisor, kannst du so wie oben gezeigt auch auf größere Zahlen adaptieren. Der Algorithmus selber bleibt also gleich. Du benötigst also eine Bibliothek die es dir ermöglicht mit sehr großen Zahlen zu rechnen. Nun, da deine Frage davon ausging das du einen ggT() für sehr große Zahlen benötigst gehe ich mal davon aus das du schon eine solche "BigNum", "Large Integer" Library benutzt.

Der obige Algorithmus ist die einfachste Form des GCD, der euklidsche Algorithmus. Gute Large Integer Librarys nutzen einen anderen Algorithmus der nach Lehmer oder Sorensen arbeitet. Der euklidsche Algo. extrahtiert von rechts nach links, also vom LSB zum MSB der Zahlen. Die Methode nach Lehmer oder Sorenson arbeiten aber umgedreht, sie berechnen die Subprodukte von Oben nach Unten, sprich vom MSB zum LSB. Dadurch sind diese Verfahren weit effizienter. Sie bauen sozusagen eine Verhältnissgleichung der MSB's beider Zahlen zueinander auf und reduzieren dann beide Zahlen so lange bis der GCD gefunden wurde. Gerade mit sehr großen Zahlen führt dies zu einer drastischen Beschleunigung des GCD.

Gruß Hagen