Jump to content

Rangliste


Beliebte Inhalte

Showing content with the highest reputation on 21.08.2019 in allen Bereichen

  1. 1 point

    Rekursion Python verstehen

    Die Erklärung von @PVoss ist formal absolut korrekt. Ich möchte aber noch auf einen anderen Punkt eingehen, nämlich auf die Herangehensweise wie man Rekursionen sehr einfach abstrahieren kann. Das macht man nämlich am einfachsten Buttom Up und nicht Top Down wie oben gezeigt. Beim Buttom Up Ansatz versteht man sofort, warum der Code aussieht, wie er aussieht. Bleiben wir mal bei dem Beispiel. Es soll eine Funktion geschrieben werden, welche die Quersumme der übergebenen Zahlen berechnet. Sprich quersumme(4321) = 4+3+2+1 = 10 Wenn man solche Aufgaben rekursiv lösen will, dann hilft der Buttom Up Ansatz. Man muss sich zunächst die Frage stellen, was der einfachste Fall wäre für einen Funktionsaufruf. Der einfachste Fall wäre, wenn ich nur die Quersumme aus einer Zahl mit einer Ziffer berechnen wollen würde. Spiele ich das einfach mal für mich durch: quersumme(5) = 5 quersumme(0) = 0 quesumme(2) = 2 Tatsächlich. Die Quersumme einer übergebenen Zahl mit nur einer Ziffer ist immer die übergebene Zahl selbst. Sprich: In der Rekursion muss ich zunächst den einfachsten Fall abbilden. In dem Codebeispiel oben ist der einfachste Fall: if len(str(n)) == 1: return n Wenn n nur eine Stelle lang ist, gebe n zurück. Wenn ich den einfachsten Fall habe, kommt der clu an der Rekursion. Jetzt muss ich mir nämlich nur noch den minimal schwierigeren Fall angucken und überlegen, wie ich vom schwierigeren Fall zum einfacheren Fall komme. Mache ich für mich wieder die Probe: quersumme(62) = 6+2 = 8 quersumme(77) = 7 + 7 = 14 quersumme(20) = 2 + 0 = 2 Ich kann hier folgendes ableiten: Wenn ich mehr als eine Stelle habe, dann muss ich immer die letzte Stelle n, die für sich genommen eben der einfache Fall ist (n=n) mit der nächst höheren zehner Stelle addieren und diesen Wert zurückgeben. Mit dem einfachen Fall habe ich bereits abgedeckt, dass ich die Quersumme einer ziffer berechnen kann. Was ich jetzt noch brauche ist ein zweiter Fall, in dem ich die einzelne Ziffer mit der nächst höheren zehner stelle addiere. Also nehme ich mir einmal die letzte Zahl (n % 10) und addiere sie mit der quersumme der nächsten höheren zehnerstelle. Wie bekomme ich die nächst höhere zehnerstelle? Nun ja, ich dividiere die Zahl durch 10 mit abgetrennter Kommastelle, dann habe ich ja meine zweite Zahl, und übergebe diese einfach wieder an meine Funktion. Denn wir wissen ja: Wenn ich nur eine Ziffer an meine Quersummen Funktion übergebe, bekomme ich ja schon durch den einfachsten Fall die korrekte Quersumme zurückgeliefert. Das ist genau das, was folgender Code tut: return n % 10 + sum_func(n//10) Bei quersumme(20) würde das also bedeuten: Addiere die letzte Ziffer (0) mit der Quersumme von (2) => 0 + Quersumme(2) = 2 Wenn du also auf deinen einfachsten Fall zurückgreifst durch den Funktionsaufruf, kannst du x beliebige Ziffernfolgen reinschmeißen, dein Code wird die immer richtig auflösen! Warum funktioniert das auch mit mehr als 2 Ziffern? Weil du zwei Fälle abdeckst. Einmal den Fall wo die Zahl nur eine Ziffer lang ist, und einmal den Fall wo die Zahl mehr als eine Ziffer hat. Fazit: Wenn man sich den einfachsten Fall und den minimal komplexeren Fall anschaut und im Code abbildet, dann braucht man komplexe Funktionsaufrufe wie Quersumme(4321) nicht mehr vollständig durchdenken wie @PVoss es gemacht hat. Und so kann man jede Rekursion abbilden. Das funktioniert praktisch immer nach dem gleichen Schema. Egal ob Quersumme, Ziffern zählen, ein String auf ein Palindrom prüfen oder oder oder ... Und genauso kannst du auch beim lesen der Rekursion Vorgehen. Schau dir an wo der einfachste Fall abgebildet ist, verstehe ihn, und dann schau dir dann was der minimal komplexere Fall wäre und wie der abgebildet ist. Das erfordert am Anfang natürlich etwas Übung, bis man dieses Vorgehen verstanden hat und den Dreh raus hat, es erspart einem im nachhinein aber unendlich viel Zeit bei der Analyse von Rekursionen.
  2. 1 point

    Rekursion Python verstehen

    % ist der Modulo-Operator, der führt eine Division durch und gibt den Rest als Ergebnis zurück // ist der abrundende Divisionsoperator [edit] Im Endeffekt macht n % 10 + sum_func(n//10) also nichts anderes als die letzte Stelle im Speicher zu halten und sum_func mit den vorhergehenden Stellen aufzurufen, anschließend wird die erste Stelle dann mit dem Ergebnis vom sum_func-Aufruf addiert. [/edit] Mir fehlt gerade die Fantasie für eine bessere Darstellung deshalb... Der rekursive Ablauf würde so aussehen: Aufruf sum_func(4321) Zeichnlänge größer 1 Skip If-Block return 4321 % 10 [= 1] + Aufruf sum_func(4321 // 10 [432]) Zeichenlänge größer als 1 Skip If-Block return 432 % 10 [= 2] + Aufruf sum_func(432 // 10 [43]) Zeichenlänger größer als 1 Skip If-Block return 43 % 10 [= 3] + Aufruf sum_func(43 // 10 [4]) Zeichenlänge ist 1 return 4 Das ist der Stack, der dann im Endeffekt so abgearbeitet wird sum_func(4) return 4 sum_func(43) return 3 + 4 sum_func(432) return 2 + 7 sum_func(4321) return 1 + 9
Diese Rangliste ist auf Berlin/GMT+02:00 eingestellt
  • Newsletter

    Möchtest du immer über unsere Neuigkeiten und Informationen auf dem Laufenden gehalten werden?
    Anmelden

Fachinformatiker.de, 2019 SE Internet Services

fidelogo_small.png

if_icon-6-mail-envelope-closed_314900.pnSchicken Sie uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App


Get it on Google Play

Kontakt

Hier werben?
Oder senden Sie eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...

Wichtige Information

Fachinformatiker.de verwendet Cookies. Mehr dazu in unserer Datenschutzerklärung