Theorieteil zum Exkurs Bruchrechnung
Der euklidische Algorithmus
Der größte gemeinsame Teiler
Dieser Begriff ist für das Kürzen von Brüchen wichtig. Betrachten wir einen einfachen Bruch wie 3/4. Diesen Bruch kann man nicht weiter kürzen. Was heißt eigentlich "kürzen"?
Erweitern und kürzen
Den Bruch 3/4 kann man erweitern, indem man sowohl Zähler wie auch Nenner mit der gleichen ganzen Zahl multipliziert, beispielsweise mit der Zahl 2. Man erhält dann den Bruch 6/8.
Umgekehrt kann man den Bruch 6/8 kürzen, indem man sowohl Zähler wie auch Nenner durch die gleiche ganze Zahl dividiert. Diese ganzzahlige Division muss jedoch "aufgehen", es darf kein Rest bleiben. Einen Bruch wie 7/8 kann man daher nicht kürzen. Die 7 als Primzahl kann nur durch 1 dividiert werden, was keinen Sinn macht, da dann nichts passiert, oder durch sich selbst, also durch 7. Der Nenner, die 8, kann aber nur durch die ganzen Zahlen 2 oder 4 dividiert werden, nicht aber durch die 7. Also kann man diesen Bruch nicht kürzen.
Größter gemeinsamer Teiler
Schauen wir uns den Bruch 15/20 an. Hier sieht man sofort, dass man den Bruch kürzen kann. Wenn wir sowohl Zähler wie auch Nenner durch 5 dividieren, erhalten wir den gekürzten Bruch 3/4. Wie kann jetzt aber ein automatisch ablaufender Algorithmus darauf kommen, die beiden Zahlen ausgerechnet durch die 5 zu dividieren?
Beispiel 1: 15/20
Betrachten wie alle Teiler des Zählers 15. Die Zahl 15 kann man ganzzahlig dividieren durch 1, 3, 5 und 15.
Die Teiler des Nenners 20 sind: 1, 2, 4, 5, 10 und 20.
Gemeinsame Teiler sind somit: 1 und 5.
Und der größte gemeinsame Teiler ist dann die 5.
Beispiel 2: 30/66
Teiler des Zählers 30: 1, 2, 3, 5, 6, 10, 15, 30.
Teiler des Nenners 66: 1, 2, 3, 6, 11, 22, 33, 66.
Gemeinsame Teiler: 1, 2, 3, 6.
Größter gemeinsamer Teiler: 6.
Also können wir Zähler und Nenner durch 6 dividieren, um den Bruch zu kürzen: 5/11.
Berechnung des ggT durch "Wegnahme der kleineren Zahl"
Euklid formulierte einen Algorithmus zur Berechnung des ggT, den man durch "wiederholte Wegnahme der jeweils kleineren Zahl von der größeren Zahl" beschreiben kann. Machen wir uns diesen Algorithmus am Beispiel 30/66 klar.
Beispiel 1: 30 / 66
Wir ziehen die kleinere Zahl von der größeren ab: 66 - 30 = 36.
Diesen Schritt können wir noch einmal wiederholen: 36 - 30 = 6.
Jetzt ist die 6 kleiner als die 30, also gehen wir genau umgekehrt vor. Wir subtrahieren die 6 von der 30. 30 - 6 = 24. Diesen Schritt kann man jetzt mehrfach wiederholen:
24 - 6 = 18, 18 - 6 = 12, 12 - 6 = 6, 6 - 6 = 0.
Wir sind jetzt bei der Null angekommen; also ist 6 das "gemeinsame Maß" der beiden Zahlen 66 und 30, der ggT.
Das Verfahren klingt gut, es sollte nicht allzu schwer sein, es algorithmisch umzusetzen. Aber erst wollen wir es noch einmal an einem anderen Beispiel testen.
Beispiel 2: 240 / 350
350 - 240 = 110
240 - 110 = 130, 130 - 110 = 20
110 - 20 = 90, 90 - 20 = 70, 70 - 20 = 50, 50 - 20 = 30, 30 - 20 = 10
20 - 10 = 10, 10 - 10 = 0.
Offensichtlich ist 10 der ggT der Zahlen 240 und 250, ein Kürzen des Bruchs führt also zu 24/35.
Berechnung des ggT durch Primfaktorenzerlegung
Prinzipiell kann man den ggT (größten gemeinsamen Teiler) über eine Zerlegung von Zähler und Nenner in Primfaktoren bestimmen.
Primfaktoren
Beispiel 1: 30 / 66
Betrachten wir eine Zahl wie 66. Man kann diese Zahl in ihre Primfaktoren zerlegen:
66 = 21 * 31 * 50 * 70 * 111
Die Primfaktorzerlegung für die Zahl 30 sieht so aus:
30 = 21 * 31 * 51 * 70 * 110
Zur Bestimmung des ggT nimmt man nun von jeder Primzahl den kleinsten Exponenten:
21 * 31 * 51 * 70 * 110 = 6
Beispiel 2: 240 / 350
240 = 24 * 31 * 51 * 70
350 = 21 * 30 * 52 * 71
Von jeder Primzahl wird der kleinste Exponent zur Bestimmung des ggT genommen:
21 * 30 * 51 * 70 = 10
Der Euklidische Algorithmus in Java
Vergleicht man die beiden hier vorgestellten Verfahren, so kommt man schnell zu dem Schluss, dass sich das klassische Verfahren von Euklid sehr gut für eine Java-Implementation eignet. Das andere Verfahren ist eher von theoretischem Interesse, bei einer mündlichen Abiturprüfung im Fach Informatik kann man mit der Kenntnis dieses Verfahrens sicherlich glänzen.
Natürlich könnte man nun eine while-Schleife nehmen und die jeweils kleinere Zahl solange von der größeren Zahl abziehen, bis entweder die Null dabei herauskommt (dann ist man auch schon fertig), oder bis ein Rest bleibt, der kleiner ist als subtrahierte Zahl. Kommen wir noch einmal auf unser Beispiel 1 zurück. Wie ziehen die kleinere Zahl von der größeren ab: 66 - 30 = 36. Diesen Schritt können wir noch einmal wiederholen: 36 - 30 = 6. Jetzt haben wir zwar nicht die Null - wir sind also noch nicht fertig - aber die 6 ist kleiner als die 30. Im nächsten Schritt ist also die 6 die kleine Zahl.
Man könnte dies javamäßig so formulieren:
while (gross >= klein)
{
gross = gross - klein;
}
Am Anfang ist 66 > 30. Die Schleifenbedingung ist also erfüllt, und daher werden die Anweisungen des Schleifenkörpers ausgeführt. Nach dem ersten Schleifendurchlauf hat gross den Wert 36. Damit ist die Schleifenbedingung immer noch erfüllt, und es kommt zu einem zweiten Schleifendurchlauf. Danach hat gross den Wert 6. Die Schleifenbedingung ist nicht mehr erfüllt, und die while-Schleife wird beendet.
Umständlich wäre jemand, der tatsächlich so programmieren würde. Wozu gibt es den Modulo-Operator in Java, der uns den Rest einer ganzzahligen Division liefert?
Der Modulo-Operator %
Der Modulo-Operator % liefert uns den Rest einer ganzzahligen Division. Wenn man zum Beispiel schreibt:
int rest = 66 % 30
So hat die Variable rest den Wert 6, denn 66 / 30 ist 2 Rest 6.
Beispiel 30 / 66
Schritt 1: 66 / 30 = 2 Rest 6
Schritt 2: 30 / 6 = 5 Rest 0
Der Algorithmus hält jetzt mit dem Ergebnis 6 an. 6 ist der ggT von 30 und 66.
Beispiel 1260 / 24
Schritt 1: 1260 / 24 = 52 Rest 12
Schritt 2: 24 / 12 = 2 Rest 0
Der Algorithmus hält jetzt mit dem Ergebnis 12 an. 12 ist der ggT von 1260 und 24.
Beispiel 240 / 350
Schritt 1: 350 / 240 = 1 Rest 110
Schritt 2: 240 / 110 = 2 Rest 20
Schritt 3: 110 / 20 = 5 Rest 10
Schritt 4: 20 / 10 = 2 Rest 0
Der Algorithmus hält also mit dem Ergebnis 5 an. 5 ist der ggT von 2.
Zurück zum Exkurs Bruchrechnung
Diese HTML-Seite wurde erstellt von Ulrich Helmich am 29. Dezember 2006.