Frage zu Java Rekursion (Dezimalzahl in das übergebene Zahlensystem umwandeln)?
Aaalso kann mir jemand helfen, wie diese Java Programmieraufgabe geht? Habe schon des öfteren mit rekursiven Methoden gearbeitet, jedoch habe ich keinen Ansatz wie ich das hier anstellen soll:
Schreiben Sie eine Methode int gibDarstellung(int zahl, int basis) die ohne Schleifen eine dezimale Zahl in die übergebene Basis umrechnet. Beispiel: (15, 2) wird zu 1111 (also wird quasi 15 in binär zurück gegeben.
Dahinter stand noch in klammern Horner-Schema.
Habe die Aufgabe aus einer Klausurrekonstruktion von einem anderen Studenten, könnte also sein, dass die Aufgabe in "echt" auch ein bisschen anders aussah.
4 Antworten
Klasse, vielen Dank. War eigentlich mega simpel... hätte nicht so schnell aufgeben sollen ;-) Für alle die es interessiert, habe es so gelöst:
public static long gibDarstellung(long zahl, int basis){ return (zahl <= 0) ? zahl % basis : zahl % basis + gibDarstellung(zahl / basis, basis) * 10; }
Eine Dezimalzahl ist nichts anderes als ein Polynom Summe(a_i 10^i)
Eine Binärzahl entsprechend Summe(a_i 2^i)
Wie kommt man an die Binärdarstellung? Man sucht die erste 2er-Potenz, die kleiner oder gleich der Dezimalzahl ist (hier 8) und legt los:
15:8 = 1 Rest 7 → nächster Durchlauf mit 7
7:4 = 1 Rest 3 → ...
Mit jedem Durchlauf wird der Exponent um 1 geringer, bzw. die Potenz durch die Basis geteilt. Die Quotienten und Reste müssen immer weitergetragen werden.
Aber nochmal zum Hornerschema. Der Nutzen liegt in der Vermeidung des Potenzierens:
15 = (1*8+7) = (1*8 + 1*4 + 1*2 + 1*1) = (((1*2)+1)*2+1)*2+1
Ein Weg vom Binärsystem ins Dezimalsystem würde mir leichter fallen.
Eine rekursive Funktion könnte vielleicht grob skizziert so aussehen (Pseudocode):
function string DezToBin(var iDez, var sKette, var iExp=10)
{
if(iExp>0)
return str(iDez \ iExp) + DezToBin(iDez % iExp, iExp-1); // \ = ganzzahlige Dividion
else
return "";
}Die Funktion muss mit einem möglichst hohen Exponenten als Startwert (Defaultwert) gestartet werden.
Bzw.
return str(iDez \ (2^iExp)) + DezToBin(iDez % (2^iExp), iExp-1);
Sorry, habe nichts zum Testen zur Hand.
Die Funktion muss mit einem möglichst hohen Exponenten als Startwert (Defaultwert) gestartet werden.
Die 2 kann natürlich zu einer beliebigen Basis verallgemeinert werden, die jedoch übergeben werden muss. Aber einem Stellenwertsystem größer 10 muss außedem in der Zeichenkette 10 durch A usw. ersetzt werden, weil man sonst 1 0 nicht von A unterscheiden könnte.
Die Funktion arbeitet zwar rekursiv, aber ohne das Hornerschema. :(
http://www.inf.fh-flensburg.de/lang/informatik/zahlendarstellung.htm Ganz nach unten scrollen. Dort findest du über den Aufgaben einen Algorithmus. Den erstmal in einer Programmiersprache implementieren und dann in eine Rekursion umwandeln. Wichtig: Rekursionen werden wie reguläre Schleifen durch eine Abbruchbedingung beendet. Gruß :)
So ist es villt übersichtlicher:
public static long gibDarstellung(long zahl, int basis) {
return (zahl <= 0)
? zahl % basis
: zahl % basis + gibDarstellung(zahl / basis, basis) * 10;
}