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()
isEmpty()

Du ska implementera kön som en länkad lista. Noderna i listan är objekt som vardera innehåller två attribut: ett värde (value) och en referens till nästa objekt (next). Klassen Node kan se ut så här:

class Node:
    def __init__(self, x):
        self.value = x    # Kan referera till värde av valfri typ
        self.next = None  # Ska peka på nästa nod

Själva Queue-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 koder - resten får du fylla i själv!

class Queue:

    def __init__(self): 
       self.first = None
       self.last = None

    def __str__(self):
	"""Returnerar köns element som en sträng.
           Tips: Titta på kursens FAQ (under Hjälp)"""

    def put(self,x):
        """Stoppar in x sist i kön """
        ny = Node(x)
        if self.first == None:
          - - -               
        else:                 
          - - -               

    def get(self):
        """Plockar ut och returnerar det som står först i kön """
        - - -

    def isEmpty(self):
        """Returnerar True om kön är tom, False annars """
        - - -

Klassen Node kan stå överst i filen, sedan klassen Queue, och sist 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.

Innan du tar itu med kortkonsten kan du prova din kö med följande testprogram:


   q.put(1)
   q.put(2)
   x = q.get()
   y = q.get()
   print x,y   # 1 2 ska komma ut

När testprogrammet fungerar kan du använda det för att lösa kortkonstens gåta. Inmatningstips är att använda raw_input().split(). 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.

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. (Till exempel kanske man vill flytta värden från en kö till en annan med

   q1 = Queue()
   q2 = Queue()
   - - -
   x = q1.get()
   q1.put(x)

). Gör nu så här: klipp ut nodklassen och köklassen från ditt program och klistra in i en ny fil QueueFile.py.

Huvudprogrammet lab2.py börjar lämpligen med raden from QueueFile import Queue, då går det att använda klassen utan att den syns i programmet.

När allt fungerar som det ska bör du ta en extra titt på koden. Är den kommenterad och begriplig? Den här labben ska redovisas tillsammans med labb 3 och 4.

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?

Laboration 2 - Kortkonst

En kö av noder

En abstrakt köklass

Frivilliga extrauppgifter

Suveränt jobbat av ....................................... fastslår......................... den .............