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 som uppför sig så här:
Vilken ordning ligger korten i?
3 1 4 2 5
De kommer ut i denna ordning:
1 2 3 5 4
En kö av noder
Programmet bygger först upp en kö av inlästa tal, sedan manipulerar
den kön enligt beskrivningen.
Med den abstrakta datastrukturen kö kan man göra tre saker:
stoppa in något, plocka ut något och kolla om kön är tom. Det motsvarar
anropen
put(x)
,
x=get()
och
isempty()
. Ditt huvudprogram ska klara sin uppgift med dessa
anrop, utan att bry sej om hur kön implementerats. Innan du tar itu med
kortkonsten kan du försöka få följande testprogram att fungera.
put(1)
put(2)
x=get()
y=get()
print x,y # 1 2 ska komma ut
Låt till en början kön finnas i samma fil test.py
som
huvudprogrammet, så man kan lätt se att
kön består av noder som innehåller ett tal och en pekare var.
Klassen node
kan stå överst i filen, sedan kan dom
globala köpekarna first
och last
komma, sedan definieras put(x), get()
och
isempty()
och sist kommer huvudprogrammet.
Det är lite knepigt att programmera put(x)
eftersom
det blir två fall, beroende på om kön är tom eller inte. Det är
till stor hjälp att rita upp situationerna, så gör det.
När testprogrammet fungerar gör du om det så att det löser kortkonstens
gåta. Inmatningstips är att använda raw_input().split()
.
Experimentera sedan med olika inmatade ordningar och lös kortkonstens gåta!
Programmet konverserar också intelligent. Mata till exempel in
meningen
JAG GILLAR NÄR DU KRAMAR MEJ
.
En abstrakt köklass
Men labben är inte slut med det.
Om man ska kunna ha flera köer igång måste man ha flera köobjekt som
har var sina
first
och
last
. Man vill till exempel
kunna flytta värden från en kö till en annan med
q1=queue()
q2=queue()
- - -
x=q1.get()
q1.put(x)
Låt filen
queue.py
börja med
class queue:
och kopiera
över all kökod och nodklassen. Nu ska varje anrop ha en
self
-parameter och i stället för två globala pekare används
self.first
och
self.last
.
Huvudprogrammet
lab2.py
börjar lämpligen med from queue import queue
,
då förblir nämligen nodklassen osynlig.
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 .............