word3.txt
från förra laborationen.
Ditt program ska finna en kortare väg till gud än den här föreslagna. Lösningsprincipen gås igenom nedan och den beskrivs ofta i läroböcker för det analoga problemet att finna kortaste väg i en graf.
Lägg stamfadern som första och enda post i en kö. Gör sedan följande om och om igen: Plocka ut den första ur kön, skapa alla söner till denne och lägg in dom sist i kön. Första förekomsten av det sökta ordet ger kortaste lösningen.
Man kan spara in både tid och utrymme om man undviker att skapa söner som är kopior av tidigare släktingar (t ex mans son fan), så kallade dumsöner.
fan.py
utgå från förra labben, som ju har två binärträd.
Nu kallar vi dom svenska
och gamla
.
Huvudprogrammet ska läsa in ordlistan, fråga efter startord och slutord,
och göra anropet makesons(startord)
. Denna funktion går systematiskt
igenom alla sätt att byta ut en bokstav i startordet, kollar att det nya
ordet finns i ordlistan men inte finns i gamla
och skriver i så fall ut det nya ordet på skärmen.
Om du gjort rätt ska fan få sjutton söner.
q
. I stället för att skriva
ut sönerna på skärmen puttar makesons
in dom i kön. Huvudprogrammet
puttar in startordet i kön och går sedan i en slinga
while not q.isempty(): makesons(q.get())När
makesons()
stöter på slutordet gör den utskriften
print "Det finns en väg till",slutord;Provkör med lite olika start- och slutord, bland annat ful - gud och ute - hit.
node
som ser ut så här.
class node: word = None father = NoneHuvudprogrammet skapar ett sådant objekt och lägger in startordet. Det som sätts in i kön och plockas ut ur kön är nu inte längre ord utan
node
, och det medför några ändringar i makesons
.
När makesons
finner slutordet vill den skriva ut hela kedjan
genom ett anrop writechain(son)
. 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
.
countchain(son)
som
returnerar kedjans längd. Ledning: Om startord och slutord byter roller
ändrar det inte kedjans längd.
Längst från varandra: Vilka två ord är längst från varandra?