Labb 5: Rekursion, breddenförstsökning del 2
- Inlämningsdatum 29 sep 2023 av 18:00
- Poäng 10
- Lämnar in en filuppladdning
- Filtyper py
Mål | Läs i kursboken |
Rekursion, nästlade noder. Denna laboration är en fortsättning på förra labben. Repetera Föreläsning 3, Övning 4 |
Kapitel 5.1 - 5.6 Links to an external site. |
□ Förberedande uppgifter
Här är en rekursiv funktion för utskrift av en lista:
def utskrift(lista): if len(lista) > 0: print(lista[0]) |
- Provkör funktionen med listan [1,2,3,4,5]
- Rita Stack Frames (enligt boken kap 5.5 Links to an external site. och 5.6 Links to an external site. ) för att visa hur rekursionen fungerar.
- Byt plats på print-satsen och det rekursiva anropet (så att print-satsen hamnar sist i funktionen).
- Provkör igen
- Rita Stack Frames och förklara resultatet.
□ Förbättra söt-sur
Det tråkiga med programmet från förra labben är att det bara talar om att det finns en lösning. För att programmet ska kunna skriva ut alla ord på vägen mellan söt och sur måste varje ord kunna peka på sin förälder. Vi inför en ParentNode för att hålla reda på både ordet och dess förälder.
class ParentNode: def __init__(self, word, parent = None): self.word = word self.parent = parent |
Huvudprogrammet ska skapa ett ParentNode-objekt och lägga in startordet (som word-attribut). Det som sätts in i kön och plockas ut ur kön är nu inte längre ord utan ParentNode. Det betyder att du måste ändra en del i funktionen makechildren från förra labben.
När makechildren finner slutordet ska den skriva ut hela kedjan genom ett anrop writechain(slutordsnod). Metoden writechain() ska skrivas rekursivt, så att man får ut kedjan med slutordet sist.
Om kön töms utan att någon lösning påträffats bör programmet meddela att det är omöjligt. Och när en lösning skrivits ut bör programmet avbryta körningen. Ett sätt att göra det är att definiera en egen Exception:
class SolutionFound(Exception): pass |
och göra raise SolutionFound när lösningen hittats.
Betyg
Denna labb kan endast ge betyg E. Du måste lämna in den och redovisa den i tid för att få göra labbarna för högre betyg i period 2.
Redovisning
Labben lämnas in indivuellt med "Lämna in uppgift"-knappen högst upp på sidan, och ska redovisas muntligt av bägge gruppmedlemmarna. Skriv gruppmedlemmarnas namn i kommentarsfältet!
Vid redovisningen ska du kunna
- visa upp och redogöra för de förberedande uppgifterna ovan,
- rita och förklara skillnaden i datastrukturen jämfört med förra labben,
- visa hur utskriften av lösningen fungerar med din rekursiva funktion
Ingen Kattis-inlämning för denna labb!