ggt und kgv berechnung beliebig vieler zahlen

F34r0fTh3D4rk · Verfasst: Fr 25.11.05 17:13

Hallo erstmal, ich möchte ein programm schreiben, um beliebig viele brüche zu addieren (später auch subtrahieren usw), diese sollen dann als gekürzter bruch ausgegeben werden. zur berechnung des kgv und ggt gibt es ja das verfahren nach euklid, nur wie mache ich das mit beliebig vielen zahlen ?

ich habe ein record:

markieren

Delphi-Quelltext

1:
2:
3:
4:

type
  TBruch = record
    Zaehler, Nenner: integer;
  end;

in der procedure habe ich davon dann ein dynamisches array, aus diesem soll der kgv und der ggt aller nenner berechnet werden, geht das mit dem euklid verfahren, wie mache ich das ?

danke schonmal

GTA-Place · Verfasst: Fr 25.11.05 19:46

Ich würde glaub kein KGV / GGT ausrechnen, sondern einfach Nenner1 * Nenner2 und Nenner2 * Nenner1 (beim Zähler dann auch).
So hätte ich es schonmal auf dem gleichen Nenner. Dann kann ich den Zähler zusammenzählen und erstmal Zähler / Nenner versuchen.
Weiter würde ich glaub Brute-Forcing nehmen (ist nicht gut bei großen Zahlen, aber mir fällt im Moment nix besseres ein).

Ich kenne das Verfahren nach Euklid nicht.

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)

Amateur · Verfasst: Fr 25.11.05 19:51

ne kgv und ggt wird da auch ausreichen. ist nicht so kompliziert auszurechnen. den kgv kriegste ganz einfach wenn du ggt hast. der rest ist mathe und findet sich sicher im netz.
dann machste nenner1 und nenner2 := kgv und die zähler jeweils mal kgv/nenner.
is nur so ne idee keine ahnung ob alles stimmt

_________________
"Kein dummes Gerede. Kein Rumrätseln. Denkt an nichts anderes mehr, nur noch an das, was vor euch liegt. Das ist die wahre Herausforderung. Ihr müßt euch vor euch selbst schützen, Leute." (Rennes in "Cube")
Beiträge: >700

F34r0fTh3D4rk · Verfasst: Fr 25.11.05 22:35

jetzt habe ich ein problem :shock:

wenn ich den bruch 6/7 kürzen will, sollte da standartmäßig 6/7 bei rauskommen, rauskommt aber 3/3

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

function p_kuerzen(Bruch: TBruch): TBruch;
var
  ggt: integer;
begin
  ggt := p_ggt(Bruch.Zaehler, Bruch.Nenner);
  //
  showmessage(inttostr(ggt));  //ergibt bei 6/7 -> 1
  //
  if ggt = 1 then
    exit;
  result.Zaehler := Bruch.Zaehler div ggt;
  result.Nenner := Bruch.Nenner div ggt;
end;

an der markierten stelle kommt 1 heraus, also müsste die function an dieser stelle abgebrochen werden. und selbst wenn nicht, sollte da 6/7 bei rauskommen, woher kommen die 3/3 ?

So berechne ich den ggT:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

function p_ggT(a, b: integer): integer;
var
  x, y, r: Integer;
begin
  x := a;
  y := b;
  r := x mod y;
  while (r <> 0) do 
  begin
    x := y;
    y := r;
    r := x mod y;
  end;
  result := y;
end;

so sieht die anwendung aus:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

procedure TForm1.Button1Click(Sender: TObject);
var
  Bruch: TBruch;
begin
  Bruch.Zaehler := strtoint(edit1.text);
  Bruch.Nenner := strtoint(edit2.text);
  Bruch := p_kuerzen(Bruch);
  edit1.text := inttostr(Bruch.Zaehler);
  edit2.text := inttostr(Bruch.Nenner);
end;

und das hier nochmal zum testen der ggt funktion, die eigentlich 100% funktioniert:

markieren

