Laboration 5

Laboration 5: Breddenförstsökning - visa vägen

Läsning

Läs kapitel 3.1 - 3.3 om Rekursion i kursboken (från Objectives fram till och med Stack Frames).

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])
        utskrift(lista[1:])

1. Provkör funktionen med listan [1,2,3,4,5]
2. Rita Stack Frames (enligt boken) för att visa hur rekursionen fungerar.
3. Byt plats på print-satsen och det rekursiva anropet (så att print-satsen hamnar sist i funktionen).
4. Provkör igen
5. 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. Det är alltså inte typen String du ska arbeta med utan en ParentNode som ser ut så här.

class ParentNode:
    def __init__(self, word, parent = None):
        self.word = word
        self.parent = parent

Huvudprogrammet ska skapa ett sådant 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, och det betyder att du måste ändra i funktionen makechildren.

När makechildren finner slutordet vill den skriva ut hela kedjan genom ett anrop writechain(child). 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 sys.exit() om man importerar modulen sys. Ett annat sätt är definiera en egen Exception:

class SolutionFound(Exception):
    pass

och göra raise SolutionFound när lösningen hittats.

Redovisning

Labben lämnas in via git  och redovisas muntligt av bägge gruppmedlemmarna.

Vid redovisningen ska du kunna

• visa upp och redogöra för de förberedande uppgifterna ovan,
• förklara i detalj hur breddenförstsökningen fungerar,
• visa hur utskriften av lösningen fungerar

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 nästa period.