Bruch kürzen mit einer Methode ggT nach Euklid

Die Aufgabe

Aufgabe 9.2

Schreiben Sie ein Programm A9_2, welches den Zähler und den Nenner eines Bruches einliest und dann den Bruch kürzt. Anschließend sind Zähler und Nenner des gekürzten Bruches auszugeben.

Zum Kürzen des Bruches wird der größte gemeinsame Teiler (ggT) des Zählers und des Nenners benötigt. Dessen Berechnung realisieren Sie nach dem Euklidischen Algorithmus, welcher in vorangegangenen Kapiteln mehrfach als Beispiel verwendet wurde, in einer Methode ggT. Der Methode werden Zähler und Nenner als Parameter übergeben, und die Methode liefert deren ggT als Ergebniswert zurück.

Gegeben sind zwei ganze Zahlen, der Zähler $z$ und der Nenner $n$ . Das Programm soll den Bruch $\tfrac{z}{n}$ so weit wie möglich kürzen und Zähler und Nenner des Ergebnisses ausgeben. Der größte gemeinsame Teiler heißt kurz ggT. Ihn soll eine Methode ggT berechnen, mit dem Euklidischen Algorithmus.

Als Beispiel dient $\tfrac{24}{36}$ ; die Aufgabe gibt keine Zahlen vor. Zwei Fälle regelt sie nicht, wir legen sie selbst fest: Bei Nenner 0 gibt das Programm eine Fehlermeldung aus. Bei negativen Zahlen steht das Minus am Ende im Zähler.

Merke: Teilt man Zähler und Nenner durch ihren ggT, ist der Bruch vollständig gekürzt. Ein kleinerer gemeinsamer Teiler würde nur einen Teil der Arbeit tun.

Klären, was Kürzen mit dem ggT heißt.
Den Euklidischen Algorithmus von Hand für 24 und 36 ausführen.
Die Methode ggT schreiben: erst den Kopf, dann den Algorithmus.
Das Hauptprogramm: einlesen, ggT aufrufen, teilen, ausgeben.
Sonderfälle: Nenner 0, negative Zahlen, Zähler 0.

Kürzen heißt: durch den ggT teilen

Zahl	Teiler
24	1, 2, 3, 4, 6, 8, 12, 24
36	1, 2, 3, 4, 6, 9, 12, 18, 36

Zähler und Nenner durch den ggT 12 geteilt

\mathrm{ggT}(24, 36) = 12, \qquad \frac{24}{36} = \frac{24 : 12}{36 : 12} = \frac{2}{3}

Ein Teiler einer Zahl teilt sie ohne Rest. Teilt man Zähler und Nenner durch dieselbe Zahl, bleibt der Wert des Bruchs gleich. Am meisten kürzt man mit dem größten Teiler, den beide gemeinsam haben.

Für 24 und 36 kann man alle Teiler aufschreiben. Gemeinsam sind 1, 2, 3, 4, 6 und 12; der größte ist 12. 24 durch 12 ist 2, 36 durch 12 ist 3. Bei großen Zahlen ist diese Liste mühsam; darum braucht das Programm ein schnelleres Verfahren.

Der Euklidische Algorithmus von Hand

jede Zeile: Rest berechnen, dann (a, b) durch (b, r) ersetzen

\begin{aligned} 24 \;\%\; 36 &= 24 \\ 36 \;\%\; 24 &= 12 \\ 24 \;\%\; 12 &= 0 \;\Rightarrow\; \mathrm{ggT}(24, 36) = 12 \end{aligned}

Der Algorithmus nutzt eine Regel: Ein gemeinsamer Teiler von $a$ und $b$ teilt auch den Rest $r$ von $a$ geteilt durch $b$ . Also kann man das Paar $(a, b)$ durch das kleinere Paar $(b, r)$ ersetzen, ohne dass sich der ggT ändert. Ist der Rest 0, teilt $b$ die Zahl $a$ ; dann ist $b$ selbst der ggT.

Auch umgekehrt geht nichts verloren: $a$ ist ein Vielfaches von $b$ plus $r$ . Ein gemeinsamer Teiler von $b$ und $r$ teilt also auch $a$ . Beide Paare haben genau dieselben gemeinsamen Teiler und damit denselben ggT.

Den Rest schreibt Java als a % b. Für 24 und 36: 24 durch 36 geht 0-mal, Rest 24. Damit tauschen $a$ und $b$ in der ersten Runde von selbst die Plätze. Dann 36 % 24 = 12 und 24 % 12 = 0: Der ggT ist 12.

Aus Skript 3, Folie 3-20 („Beispiel: Euklidischer Algorithmus“): a, b eingeben. Falls b > a, vertausche a und b. Teile a durch b, Rest r := a mod b. Falls r = 0, Ende mit ggT = b. Sonst ersetze a durch b und b durch r, weiter beim Teilen.

Runde	a	b	r = a % b
Start	?	?	?
1	?	?	?
2	?	?	?

Schritt 0Die Aufgabe

Schritt 1Kürzen heißt: durch den ggT teilen

Schritt 2Der Euklidische Algorithmus von Hand

Abbildung 1Kürzen und Euklid

Die Aufgabe

Kürzen heißt: durch den ggT teilen

Der Euklidische Algorithmus von Hand