Dezimal- in Binärzahl (rekursiv)

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Stift005
User
Beiträge: 16
Registriert: Montag 2. November 2020, 16:52

Donnerstag 13. Mai 2021, 16:11

Hallo zusammen,

ich komme gerade bei folgender Aufgabe nicht weiter:
Ich soll eine rekursive Funktion schreiben, die eine Dezimalzahl entgegennimmt und diese dann als String als Binärzahl zurückliefert.

Mein Ansatz funktioniert auch, jedoch nutze ich eine globale Variable.. Also werden bei mehrmaligen Aufrufen der Funktion die Ergebnisse in dieser aneinandergereiht. Nun könnte man natürlich die Variable dazwischen immer wieder "leeren", aber das wäre ja zu einfach. :P

Meine Frage daher: Wie könnte man das ganze ohne globale Variable lösen? Mein Hauptproblem ist einfach, dass ich nicht weiß, wie ich der Funktion ein "Gedächtnis" verpassen kann - wenn man das so sagen kann.

Code: Alles auswählen

result = []

def decInBinRek(n):
## Nimmt eine Dezimalzahl und wandelt diese in eine Binärzahl um, in dem die Zwischenergebnisse in der Liste 'result' zwischengespeichert werden.

    if n == 0:
      result.reverse()
      return "".join(result)
    else:
      result.append(str(n % 2))
      return decInBinRek(int(n / 2))

print(decInBinRek(20))
print(decInBinRek(42))

"""
Output:
10100
10101000101

"""

Wäre super, wenn mir jemand helfen könnte!
Sirius3
User
Beiträge: 14609
Registriert: Sonntag 21. Oktober 2012, 17:20

Donnerstag 13. Mai 2021, 16:34

Engerückt wird in Python immer mit 4 Leerzeichen pro Ebene, nicht mal 4 und mal 2.
Funktionen werden wie Variablen komplett klein geschrieben.
Es gibt keine Dezimalzahlen, sondern nur eine interne Repräsentation einer Zahl, die Du entweder in einen String mit einer Dezimalzahl oder eben einem String mit einer Binärzahl umwandeln mußt, damit man sie ausgeben kann.
Benutze keine Abkürzungen, wenn Du rekursiv meinst, dann schreibe nicht Rek.
Also decInBinRek -> number_to_binary_recursive.
Wenn Du eine Ganzzahldivision haben willst, benutze // und nicht int mit Fließkommadivision.

Eine Möglichkeit wäre, result immer als Argument mitzugeben, besser wäre es aber, die Funktion komplett umzusturkturieren und tatsächlich eine Funktion zu schreiben, die aus einer n-bittigen Zahl eine Binären Ziffer und eine n-1 - bittige Zahl macht und rekursiv wird die n-1 bittige Zahl in einen String umgewandelt und mit der Ziffer zu einem String mit n-Bit kombiniert.
Stift005
User
Beiträge: 16
Registriert: Montag 2. November 2020, 16:52

Donnerstag 13. Mai 2021, 17:03

Das Einrücken überlasse ich eigentlich immer PyCharm?
Den Rest habe ich mal so überarbeitet:

Code: Alles auswählen

def number_to_binary_recursive(n, res):
    if n == 0:
        res.reverse()
        return "".join(res)
    else:
        res.append(str(n % 2))
        return number_to_binary_recursive(n//2,res)

print(number_to_binary_recursive(20, res = []))

print(number_to_binary_recursive(42, res = []))
Funktioniert! Vielen dank! :)
Sirius3
User
Beiträge: 14609
Registriert: Sonntag 21. Oktober 2012, 17:20

Donnerstag 13. Mai 2021, 17:39

Es ist es natürlich schlecht, dass man bei der Funktion immer eine leere Liste übergeben muss; das kann man lösen, in dem man ein Defaultargument benutzt:

Code: Alles auswählen

