Hallo,
als Aufgabe in einem Pascal(-Anfänger)-Kurs muß ich ein Programm schreiben, daß den größten gemeinsamen (ganzzahligen) Teiler von 2 beliebigen Zahlen berechnet und ausgibt.
Leider habe ich in diesem Bereich der Mathematik wenig Ahnung, so daß mir die Grundlage fehlt…
Hat jemand ein bereits fertiges Programm bzw. ein paar grundlegende Tips zur Berechnung?
Vielen Dank für Hinweise,
Martin
Siehe Delphi-Forum [o.T.]
.
hi,
sorry, es geht mit nicht nur ums programmieren, sondern um die mathematische grundlage…
hab damals in der schule wohl gefehlt 
tschüss
martin
Hat jemand ein bereits fertiges Programm bzw. ein paar
grundlegende Tips zur Berechnung?
Du mußt beide zahlen in Primfaktoren zerlegen und alle gemeinsamen Primfaktoren multiplizieren. Wenn Du beispielsweise die Zahlen 30 und 132 hast, dann lauten die Primzahlzerlegungen
120 = 2*2*2*3*5
132 = 2*2*3*11
Da in beiden Zahlen zweimal der Faktor 2 und einmal der Faktor 3 übereinstimmt, lautet der größte gemeinsame Teiler 2*2*3=12.
Hallo Martin
sorry, es geht mit nicht nur ums programmieren, sondern um die
mathematische grundlage…
Am einfachsten geht das programmtechnisch wohl mit dem euklidischen Algorithmus:
Leider weiß ich nichts über die „mathematischen“ Voraussetzungen, die Du mitbringst. Da Du das ganze programmieren mußt, mach ich die Herleitung gleich mal allgemein. (Beispiele können auf Nachfrage nachgeliefert werden.)
Erst mal zur „Theorie“:
Nennen wir die beiden Zahlen, von denen der größte gemeinsame Teiler bestimmt werden soll, mal n_1 und n_2. Hierbei sei n_1 > n_2. (Also müssen die Zahlen zuerst der Größe nach sortiert werden)
Nun kann man die größere Zahl immer in der Form:
n_1 = k_1 * n_2 + R_1 mit Rest R_1 zwischen 0 und n_2-1 schreiben (Rest n_2 würde ja bedeuten, daß die Zahl n_1 durch n_2 teilbar gewesen wäre)
oder anders ausgedrückt:
n_1 : n_2 = k_1 Rest R_1 (Ganzzahl oder Integerdivision liefert k_1)
Nun betrachten wir nochmal die erste Gleichung:
n_1 = k_1 * n_2 + R_1
Der gesuchte größte gemeinsame Teiler teilt links n_1 und rechts n_2. Wenn die Gleichung stimmen soll, teilt also der gesuchte größte gemeinsame Teiler auch R_1. (Nur dann wäre auch rechts ggT ausklammerbar)
Also wissen wir nun, daß der ggT n_2 und auch R_1 teilt und können nun genau dasselbe Verfahren mit n_2 und R_1 wiederholen. (Schleife programmieren)
n_2 = k_2 * R_1 + R_2
Das ganze nochmal:
R_1 = k_3 * R_2 + R_3
…
In jedem Schritt werden die Reste bei der Division kleiner, so daß das Verfahren automatisch irgendwann mit dem Rest 0 abbricht. (Abbruchbedingung)
Hoffe Dir geholfen zu haben
Helga
Hat jemand ein bereits fertiges Programm bzw. ein paar
grundlegende Tips zur Berechnung?Du mußt beide zahlen in Primfaktoren zerlegen und alle
gemeinsamen Primfaktoren multiplizieren.
Das ist die Loesung einer einfachen Aufgabe (euklidischer Algorithmus, logarithmische Anzahl von Divisionen mit Rest) mit einem hochkomplexen Verfahren, welches im wesentlichen auf einem brute-force-Ansatz basiert. Viel Spass beim Programmieren.
Ciao Lutz
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]