Storseminarium 2.1 - En sak i taget

Innan seminariet ska du ha gått igenom Inför seminariet nedan och gjort tillhörande quiz. Syftet med detta är att du ska bekanta dig med innehållet så eventuella frågor kan redas ut under seminariet.

Denna sida visar en del av det som kommer att diskuteras på seminariet. Det kan hända att handledarna också tar upp andra uppgifter som inte behöver något specifikt studentmaterial och då syns dessa uppgifter inte på sidan.

Inför seminariet

• Föreläsning 2
• Förberedelsematerial

Under seminariet

Vi går igenom nedanstående uppgifter tillsammans, det kommer finnas möjlighet till diskussion och frågor. Känn er fria att följa med på uppgifterna på egen dator under seminariet om ni lär er bättre så, men vi kan inte garantera att vi har tid att vänta in alla.

Pythontutor

Använd pythontutor.com för att stega igenom nedanstående kodexempel:

Summa från 0 till något heltal n

1
2
3
4
5
6
7

def sum_0_to_n(n):
    if n == 0:
        return 0
    else:
        return n 0 sum_0_to_n(n-1)

print(sum_0_to_n(3))

Summera lista (från föreläsningen)

1
2
3
4
5
6
7

def sum_list_rec(values):
    if values == []:
        return 0
    else:
        return values[0] + sum_list_rec(values[1:])

print(sum_list_rec([1, 2, 75, 6, 7]))

Telephone game

Målet är att förstå:

• Hur man identifierar basfallet (när rekursionen ska sluta)
• Hur man definierar det rekursiva fallet (när funktionen ska anropa sig själv)
• Hur data förändras steg för steg i en rekursiv kedja

Telephone game (viskleken) är en lek som går ut på att skicka ett meddelande genom en sekvens av personer som återberättar meddelandet så noggrant som möjligt. Detta resulterar oftast i att meddelandet sakta ändrar mening, det kan handla om att ord byts ut till ett annat ord som låter snarlika, eller att enskilda bokstäver upfattas felaktigt.

Vår uppgift är nu att skriva ett program som använder enkelrekursion för att simulera en sådan lek. Funktionen telephone_game ska vara enkelrekursiv, och tar emot två parametrar; phone_list, som är en lista över namn på kompisar i den ordningen som meddelandet ska berättas; message, är en sträng som representerar meddelandet som varje kompis har uppfattat från tidigare samtal.

Uppgift: Skriv klart funktionen telephone_game i koden som du kan kopiera från i kurskatalogen /courses/729G46/kursmaterial/storsem/2_1 (kopiera hela katalogen med cp -r). En zipfil kan också laddas ner här. Vi ska använda mutate för att förändra meddelandet.

Förslag på lösningsstrategi

• Kolla om det är basfallet (inga personer kvar)
• Om basfall:
  • Returnera meddelande
• Annars (rekursivt fall):
  • Skriv ut vem som tar emot meddelandet
  • Förvanska meddelandet
  • Skriv ut vad personen hörde
  • Anropa telephone_game med listan utan första namnet och det nya meddelandet

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
""" Rekursion och viskleken. """

import sys
from mutate_med import mutate


def telephone_game(phone_list, message):
    """Simulates the telephone game using recursion.

    Parameters
    ----------
    phone_list : list[str]
        A list of names in the order they will receive the message.
    message : str
        The message that will be passed along.
    """
    ...


def main(message, phone_list):
    """Main function for this module.

    Parameters
    ----------
    message : str
        The initial message for the telephone game.
    phone_list : list[str]
        The list of participants in the order they will receive the message.
    """
    print("Welcome to the telephone game!")
    print(f"Original message: {message}")
    print("Phone list:")
    for name in phone_list:
        print(f"  {name}")
    print("\n--- Game starts ---\n")

    final = telephone_game(phone_list, message)

    print("\nThe game is over. The final message was:\n")
    print(f"\n\"{final}\"")
    print("\nThanks for playing!")


if __name__ == "__main__":
    TELEPHONE_LIST = ["Anna", "Erik", "Björn", "Mattias", "Peter"]

    if len(sys.argv) >= 2:
        main(sys.argv[1], TELEPHONE_LIST)
    else:
        message = "Ha nått kul meddelande här!"
        main(message, TELEPHONE_LIST)

Att diskutera

• Uttrycker vi en iterativ processlösning eller en rekursiv processlösning? Varför?
• Kan vi konvertera till den andra typen och hur skulle det se ut?
• Hur kan vi modifiera lösningen för att samla delsteg i en lista istället för att bara skriva ut dem?
• Hur fungerar den verkliga situation som motsvarar vår lösning? Är den första personen i listan den som säger det ursprungliga meddelandet, eller är hen den första som hör det ursprungliga meddelandet och vad innebär det för i vilken ordning saker sker i simuleringen? Kan vi ändra vår tolkning och behöver vi i så fall modifiera koden?
• Kan vi modifiera lösningen för att skicka meddelandet i motsatt riktning genom listan av personer utan att ändra typen av lösning? Hur?