def number_to_binary_recursive(n, result=None):
    if result is None:
        result = []
    if n == 0:
        result.reverse()
        return "".join(result)
    else:
        n, digit = divmod(n, 2)
        result.append("1" if digit else "0")
        return number_to_binary_recursive(n, result)

print(number_to_binary_recursive(20))
print(number_to_binary_recursive(42))
Jetzt hast Du noch das Problem, dass 0 ein falsches Ergebnis liefert.
Stift005
User
Beiträge: 16
Registriert: Montag 2. November 2020, 16:52

Donnerstag 13. Mai 2021, 19:39

Stimmt, so schaut das besser aus.
Das mit der 0 habe ich nun stumpf mit einer weiteren If-Abfrage gelöst:

Code: Alles auswählen

def number_to_binary_recursive(n, res=None):
    if res is None and n == 0:
        return 0
    if res is None:
        res = []
    if n == 0:
        res.reverse()
        return "".join(res)
    else:
        res.append(str(n % 2))
        return number_to_binary_recursive(n//2,res)

print(number_to_binary_recursive(20))

print(number_to_binary_recursive(42))

print(number_to_binary_recursive(0))
Sirius3
User
Beiträge: 14609
Registriert: Sonntag 21. Oktober 2012, 17:20

Donnerstag 13. Mai 2021, 20:08

Bei 0 gibt die Funktion aber eine Zahl zurück, sonst, wie es sich gehört einen String.
Stift005
User
Beiträge: 16
Registriert: Montag 2. November 2020, 16:52

Donnerstag 13. Mai 2021, 20:40

Code: Alles auswählen

def number_to_binary_recursive(n, res=None):
    if res is None and n == 0:
        return str(0)
    if res is None:
        res = []
    if n == 0:
        res.reverse()
        return "".join(res)
    else:
        res.append(str(n % 2))
        return number_to_binary_recursive(n//2,res)

print(number_to_binary_recursive(20))

print(number_to_binary_recursive(42))

print(number_to_binary_recursive(0))
Jetzetle aber :D
Sirius3
User
Beiträge: 14609
Registriert: Sonntag 21. Oktober 2012, 17:20

Donnerstag 13. Mai 2021, 20:51

Statt str(0) schreibt man besser "0". Auch das str(n%2) ist nicht wirklich reine Lehre, weil Du eine Funktion benutzt, die eine Zahl in einen Dezimalstring umwandelt.
Es wird zwei mal ‹res is None› bzw ‹n == 0› geprüft, was man noch vereinfachen könnte:

Code: Alles auswählen

def number_to_binary_recursive(n, res=None):
    if n == 0:
        if res is None:
            return "0"
        res.reverse()
        return "".join(res)
    if res is None:
        res = []
    res.append("1" if n % 2 else "0")
    return number_to_binary_recursive(n//2, res)
Stift005
User
Beiträge: 16
Registriert: Montag 2. November 2020, 16:52

Donnerstag 13. Mai 2021, 20:58

Das ändere ich nochmal. Dann ist aber genug. ^^
Nochmal danke für deine Hilfe und noch einen schönen Abend!
Benutzeravatar
__blackjack__
User
Beiträge: 8721
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Donnerstag 13. Mai 2021, 21:03

Hach ich bin ein bisschen zu spät dran, aber trotzdem…

@Stift005: Erstmal eine ”echtere” rekursive Lösung, also eine die noch nicht endrekursiv ist, und deshalb einfach durch eine Schleife ersetzt werden sollte:

Code: Alles auswählen

def _to_binary(n):
    return "" if n == 0 else _to_binary(n // 2) + str(n % 2)

def to_binary(n):
    return _to_binary(n) or "0"
Und dann Deine Funktion etwas umformuliert und gestrafft:

Code: Alles auswählen

def to_binary(n, digits=None):
    if digits is None:
        digits = []

    if n == 0:
        return "".join(reversed(digits)) if digits else "0"
    else:
        digits.append(str(n % 2))
        return to_binary(n // 2, digits)
long long ago; /* in a galaxy far far away */
Antworten