Delphi-Quelltext

1:
2:
3:
4:

procedure TForm1.Button2Click(Sender: TObject);
begin
  showmessage(inttostr(p_ggt(6, 7)));
end;

wo liegt der fehler ? :shock:

Amateur · Verfasst: Fr 25.11.05 22:48

ich denk mal in der ggt berechnung. ich kenn den algo den du verwendet hast nicht aber ich poste einfach mal den den wir in der schule hatten. vielleicht gehts ja damit.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

function ggt(x,y:integer):integer;
 begin

    repeat
        while x>y  do
            x:=x-y;
        while y>x  do
            y:=y-x;
    until x=y;
    result:=x;
 end;

wobei x und y >0 sind...

_________________
"Kein dummes Gerede. Kein Rumrätseln. Denkt an nichts anderes mehr, nur noch an das, was vor euch liegt. Das ist die wahre Herausforderung. Ihr müßt euch vor euch selbst schützen, Leute." (Rennes in "Cube")
Beiträge: >700

F34r0fTh3D4rk · Verfasst: Fr 25.11.05 22:49

der ggt scheint ja zu stimmen, der ist 1 :shock:

Amateur · Verfasst: Fr 25.11.05 22:51

hast du ihn mal mit anderen werten probiert? nur so zur kontrolle dass das wenigstens klappt...
was ist der rückgabewert der funktion kürzen wenn du exit aufrufst? ist im moment noch das einzige was mir auffält.

_________________
"Kein dummes Gerede. Kein Rumrätseln. Denkt an nichts anderes mehr, nur noch an das, was vor euch liegt. Das ist die wahre Herausforderung. Ihr müßt euch vor euch selbst schützen, Leute." (Rennes in "Cube")
Beiträge: >700

F34r0fTh3D4rk · Verfasst: Fr 25.11.05 22:54

klar, brüche die man kürzen kann scheint er weitestgehend richtig zu kürzen und der ggt scheint immer zu stimmen. aus 8/4 macht er 2/1 und aus 4/8 1/2 das ist korrekt

wenn ich dann aber nochmal draufklicke, macht er wieder 3/3 draus, vielleicht ne variable nicht initialisiert oder so ?! an der variable ggt liegts net :!:

aus 3/3 macht er dann 1/1 und daraus wieder 3/3 usw ... :shock:

moment mal, ich glaube da fehlt noch das:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

function p_kuerzen(Bruch: TBruch): TBruch;
var
  ggt: integer;
begin
  result := Bruch;
  ggt := p_ggt(Bruch.Zaehler, Bruch.Nenner);
  if ggt = 1 then
    exit;
  result.Zaehler := Bruch.Zaehler div ggt;
  result.Nenner := Bruch.Nenner div ggt;
end;

Amateur · Verfasst: Fr 25.11.05 22:56

wenn du nochmal klickst ist ggt wieder 1 und es kommt exit... ich vermute dort den fehler dass die funktion dann was falsches zurückgibt...

_________________
"Kein dummes Gerede. Kein Rumrätseln. Denkt an nichts anderes mehr, nur noch an das, was vor euch liegt. Das ist die wahre Herausforderung. Ihr müßt euch vor euch selbst schützen, Leute." (Rennes in "Cube")
Beiträge: >700

F34r0fTh3D4rk · Verfasst: Fr 25.11.05 22:57

jetzt gehts, danke :wink:

jasocul · Verfasst: Sa 26.11.05 20:56

Um auf deine ursprüngliche Frage zurück zu kommen:
Den ggT von mehreren Zahlen würde ich rekursiv programmieren.
Immer den ggT von zwei Zahlen berechnen. Mit dem Ergebnis und der nächsten Zahl wieder den ggT berechnen. Das ganze solange, bis keine Zahlen mehr da sind oder der ggT sich nicht mehr verändert.

F34r0fTh3D4rk · Verfasst: Sa 26.11.05 21:20

hab ich auch so gemacht, danke

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme