Dezimalzahlen in Binärzahlen rekursiv?
Guten Abend, ich habe ein Problem mit einer Aufgabe aus dem Studium. Ich soll eine Methode toBin() schreiben, die eine Dezimalzahl in eine Binärzahl umwandelt und immer mit "0" beginnt. z.B. new Num(2).toBin() = "010". Es soll als String ausgegeben werden und muss rekursiv sein. Ich habe bereits mehrere Lösungswege versucht aber durch eine Variable "final long n" komme ich nicht weiter, da ich bei meinen Lösungen die Variable immer geändert hätte wenn sich die Methode selber wieder aufruft. Jetzt bin ich komplett überfragt und brauche Hilfe.. Danke schonmal :)
EDIT: Habe mal die Methode neu geschrieben. Würde Sie so funktionieren?
4 Antworten
Naja, du könntest rekursiv immer neue Objekte erstellen.
Also in toBin() machst du ja eine Rechnung, um eine Stelle des Strings herauszufinden und dann hast du eine Zahl, die du erneut mit toBin() aufrufen möchtest... Also könntest du mit einem neuen Objekt Num(blabla).toBin() arbeiten.
Danke für die Hilfe. Ich muss in toBin() ja eine Rechnung machen mit der Variable aus Num(n) aber sobald ich dann versuche die Variable zu verändern bekomme ich ja ne Fehlermeldung weil "n" ja final ist. Wenn ich ein rekursiv neue Objekte erstelle würde dann nicht das selbe passieren? Vielleicht ist mein Denkansatz auch komplett verkehrt aber ich blicke da leider nicht durch, da Rekursionsrechnungen an sich schon schwer zu verstehen ist für mich und das noch komplizierter ist.
Hallo, ich habe in die Frage oben ein neues Bild eingefügt mir einer Lösungsmöglichkeit. Denken Sie es funktioniert so?
Sorry, ich sehe trotz Neuladen der Seite keine Veränderung.
Ah dann muss die Änderung wohl erst genehmigt werden..
Du kannst auch in Kommentaren Text als Programmcode formatieren. Dafür klickst du auf das Quadrat rechts neben/über dem Eingabefeld mit dem Tt drin und dann auf </>.
class Num{
//n is assumed to be a positive number
final long n;
Num(long n){
assert n>=0;
this.n = n;
}
String toBin(){
long dual = this.n;
long rest = dual%2;
dual = (dual - (dual%2)) /2;
return "" + new Num(dual) + rest;
}
Der Lösungsweg für eine Umrechnung wird bereits hier iterativ behandelt.
Ich würde empfehlen, eine Instanz des StringBuilder zu erstellen, in diesem die "0" zu speichern und diesen dann bei den rekursiven Aufrufen immer weiter zu tragen.
Pseudocode (noch ohne Abbruchbedingung):
toBin(number, builder):
place = number % 2
builder.append(String.valueOf(place))
toBin(number / 2, builder)
Danke für die Antwort, die Methode toBin() darf keine übergebenen Werte haben leider, das wird übers Studium geprüft wenn ich den Code abgebe und führt dann zu Fehlermeldung / Punktabzug..
Diese toBin-Methode sollte eine nichtsichtbare Überladung darstellen:
public String toBin() {
StringBuilder builder = new StringBuilder();
toBin(n, builder);
return builder.toString();
}
private void toBin(int number, StringBuilder builder) {
// ...
}
Es wäre also eine Helfermethode. Die kannst du natürlich auch anders benennen.
Okey also das verwirrt mich doch ganz schön.. wozu die void toBin. Was ist deren Nutzen, könnten Sie mir das bitte erklären. Denn auch wenn Sie bestimmt recht haben, sagt es mir leider nichts..
Die void toBin ist die eigentliche rekursive Funktion (deren Inhalt / Funktion ich oben schon mit dem Pseudocode beschrieben habe). Vielleicht hätte ich ihr doch einen besseren Namen geben sollen.
Die Methode hat den Rückgabewert void, da nichts zurückgegeben werden muss. Das Ergebnis wird in der StringBuilder-Instanz getragen, die immer weitergereicht wird.
Um es bildlich zu beschreiben: Der Builder ist wie der Spendenteller in der Kirche. Er wird einmal herumgereicht und trägt am Ende somit auch das Endergebnis.
void nextPerson(plate, neighbour) {
plate.add(gift);
if (neighbour.next == null)
return;
nextPerson(plate, neighbour.next);
}
Wird hierbei nicht die Binärzahl umgedreht - oder übersehe ich jetzt was? Eigentlich will man mit tiefergehender Rekursion (höhere Stellen der Zahl) vorn etwas an das Ergebnis hinzufügen...
Schön gesehen, das Ergebnis muss ja noch umgedreht werden. 😁
Heißt, erst müsste man ganz nach unten und danach die Werte anhängen.
Pseudocode (immer noch ohne Abbruchbedingung):
toBin(number, builder):
place = number % 2
toBin(number / 2, builder)
builder.append(String.valueOf(place))
Die 0 wird erst ganz zum Schluss zugefügt.
Das was regex gesagt hat.
Wenn die Methode nicht verändert werden darf ist deine rekursive Methode eben eine private Methode.
Die Methode die sich selbst aufruft gibt der einfach den aktuellen Parameter mit. Wie z.b. nen den Stringbuilder.
Neue Objekte zu erzeugen davon halte ich in dem Falle auch nicht viel.
Das ist hoffentlich eine Theorie-Aufgabe? So was mit Objekten zu machen fühlt sich für mich so an, wie mit einem Lastzug zwei Häuser weiterzufahren statt die paar Schritte zu Fuß zu gehen.
Wie kmkcl schon sagte - neue Objekte erzeugen statt neuer Variablen.
Meine Lösung ist mit ziemlicher Sicherheit zu "elegant":
String toBin() {
return (this.n == 0)
? "0"
: (new Num(this.n / 2)).toBin() + (this.n % 2 == 0 ? "0" : "1";
}
Aber ich finde, jemand, der Anfängern solche "Antipattern" beibringt, gehört wenigstens geohrfeigt. Oder dazu verdonnert, die nächsten zwei Jahre ausschließlich mit Computern zu arbeiten (und zu spielen!), die mit maximal 256 MB RAM ausgestattet und mit maximal 20 MHz getaktet sind.
Tatsächlich find ich das auch ziemlich scheiße, ich weiß im Studium muss man viel selber lernen aber solche Strukturen werden bei uns weder in den Vorlesungen noch in den Übungen behandelt.. Aber da muss ich halt durch
Okey ich glaube ich verstehe den Code ein wenig, aber wozu am Ende + (this.n % 2 == 0 )? "0" : "1"; wurde genau das nicht schon bei return(this.n ==0) abgefragt?
"%" ist der Modulo-Operator (Operator für den Rest bei einer Ganzzahl-Division).
Ja das weiß ich :D aber ich meinte, wenn return (this.n == 0) false ist, dann ist die Abfrage ob this.n % 2 == 0 ist doch überflüssig oder? Da er ja nur zu dieser Abfrage kommt wenn das return(this.n == 0) false ist und somit der Rest automatisch 1 sein muss. Oder sehe ich das falsch? Ist aber auch nicht so wichtig mein eigentliches Problem ist ja die Rekursion. :D
Übrigens, deine Logik in dem Kommentar oben funktioniert.
Allerdings weiß ich nicht, ob man das "new Typename(...)" nicht in Klammern setzen muss - immerhin könnte es sein.
Jedenfalls ruft Java die Methode toString() auf, wenn ein String gebraucht wird - du müsstest hier also entweder explizit toString() auf toBin() umleiten oder
(new Num(dual)).toBin()
verwenden.
Außerdem könntest du
dual = (dual - rest)) /2;
verwenden - rest ist ja schon dual%2.
Spart ein paar Nanosekunden, aber darauf kommt es bei den Millisekunden für die Objektverwaltung ja nun wirklich nicht an.
Ich habe hier den "ternären Operator" "?:" verwendet. Das ist so eine Art if-else für Ausdrücke.
Vermutlich ist es verwirrend, dass ich das Fragezeichen in die nächste Zeile gezogen habe, damit es über dem Doppelpunkt steht. (Gewohnheit ...) Wenn man sich daran gewöhnt hat, auf das (vorhandene/fehlende) Semikolon am Zeilenende zu achten, fällt das mehr auf.
Okey gut, was meinen Sie mir new Typename(...) und ja: new Num(dual).toBin() habe ich leider vergessen hinzuzufügen, ohne to.Bin() wäre es dann ja nicht rekursiv, oder? Und sorry für so viele Fragen bin erst im ersten Monat vom Studium.. :D
Ohne toBin() ist es nur deshalb nicht rekursiv, weil toString() nicht toBin() aufruft.
"new Typename(...)": "Typename" steht hier als Platzhalter für einen Typnamen (hier "Num") und die drei Punkte ... für etwas, das man hier ergänzen muss.
Kein Problem wegen der vielen Fragen - vielen von uns macht es Spaß, sich damit auseinanderzusetzen.
Übrigens - in Internetforen gilt üblicherweise das "Du". Bleiben wir doch dabei.
Okey danke für die Erklärung habe es jetzt verstanden, ich werde mal die Methode sowie die anderen Aufgaben machen und falls es dann erneut Fragen gibt werde ich mich nicht zurückhalten :D
Vielen vielen Dank bis hier schonmal!
Also ich bins erneut :D
Diesmal nur ein kleines Problem..
Ich soll wie in der ersten Aufgabe umrechnen. Und sobald der Rest
>= 10 ist soll er Buchstaben ausgeben, dafür war die Methode
getDigit bereits vorgegeben. Es kommt keine Fehlermeldung o.ä also
es läuft ABER bei der Berechnung, ob "rest >= 10" ist gibt er mir
wenn ich die Methode getDigit(rest) aufrufe nicht A aus sondern er
gibt der Variable "rest" den Wert 65, was das Ergebnis verfälscht.
Ich weiß aber nicht wie er auf den Wert 65 kommt. Die Methode
getDigit verändert die Zahl ja nicht wirklich..
String toBase(int b){
long zahl = this.n;
long rest = zahl%b;
zahl = (zahl-(rest))/b;
if (rest >= 10) {rest = getDigit(rest);}
if(zahl == 0) return "" + 0 + rest;
return "" + new Num(zahl).toBase(b) + rest;
}
static char getDigit(long d){
return (char) (d<10? '0'+d : 'A'+d-10);
}
Es wäre hilfreich, wenn man für euren Compiler die Typüberprüfung auf "strict" setzen könnte - dann würde
rest = getDigit(rest)
einen Fehler auswerfen - String lässt sich nicht implizit in long umwandeln, und auch sonst würden sehr viele Fehler vermieden.
Auch
return "" + new Num(zahl).toBase(b) + rest;
würde einen Fehler ergeben - long lässt sich nicht implizit in String umwandeln (Variable rest).
Warum nimmst du nicht einfach
"" + new Num(zahl).toBase(b) + getDigit(rest)
als Rückgabewert?
Mir fehlt hier eine Überprüfung, dass b zwischen 2 und 36 (jeweils einschließlich) liegt.
Bei 1 ergäbe dies eine infinite Rekursion bzw. einen Stapelüberlauf, bei 37 wäre "[" eine gültige Ziffer.
String toBin() {
return (this.n==0) ? "0"
: (new Num(this.n>>1)).toBin() + (this.n & 1 == 1) ? "1" : "0";
}
Alternative Formulierung - Es ist halt schon ein Jammer, daß man bei Java nicht einfach nur this.n &1 schreiben kann, sondern immer vergleichen muß.
Vom Standpunkt der Typsicherheit ist das zu begrüßen, vom Standpunkt des Praktikers nicht.
Bei dieser Verschwendung von Objekten dreht sich mir als erfahrenem Entwickler der Magen um ... Immerhin funktioniert es, und da es offensichtlich eine reine Theorie-Aufgabe ist, ist es ok.