kleinstes gemeinsames vielfaches finden

Hallo,

wie programmiert man ein kleines Tool, dass das (a) kleinste bzw. (b) größte gemeinsame Vielfache berechnen kann. Ich würde um Pseudocode bitten; sollte es hier sogar einen Pascalhelden geben, dann bitte in Pascal!

Danke.

google

Gary

Hi!
(b) Das größte gemeinsame Vielfache gibt es nicht!
Vielleicht meintest du den größten gemeinsamen Teiler

// Pseudo-Code:
function ggt(a,b):
MachBeideWertePositiv()
for() // Endlosschleife
begin // Da du anscheinend in Pascal proggst
if(a ist 0)
return b;
b = b mod a;
if(b ist 0)
a = a mod b;
end; // for

(a) kleinstes gemeinsames Vielfaches

// Pseudo-Code
function kgv(a,b)
if(a ist 0) oder (b ist 0)
return 0;
a = a div ggt(a,b);
b = b*a;
if (b ist kleiner 0)
return -b;
else
return b;

WebFritzi

Ich versuch mal, die ggT-Funktion in Pascal zu kloppen. Schlagt mich, wenn's falsch ist:

Function ggT(a,b:integer):integer;
begin
   a := abs(a);
   b := abs(b);
   while a <> 0 
   begin 
      b = b mod a;
      if b = 0 then a = a mod b;
   end;
   ggT = b;
end;

kwoTx

b:=7 mod 14 --> b=7
mit freundlichem gruß von der endlosschleife

so vielleicht?

uses crt;

function ggt(a,b:word):word;
var result:word;
begin
  while a <> 0 do begin
    result := b mod a;
    if result = 0 then begin
      ggt:=a;
      a:=0;
    end else begin
      b:=a;
      a:=result;
    end;
  end;
end;

var zahl1,zahl2:word;

begin
  repeat
  writeln('geben sie zwei zahlen zwischen 1 und 65535 ein:');
  readln(zahl1,zahl2);
  until (zahl1<>0) and (zahl2<>0);
  writeln('der ggT von ',zahl1,' und ',zahl2,' ist ', ggt(zahl1,zahl2));
  readln;
end.

Gary

Original erstellt von WebFritzi:
**Schlagt mich, wenn's falsch ist:
**

Werd ich tun, du hast meinen Algo falsch übersetzt.

Function ggT(a,b:integer):integer;
begin
   a := abs(a);
   b := abs(b);
   while 1 { Ich weiß nicht, wie man eine Endlosschleife macht }
   begin 
      if a = 0 then
          ggT = b;
      b = b mod a;
      if b = 0 then
          ggT = a;
      a = a mod b;
   end;
end;

kwoTx hat völlig recht, dein PC würde sich mit deinem Algo bei 7 mod 14 aufhängen.

(Ich habe schon lange nicht mehr in Pascal programmiert, aber bis auf die Schleife müsste es stimmen.)

WebFritzi

Ich habe deinen Pseudocode genauso übersetzt wie er da steht. Setz mal b=7 und a=14. Es wird das Gleiche herauskommen. Und mal zum Stil: Endlosschleifen sind scheiße! Mach lieber eine ordentliche Ausgangsbedingung!

Gary

Sorry, Sorry, Sorry. Ich hab im ersten Post eine Zeile vergessen (Weil man beim Posten keine Tabs machen kann!!).

// Pseudo-Code:
function ggt(a,b):
MachBeideWertePositiv()
for() // Endlosschleife
begin // Da du anscheinend in Pascal proggst
  if(a ist 0)
    return b;
  b = b mod a;
  if(b ist 0)
    return a; // Diese Zeile hab ich vergessen.
  a = a mod b;
end; // for

<edit>
Welche Abbruchbedingung soll ich nehmen:
a == 0 ?
Da hab ich b vergessen.
b == 0 ?
Da hab ich a vergessen.
(a == 0) && (b == 0) ?
Da müsste ich nach der Schleife wieder prüfen, ob jetzt b oder a gleich Null ist, und dann das jeweils andere zurückgeben.

==> Alle drei Versionen sind ineffizient.

Und noch was zum Thema Stil: Es kommt nicht immer auf den Stil an. Wenn ich mich jetzt entscheiden muss, ob ich den Stil oder die Effizienz bevorzugen soll, gewinnt immer die Effizienz. Ich behaupte aber nicht, das Stil nicht wichtig ist.
Und... wieso ist eine Endlosschleife schlechter Stil?
Ich hab doch meine Abbruchbedingungen. Nur stehen sie nicht im Schleifenkopf. Na und.

[ Dieser Beitrag wurde am 18.12.2002 um 21:10 Uhr von Gary editiert. ]