Frage zur Rekursion

[_nohtyp_]

Ich übe grade meine Kenntnisse an Aufgaben des Sächsischen Informatikwettbewerbs. Hier der Code:

Code: Alles auswählen

eingabe = list('4Satz03Das') + ['17'] + list('3ein13ist') + ['12']

sprung = 7
satz = []


def satz_lesen(sprung, eingabe, satz):

    # da Liste mit Index 0 beginnt, sprung -= 1
    # Umwandlung in int, um Verwendung als Listenindex
    buchstaben = int(eingabe[sprung - 1])

    for i in range(buchstaben):

        # Buchstabe = Listen-Inhalte nach dem Sprungpunkt
        buchstabe = eingabe[sprung + i]
        satz.append(buchstabe)

    # For-Schleife laueft ein Element weiter, um Sprungpunkt zu ermitteln
    for i in range(buchstaben + 1):

        # Zahl nach letztem Buchstaben (neuer Sprungpunkt) wird gesucht
        if i == buchstaben:

            # "sprung" wird Inhalt des Indexes nach den Buchstaben zugewiesen
            sprung = eingabe[sprung + i]
            break

    # Wenn die Sprungadresse 0 ist, ist der Satz beendet
    if sprung == 0:
        return

    # Funktion wird mit neuem Sprungpunkt erneut ausgefuehrt
    return satz_lesen(sprung, eingabe, satz)

sprung = satz_lesen(sprung, eingabe, satz)

print 'Ergebnis:'
print ''.join(satz)

Es geht darum, den oben definierten Satz zu entschlüsseln. Es wird ein Sprungpunkt gegeben, der zu einer Position im Satz führt (der Satz beginnt im Original mit Index Nummer 1). Diese zeigt die Anzahl der Buchstaben die folgen. Abgeschlossen wird das Wort durch eine neue Sprunganweisung.

Ich habe jetzt versucht, dass Problem durch Rekursion zu lösen. Nur leider kommt der Fehler:

Code: Alles auswählen

TypeError: unsupported operand type(s) for -: 'str' and 'int'

Ich denke mal, dass nicht die richtige Sprungadresse raus kommt, und das ganze deshalb mit dem Buchstaben anfängt. Ich weiß aber nicht, warum.

Kann mir jemand helfen?
Danke!

[EyDu]

Zum Nachdenken:

Code: Alles auswählen

>>> "eins" - 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for -: 'str' and 'int'

Und zeige beim nächsten Mal bitte den gesamten Traceback und nicht nur den Teil, den du für wichtig hältst.

[_nohtyp_]

Code: Alles auswählen

Traceback (most recent call last):
  File "/Users/ich/Documents/Projekte/Memory_Caching.py", line 37, in <module>
    sprung = satz_lesen(sprung, eingabe, satz)
  File "/Users/ich/Documents/Projekte/Memory_Caching.py", line 35, in satz_lesen
    return satz_lesen(sprung, eingabe, satz)
  File "/Users/ich/Documents/Projekte/Memory_Caching.py", line 12, in satz_lesen
    buchstaben = int(eingabe[sprung - 1])
TypeError: unsupported operand type(s) for -: 'str' and 'int'
[Finished in 0.1s with exit code 1]
[shell_cmd: python -u "/Users/martin/Documents/Projekte/Memory_Caching.py"]
[dir: /Users/martin/Documents/Projekte]
[path: /usr/bin:/bin:/usr/sbin:/sbin]

[EyDu]

Dann schau dir doch mal Zeile sieben deiner Fehlermeldung im Code an und überlege, was das mit meinem Hinweis zu tun hat. Noch ein Hinweise: lass dir die Variablen und deren Typen mittels print ausgeben und Zerlege den Ausdruck in Teilausdrücke.

[_nohtyp_]

Das statt der Sprungadresse der Buchstabe danach ausgegeben wird. Aber meine Frage: Warum?

[BlackJack]

@_nohtyp_: `eingabe` enthält ausschliesslich Zeichenketten und keine Zahlen. Nach Zeile 26: ``sprung = eingabe[sprung + i]`` was erwartest Du hat der Wert von `sprung` für einen Wert?

[_nohtyp_]

Das habe ich übersehen. Danke
Aber wenn ich die Sprunganweisung mit int() umwandle, kommt folgender Fehler: ValueError: invalid literal for int() with base 10: 'e'

Also kommt doch etwas falsches raus.

[BlackJack]

@_nohtyp_: Dann stimmt etwas mit Deinen Rechnungen nicht.

Ist das eine Aufgabe aus dem Archiv oder was aktuelles? Falls aus dem Archiv, in welcher Schulform und in welchem Jahr findet man die denn?

Ist Rekursion eine Bedingung bei der Aufgabe? Ich habe das iterativ jedenfalls in vier einfachen Zeilen lösen können, und Deine Funktion ist ja schon endrekursiv, also eigentlich sehr einfach in eine Schleife überführbar. Die Frage deshalb, weil Python nicht wirklich geeignet ist jedes Problem mit Rekursion anzugehen. Wie eigentlich alle Programmiersprachen mit einem Aufrufstapel und ohne garantierte Wegoptimierung von endrekursiven Aufrufen („tail call optimization”/TCO).

[_nohtyp_]

Leider habe ich die Aufgaben nicht online gefunden. Aber Rekursion ist keine Bedingung, nur ich dachte, es würde sich gut anbieten.

[Leonidas]

Ich würde mir ja gerne die Aufgabe ansehen, aber irgendwie verstehe ich die Eingabe nicht. Warum sind '17' und '12' ein Eintrag in der Eingabeliste, die '03' und '13' zwei? Es terminiert ja offenbar wenns bis 0 springt, aber zählen die Zahlen überhaupt in die Sprungoffsets rein? Ich muss sagen, deine Erklärung verwirrt mich total.

[BlackJack]

@Leonidas: Die 17 und die 12 sind *eine* Zahl, während '03' und '13' jeweils *zwei* Zahlen sind. Das Format ist '<Länge><Wort><Zeiger>' wobei <Länge> die Länge von <Wort> angibt und <Zeiger> der Versatz an dem das nächste Wort in diesem Format steht. Wenn <Zeiger> 0 ist, hat man das Ende des Satzes erreicht.

Ich finde das Format auch komisch und hätte als Steller einer solchen Aufgabe wahrscheinlich die Zahlen als Bytes kodiert, damit man nicht das Problem bekommt die Byte-/Zeichenfolgen '42' und '4', '2' unterscheiden zu müssen. Also so:

Code: Alles auswählen

source = '\x04Satz\x00\x03Das\x11\x03ein\x01\x03ist\x0c'

Oder man hätte die Zahlen grundsätzlich zweistellig angeben können.

@_nohtyp_: Wenn die Aufgabe gelöst ist, wäre eine weitere interessante Übung IMHO eine Funktion die so einen kodierten Satz erzeugt, damit man das nicht von Hand machen muss, wenn man solche Aufgaben stellen möchte.

[Leonidas]

@BlackJack: Danke, so ist das deutlich verständlicher.

Spoiler alert: Hier eine Lösung in Haskell, rekursiv. Nicht endrekursiv, aber für die größe der Eingaben sollte das ausreichen

[BlackJack]

Mal eine Lösung in Forth:

Code: Alles auswählen

: $, ( adr len -- )
    dup c,
    here
    over allot
    swap cmove
;

create input
    s" Satz" $,  0 c,
    s" Das" $,   17 c,
    s" ein" $,   1 c,
    s" ist" $,   12 c,

\ input  here input -  dump  \ Debug: Dump input data.

: decode-word ( u -- u )
    chars input +
    dup  1 chars -  c@
    2dup type
    + c@
;

: decode-sentence ( u -- )
    begin dup 0<> while
        decode-word  space
    repeat
    cr  drop
;

: main  7 decode-sentence ;

main
bye

Die Längen und Sprünge werden hier als Bytes kodiert. Der auskommentierte Abzug des Speichers ab `input` sieht so aus:

Code: Alles auswählen

B71D67F8: 04 53 61 74  7A 00 03 44 - 61 73 11 03  65 69 6E 01  .Satz..Das..ein.
B71D6808: 03 69 73 74  0C          -                           .ist.

[_nohtyp_]

Ich würde lieber wissen, was ich falsch gemacht habe, anstatt der Lösung. Sonst mache ich es nächstes Mal ja wieder falsch.

[BlackJack]

@_nohtyp_: Die beiden Lösungen helfen Dir bei Python ja nicht wirklich weiter, dazu sind Haskell und Forth zu verschieden zu Python (und untereinander).

Wenn Du beim Buchstaben nach der Zahl heraus kommst, dann hast Du Dich offensichtlich irgendwo verrechnet. Geh den Algorithmus doch einfach mal von Hand mit Papier und Bleistift durch, dann siehst Du ja wo etwas falsches berechnet wird.

Die ``for``-Schleife ab Zeile 20 ist übrigens ziemlich unsinnig.

[Leonidas]

Die ganzen Schleifen sind ziemlich unsinning und bei einer rekursiven Lösung auch unnötig. Du kannst ja das Wort extrahieren indem du Indexing betreibst, da musst du nicht iterieren.

Vorgehen bei rekursiven Funktionen:

• Überlege dir was die Funktion für einen Datentyp zurückgibt. Ich würde für den Anfang nicht-endrekursive Funktionen empfehlen, weil sie einfacher zu verstehen sind.
• Überlege dir was der Abbruchfall ist. Und was im Abbruchfall zurückgegeben werden muss. Das ist bei dir etwa in Zeile 31 schonmal falsch, weil egal wie gut dein Algorithmus funktioniert, am Ende ist ``sprung`` null und damit gibst du ``None`` zurück, und zwar rekursiv und das Ergebnis beim Aufrufer ist immer ``None``.
• Nachdem du den Abbruchfall abgehandelt hast, kannst du den Regulärfall abhandeln. Dazu musst du erstmal die Zahl der Buchstaben auslesen, dann die Buchstaben selbst und dann den nächsten Sprung. Das kannst du quasi alles über Indexing erledigen. Dann noch die gelesenen Buchstaben mit dem Aufruf kombinieren und fertig.

[_nohtyp_]

Habe jetzt mein Programm umgebaut:

Code: Alles auswählen

eingabe = list('4Satz03Das') + ['17'] + list('3ein13ist') + ['12']

sprung = 7
satz = []

def satz_lesen(sprung, eingabe):
    anzahl_zeichen = eingabe[sprung - 1]
    wort = eingabe[sprung:sprung + int(anzahl_zeichen)]
    satz.append(wort)
    sprung = eingabe[
        sprung + int(anzahl_zeichen):sprung + int(anzahl_zeichen) + 1]
    sprung = ''.join(sprung)
    return sprung


sprung = satz_lesen(sprung, eingabe)
print sprung
# satz_lesen(sprung, eingabe)

print satz

Jetzt habe ich nur einen komischen Fehler. Wenn ich die Variable "sprung" ganz oben auf die nächste Sprunganweisung, also 17 stelle, kommt auch das nächste Wort. Speichere ich aber den Sprung, der mit return zurückgegeben wurde und benutzte den, funktioniert es nicht. Obwohl auch 17 zurückgegeben wird. Verstehe ich nicht.

Edit: Die Fehlermeldung ist die gleiche, wie bei der rekursiven Variante.

[EyDu]

Du bekommst die gleiche Fehlermeldung, weil du den selben Fehler wie oben erneut machst. Lass dir zu allen Schritten und Zwischenergebnissen wieder Wert und Typ ausgeben, dann siehst du es.

[Sirius3]

@_nohtyp_: die globale Variable »satz« erzeugt sehr komplizierte Abhängigkeiten, die man eigentlich nicht haben will. Besser wäre es eine statt »satz_lesen« eine Funktion »lese_wort« zur haben, die sowohl das Wort als auch die nächste Position zurückliefert. Zu Deinem Problem: »sprung« ist im ersten Aufruf eine Zahl, beim zweiten mal aber etwas anderes.

[BlackJack]

@_nohtyp_: So etwas wie ``sequence[(berechnung):(berechnung) + 1]`` ist im allgemeinen eine komplizierte Art ``sequence[(berechnung)]`` zu schreiben. Es gibt zwar einen Unterschied, nämlich dass die erste Variante statt eines `IndexError` eine leere Sequenz liefert wenn das Ergebnis der Berechnung ausserhalb der Länge von `sequence` ist, aber dieser Fall sollte bei gültigen Eingabedaten in Deiner Funktion nicht eintreten. Oder anders ausgedrückt: Sollte der Fall tatsächlich eintreten, dann möchte man eher dass der genau an der Stelle schon eine Ausnahme auslöst, und nicht erst später wenn anderer Code nicht mit der leeren Sequenz gerechnet hat.

Zeile 12 ist sinnfrei, und da wäre für Dich auch schon ein Hinweis dass da etwas nicht stimmen kann, denn wenn `sprung` eine Zahl wäre, würde diese Zeile eine Ausnahme auslösen weil man über eine Zahl nicht iterieren kann.

`sprung` finde ich übrigens auch einen komischen Namen für diesen Wert. Ich hätte das wohl `offset` oder `versatz` genannt.