Python: Fibonacci mit Listen < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:59 Do 03.01.2019 | | Autor: | Kian |
| Aufgabe | Gegeben sei eine Treppe mit einer beliebigen Anzahl an Stufen. Eine Person kann eine oder zwei Stufen auf einmal erklimmen.
a) Schreiben Sie eine einstellige rekursive Funktion stairs(n), die eine Liste mit allen Möglichkeiten zurückgibt, eine Treppe mit n Stufen zu erklimmen.
b)Erweitern Sie Ihre Funktuion um ein zweites Argument, welches eine Liste ist, die alle Stufenanzahlen enthält, die eine Person mit einem Schritt erklimmen kann. |
Hallo,
Um die Aufgabe a) zu lösen habe ich die Methode von Fibonacci angewendet.
Die Funktion die ich geschrieben habe für a) ist rekursiv und liefert mir eine Liste mit allen Moeglichkeiten um die Stufen entweder mit 1 oder 2 schritten zu erklimmen.
Ich komme bei b) überhaupt nicht weiter.
Kann mir jemand einen Tipp geben oder einen Ansatz? Über Pseudocode würde ich mich auch freuen. Ich habe die Idee, Aber ich weiss einfach nicht wie ich die Umsetzen soll und wenn ich richtig überlege ist meine Idee auch nicht korrekt.
Lg
|
|
| |
|
Nachdem ich den Satz bei b) 5 mal gelesen und 10 Minuten überdacht habe, vermute ich, verstanden zu haben, was gemeint ist.
Bisher konnte die Person nur entweder 1 oder 2 Stufen auf einmal nehmen. Nun soll die Liste weitere/andere Mgl. enthalten, z.B. bei [2|3|7|] darf die Person jedesmal entweder 2, 3 oder 7 Stufen weiter springen. stairs(12,[2|3|7|]) soll dann eine Liste von möglichen Schrittfolgen angeben, um von Stufe 1 auf Stufe 12 zu gelangen, also u.a. 2+3+5, 3+2+5,..., 2+2+2+2+2+2, usw.
Tipp:
Um stairs(12,[2|3|7|]) zu berechnen, gehe
- zuerst 2 zurück. Das gibt stairs(10,[2|3|7|]), und an die Listenelemente hängst du nun überall 2 an.
- dann 3 zurück. Das gibt stairs(9,[2|3|7|]), und an die Listenelemente hängst du nun überall 3 an.
- zuletzt 7 zurück. Das gibt stairs(5,[2|3|7|]), und an die Listenelemente hängst du nun überall 7 an.
Die Abbruchbedingung musst du dir nun selber überlegen. Vor allem die Zusatzbedingung, dass du mit allem bei der 1. Stufe starten musst...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:23 Do 03.01.2019 | | Autor: | Kian |
Hallo,
danke für deine Antwort.
Habe die Logik dahinter verstanden, ich weiss nur nicht wie ich das jetzt umsetzten soll.
Vor allem weiss ich nicht wie ich immer was an die Liste anhängen soll.
def stairs(n, steps) were meine Funktion.
Abbruch waere dann wenn n < step[x] ist oder?
|
|
|
| |
|
Bleiben wir bei meinem Beispiel.
Wenn du dich mit n herunterhangelst und z.B. bei 2 landest, kannst du nicht mehr auf 1 kommen, da du nur Rückwärtssprünge 2, 3 oder 7 machen kannst. In diesem Fall gibst du eine leere Liste zurück.
Landest du genau auf 1, gibst du eine Liste mit nur 1 (als Startstufe) zurück.
Bist du bei n> 1, bildest du eine leere Liste. Dann machst du die drei von mir erwähnten Aufrufe mit n-2, n-3 und n-7.
Kommt bei einem der Aufrufe eine leere Liste zurück, machst du nichts damit. Dann hat sich dieser Zweig heruntergehangelt, ohne auf 1 zu landen.
kommt eine nicht-leere Liste zurück, fügst du nun an alle Listenelemente den momentanen Wert von n an und hängst dann das Ganze an die o.a. hier gebildete leere Liste. Das selbe mache mit den anderen beiden Aufrufen. Dann gib das neue Gebilde zurück.
Ich schreibe das mal relativ unkonventionell auf:
function stairs(n:Ganzzahl,Z:liste der erlaubten Stufenzahlen):Textliste
setze L=leere Textliste
Falls n<1 gebe L als leere Textlisteiste für den Funktionswert von stairs zurück
sonst
Falls n=1 setze L="1" und gebe L als Textliste stairs zurück
sonst
Lass Zeiger i von 1 bis Anzahl der Elemente in Z
laufen und
beginne
setze H=stairs(n-Element mit Nr. i aus Z,Z)
Falls H nicht leer:
Einschub: Ich nehme jetzt mal an, n=8,Z=[2,3,7]. Dann ist der erste Aufruf H=stairs(8-2, Z), also stairs(6,Z), und H wird zu ["1-3-6","1-4-6"].
Nimm jedes Element der Reihe nach aus H, setze den Text der aktuellen Stufe "-n" dahinter (kein n, sondern die Zahl, im roten Bespiele also "-8") und hänge dies an L an.
Wiederhole den Vorgang mit dem nächsten i
Gib dann L als Liste stairs zurück
Hier noch mal schematisch, was passiert:
Gesucht ist stairs(12, Z) mit obigem Z. Wir nehmen an, wir haben uns rekursiv heruntergehangelt und sind gerade im Aufruf stairs(8, Z). Wir bilden die leere liste L. Nun nehmnen wir das erste Element aus Z, die 2, ziehen dieses von 8 ab und rufen somit stairs(6, Z) auf. Dieses liefert uns, was wir voraussetzen, die Liste aller Wege von Stufe 1 auf Stufe 6 zurück, nämlich den Text 1-3-6 sowie den Text 1-4-6, was wir in H abspeichern. Daran hängen wir nun jeweils -8 an fund fügen dies in L (noch leer) ein, so dass L jetzt 1-3-6-8 und 1-4-6-8 enthält.
Jetzt nehmen wir das zweite Element aus Z, die 3, ziehen es von 8 ab und rufen stairs(5, Z) auf. Das liefert und nur 1-3-5 zurück, wir hängen -8 an und ergänzen L mit 1-3-5-8.
Nun das selbe mit 7, wir rufen stairs(1, Z) auf, erhalten die 1 zurück und hängen -8 an, packen in L also noch 1-8.
Dann geben wir L komplett zurück.
Würden wir z.B. von stairs(5, Z) aus den dritten Schritt mit dem Aufruf stairs(5-7, Z), also stairs(-2, Z) machen, bekämen wir die leere Liste zurück und würden nichts anhängen und nichts zu L hinzufügen.
ich hoffe, du kannst meine Überlegungen umsetzen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:37 Fr 04.01.2019 | | Autor: | Kian |
Danke für die tolle Antwort.
Ich habe alles verstanden, bis auf den 2. Else-Teil. Ich gehe stark davon aus das ich es nicht richtig implementiert habe. (Code im Anhang)
Dateianhänge:
Anhang Nr. 1 (Typ: py) [nicht öffentlich]
|
|
|
| |
|
Hier stimmt was nicht:
for x in range(len(H)):
lst.extend(stairs(n-H[x], steps))
Hier rufst du wieder stairs auf, und zwar mit n-H[x]. Das ist aber falsch. Der Aufruf H = stairs(n-steps[i], steps) ist richtig. Bleiben wir wieder bei meinem Zahlenbeispiel.
Du hast stairs aufgerufen und die Liste, die zurückkam, in H gespeichert. H enthält alle möglichen Wege, um zu n-steps[i] =8-2=6 zu kommen, z.B. "1-3-6" und "1-4-6", wobei "1-3-6" und "1-4-6" Listenelemente vom Typ Text sind (oder selber wieder Listen, s.u.). Diese Listenelemente aus H knöpst du dir nun einzeln vor und hängst daran -8 an. Du brauchst also für H eine Schleife, mit der du alle Elemente daraus abarbeitest. Falls Python (kenne ich leider nicht) nicht mit Texten arbeitet, kann das auch so aussehen, dass du statt der Texte Listen hast:
H=stairs(6,steps), also
H = [ [mm] [\[1,3,6],[1,4,6] [/mm] ], und du machst nun daraus H = [ [mm] [\[1,3,6,8],[1,4,6,8] [/mm] ]. Dann ergänzst du lst um [1,3,6,8],[1,4,6,8]. Im nächsten Schritt rufst du H=stairs(5,steps) auf, machst mit dem neuen H das selbe, dann nochmals mit H=(1,steps).
Am Ende ist lst=[ [mm] [\[1,3,6,8],[1,4,6,8],[1,3,5,8],[1,8] [/mm] ], und das sind alle mgl. Wege zur 8. lst wird zurückgegeben.
|
|
|
|
