Till KTH:s startsida Till KTH:s startsida

Laboration 2

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

  1. 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

  2. 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
    
  3. Skriv Trollkarlsprogrammet

    Skriv ett program som simulerar korttricket (se exemplet överst i labben).

    Inmatningstips är att användainput() för att läsa in hela raden och sensplit() 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.

  4. 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.
  5. 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 ochLinkedQ, 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. Använd samma gränssnitt som i uppgift 1:

    • put(x)
    • x = get()
    • isEmpty()

    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!

  6. Trollkarlsprogrammet med LinkedQ

    Ändra import-satsen i trollkarlsprogrammet så att du importerar klassenLinkedQ istället förListQ. 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.

Betyg

betyg E: Ditt program löser uppgifterna ovan, du kan rita och förklara hur metoderna fungerar.

betyg C: Kraven för E uppfyllda + Perfekt program + Labben inlämnad via KTH Social i tid och redovisad i tid (se datum under Laborationer).

betyg A: Kraven för C uppfyllda + en av följande 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. Tricket här är att använda en stack som hjälp för att kunna vända på kortens ordning.
  • 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?

                                                     Fler avslöjanden från trolleriprofessorn.

Alexander Baltatzis created page 14 January 2014

commented 26 January 2014

I labbtydelsen står det:

"Skriv en egen klass ListQ där du implementerar en kö med hjälp av pythons inbyggda lista."

Betyder det att jag skriver en klass som importerar pythons queue och använder den, min klass är bara en wrapper, eller ska jag skriva logiken till en kö?

Teacher commented 26 January 2014

Du ska inte använda Pythons inbyggda queue utan pythons inbyggda lista.

commented 27 January 2014

Vilket datum gäller för redovisning? 10 Oktober låter sent..

Kommer det finnas möjlighet till hjälp på ordinarie lab-tider de kommande tre veckorna?

Teacher commented 27 January 2014

Hoppsan - det är höstens datum :-)

Titta på huvudsidan för labbarna, där finns datum för inlämning och redovisning.

commented 27 January 2014

Har det blivit något fel i instruktionerna kanske?

"Vilken ordning ligger korten i? 3  1   4   2   5
De kommer ut i denna ordning: 1 2 3 5 4"

Borde inte ordingen som korten låg i vara 3 1 5 2 4 ?
Om inte så uppskattar jag gärna en förklaring :)

Teacher commented 27 January 2014

Det är den som kör programmet som bestämmer i vilken ordning hen vill lägga korten...

commented 27 January 2014

Ha, såg nu att det stod "1 2 3 5 4" och inte "1 2 3 4 5".. Never mind!

commented 5 February 2014

Innefattar "perfekt program" att vi ska ha testfall även i denna labb? Tänkte eftersom det inte står explicit nånstans.

Teacher commented 6 February 2014

Varför inte? Testfall sparar tid när du utvecklar programmet. 

commented 6 February 2014

Är tanken att man ska ha gjort, och skicka in, två olika program eller att man utvecklar det första hela vägen tills uppgift 6 då det är klart?

Teacher commented 6 February 2014

Bägge varianterna fungerar, men enklast är nog att du lägger bägge klasserna i samma fil när du skickar in.

commented 7 February 2014

Måste man använda stackar i lösningen för baklänges-simuleringen?