Suche Algorithmus, um kgV und ggT zu bestimmen

Computer: Software & Programmierung Delphi & Pascal
#1

Hallo!

Ich möchte auf Pascal ein Mathematikprogramm schreiben. Leider bin ich beim Bestimmen von kgV und ggT bisher noch nicht auf einen ordentlichen Algorithmus gekommen. Kann mir jemand weiterhelfen?

Es wäre schön, die Lösung in einem Struktogramm aufgezeigt zu bekommen!

#2

bin ich beim Bestimmen von kgV und ggT bisher noch nicht auf
einen ordentlichen Algorithmus gekommen.

Hi Christoph,

da der ggT und der kgV über die Beziehung

ggT(a, b) \* kgV(a, b) = a \* b

miteinander verknüpft sind, kannst Du immer sofort das kgV ausrechnen, wenn Du den ggT hast.

Wie man den ggT zweier Zahlen „schnell“ ausrechnen kann, ist seit ca. 2300 Jahren bekannt. Euklid entdeckte folgende Rekursionsformel:

ggT(a, b) = a für b = 0
 ggT(a, a mod b) für b \> 0 
("Euklidischer Algorithmus")

Da kannst Du nun direkt eine rekursiv arbeitende Pascal-Funktion draus machen. Die nichtrekursive (also mit einer Schleife arbeitende) Variante sieht so aus:

FUNCTION CalculateggT (a, b: INTEGER): INTEGER;
VAR h: INTEGER;
begin
 h := 1;
 WHILE (h\>0) DO
 begin
 h := a MOD b;
 a := b;
 b := h
 end;
 Result := a
end;

Zum Euklidischen Algorithmus gibt’s etliche Seiten im Netz – bei Interesse einfach mal von ner Suchmaschine Gebrauch machen.

Mit freundlichem Gruß
Martin

#3

ggT:

gegeben sind die Zahlen A, B mit A>B.

  1. Bilde den Rest der Division der größeren duch die kleinere Zahl: M = A mod B

  2. Subtrahiere den Rest von der kleineren Zahl: N = B - M

  3. Ist B ohne Rest durch N teilbar ?: If B mod N = 0:
    Ja: N ist der ggT
    Nein: setze A := B und B := N, weiter bei 1)

kgV:

kgV := A*B / ggT

Das war auf die Schnelle - ich hoffe, es ist richtig.

Gruß
Jochen

#4

Vielen Dank Euch beiden!