Dezimal in dual, rekursiv: die Dualzahl in einer Zeile

Die Aufgabe

Aufgabe 10.4

In Aufgabe 6.3a wurde ein Programm zur Umwandlung einer natürlichen Zahl von der Dezimaldarstellung in die Dualdarstellung entwickelt. Es wurde der Einfachheit halber pro Zeile eine Ziffer der Dualzahl ausgegeben, beginnend mit der niedrigstwertigen.

Um die Ausgabe nun so zu gestalten, dass die resultierende Dualzahl in einer Zeile geschrieben wird und die niedrigstwertige Stelle wie üblich rechts angeordnet ist, wird die Umwandlung mit Hilfe der Rekursion realisiert. Es dürfen die mathematischen Funktionen Division und Rest (modulo) verwendet werden.

Vervollständigen Sie die vorgegebene Datei A10_4.java.

Die vorgegebene Datei A10_4.java:

1class A10_4 {2 3    static void printDual (int x) {4        // Ergänzen Sie hier den fehlenden Code5    }6 7    public static void main (String[ ] args) {8        Out.print("Bitte geben Sie eine Zahl aus N0 ein: ");9        int n = In.readInt();10        printDual(n);11        Out.println();12    }13}

In Aufgabe 6.3a kam jede Ziffer in eine eigene Zeile, die letzte Ziffer zuerst. Für 13 stand da untereinander 1, 0, 1, 1. Jetzt soll 1101 in einer Zeile stehen, so wie man eine Dualzahl schreibt. Die Vorlage gibt main schon vor. Zu schreiben ist nur der Rumpf der Methode printDual, und zwar rekursiv.

Erlaubt sind die ganzzahlige Division / und der Rest %(modulo). Für ganze Zahlen schneidet / die Nachkommastellen ab: 13 / 2 ist 6. 13 % 2 ist der Rest 1. In der Divisionsmethode heißen dieselben Rechnungen x div 2 und x mod 2: x div 2 ist in Java x / 2, x mod 2 ist x % 2.

Merke: Bei einer rekursiven Methode entscheidet die Reihenfolge im Rumpf. Was vor dem Selbstaufruf steht, passiert auf dem Hinweg; was danach steht, auf dem Rückweg, also in umgekehrter Reihenfolge.

Rückblick: was die Divisionsmethode liefert.
Die Idee: erst der vordere Teil, dann die letzte Ziffer.
Der Basisfall: x kleiner als 2.
Erst aufrufen, dann ausgeben.
Der Ablauf für 13.
Das fertige Programm testen.

Rückblick: was die Divisionsmethode liefert

x	x div 2	x mod 2
13	6	1
6	3	0
3	1	1
1	0	1

Die Divisionsmethode teilt die Zahl immer wieder durch 2, bis 0 herauskommt. Jeder Rest ist eine Ziffer der Dualzahl. Der erste Rest ist die letzte Ziffer (die niedrigstwertige Stelle, ganz rechts), der letzte Rest die erste.

Ein Programm, das jeden Rest sofort ausgibt, schreibt die Ziffern darum verkehrt herum. In 6.3a war das so verlangt: eine Ziffer je Zeile, die niedrigstwertige zuerst.

Aus Aufgabe 6.3 („Dezimal in dual mit der Divisionsmethode: do-while und for“): Dort gab eine Schleife x % 2 aus und rechnete dann x = x / 2, bis x gleich 0 war. Für 13 kamen so die Ziffern 1, 0, 1, 1, also die letzte zuerst.

Die Idee: erst der vordere Teil, dann die letzte Ziffer

vorderer Teil = Dualzahl von x / 2, letzte Ziffer = x % 2

13 = 2 \cdot 6 + 1 \quad\Rightarrow\quad 13_{10} = \underbrace{110}_{6_{10}}\,1_2

Die kleine Zahl unten an einer Zahl nennt ihre Basis: 13₁₀ ist 13 im Zehnersystem (dezimal), 1101₂ dieselbe Zahl im Zweiersystem (dual). Die erste Zeile der Tabelle sagt: 13 = 2 · 6 + 1. Die letzte Ziffer von 13 ist der Rest 1. Alle Ziffern davor sind die Dualzahl von 6, nämlich 110. Zusammen: 110 und dahinter 1 ergibt 1101.

Um 13 auszugeben, gibt man also zuerst 6 in dual aus und hängt dann die 1 an. „6 in dual ausgeben“ ist dieselbe Aufgabe für eine kleinere Zahl. Genau dafür ruft printDual sich selbst auf: mit x / 2.

Schritt 0Die Aufgabe

Schritt 1Rückblick: was die Divisionsmethode liefert

Schritt 2Die Idee: erst der vordere Teil, dann die letzte Ziffer

Abbildung 1

Die Aufgabe

Rückblick: was die Divisionsmethode liefert

Die Idee: erst der vordere Teil, dann die letzte Ziffer