Laboration 2 - Kortkonst
"Trollkarlen tar ut de tretton spaderna ur leken, håller dem som en
kortlek med baksidan upp och lägger ut dem på följande sätt: Översta
kortet stoppas underst, nästa kort läggs ut med framsidan upp, nästa
kort stoppas underst, nästa kort läggs ut osv. Till publikens
häpnad kommer korten upp i ordning ess, tvåa, trea...
Utförande: Man ordnar i hemlighet korten enligt följande."
|
Ja, här bryter vi citatet ur Liberg: Trolleri för alla.
I labbuppgiften ingår nämligen att ta reda på kortkonstens hemlighet!
Du ska därför göra ett program där man kan simulera korttricket så här:
Vilken ordning ligger korten i?
3 1 4 2 5
De kommer ut i denna ordning:
1 2 3 5 4
Uppgifter
-
ListQ - en kö med Pythons lista
Med den abstrakta datastrukturen kö kan man göra tre saker:
stoppa in något sist, plocka ut det som står först och kolla om kön är tom. Det motsvarar
anropen
-
put(x)
-
x = get()
-
isEmpty()
Skriv en egen klass ListQ där du implementerar en kö med hjälp av
pythons inbyggda lista.
Till din hjälp har du Pythons
listmetoder
-
Testa ListQ
Prova din kö med följande testprogram:
q = ListQ()
q.put(1)
q.put(2)
x = q.get()
y = q.get()
print x,y # 1 2 ska komma ut
|
-
Skriv Trollkarlsprogrammet
Skriv ett program som simulerar korttricket (se exemplet överst i labben).
Inmatningstips är att använda raw_input()
för att
läsa in hela raden och sen split()
för att dela upp den.
Experimentera sedan med olika inmatade ordningar och lista ut i vilken ordning
korten ska ligga innan man börjar trolla för att man ska få ut alla
tretton i rätt ordning!
Programmet konverserar också intelligent. Mata till exempel in
meningen
JAG GILLAR NÄR DU KRAMAR MEJ
.
Skapa en ListQ-modul
Gör nu så här:
klipp ut klassen från ditt program och
klistra in i en ny fil listQFile.py
Importera klassen till huvudprogrammet med raden
from listQFile import ListQ
Nu går det att använda klassen utan att den syns i programmet.
-
LinkedQ - en kö av noder (länkad lista)
Nu ska du istället implementera kön som en länkad lista.
Då behövs två klasser: Node
och LinkedQ
,
som kan ligga i samma fil.
Noderna i listan är
objekt som vardera innehåller två attribut: ett värde (value
)
och en referens till nästa objekt (next
).
Själva LinkedQ-klassen har två attribut: first
som håller reda på den första noden i kön och last
som pekar ut den sista. Här är en del av koden - resten får
du fylla i själv!
Som inspiration kan du titta på
stack.py från Övning 1.
Det är extra knepigt att programmera put(x)
eftersom
det blir två fall, beroende på om kön är tom eller inte.
Rita upp bägge fallen (lådor med pilar) innan du skriver koden!
-
Trollkarlsprogrammet med LinkedQ
Ändra import-satsen i trollkarlsprogrammet så att du importerar
klassen LinkedQ
istället för ListQ
.
Provkör. Fungerade det? Då har du lyckats implementera
den abstrakta datastrukturen kö på två olika sätt.
Testa också att rita en blomma.
När allt fungerar som det ska bör du ta en extra titt på koden.
Är den kommenterad och begriplig? Hur har du testat programmet
för att se att det fungerar
Den här labben ska redovisas tillsammans
med labb 3 och 4.
Fler avslöjanden från
trolleriprofessorn.
Frivilliga extrauppgifter
Bakfram kortkonst:
Det är tidskrävande att experimentera sej fram till rätt utgångsordning
på korten. En genial metod är förstås att göra kortkonsten baklänges,
och det ska du programmera. Då är det det sista inmatade kortet som man
ska ta sej an först och därför behövs en stack för tillfällig lagring.
Sedan vidtar köjobbet men nu måste förstås kön ha
first
på understa kortet och
last
på översta.
För att slutligen skriva ut kortbunten uppifrån och ner måste man
alltså gå via stacken igen. Puh!
Misslyckad blandning:
Korthajarnas riffelblandning går till så att leken delas på mitten
och de båda halvlekarna rifflas ihop så att undre halvlekens översta
kort hamnar överst och övre halvlekens understa kort hamnar underst.
Ryktet säger att den här blandningen inte får göras för många gånger,
för då är korten tillbaka i ursprunglig ordning. Kan det stämma?
För att programmera det här behöver du tre köer.
Ditt program ska fråga efter antal kort (ett jämnt tal) och antal
blandningar och skriva ut hur ordningen blir efteråt. Testa med
6 kort och tre blandningar eller 62 kort och sex blandningar. Hur
många behövs för vår vanliga kortlek med 52 kort?
Suveränt jobbat av ....................................... fastslår......................... den .............