Pythonuppgifter, kapitel 10. Godtyckligt nästlade strukturer

Att lära dig från uppgifterna

• Använda rekursion för att traversera godtyckligt nästlade strukturer.
• Lösa problem i nästlade strukturer med hjälp av dubbelrekursion.
• Kombinera rekursion och iteration för att hantera godtyckligt nästlade strukturer.

Man kan få max 52 poäng och för att få godkänt krävs 20 poäng. Försök dock att lösa fler uppgifter då inte alla fel upptäcks av rättningsskriptet. Om ni har lite marginal kan ni kanske bli godkända även om assistenten som rättar hittar något sådant fel.

Vi har tidigare använt rekursion för att lösa problem som att beräkna fakulteten av ett tal, summera en sekvens eller vända på en sträng. I samtliga fall har vi vid varje anrop av funktionen bara behövt göra ett ytterligare anrop av samma funktion. Vi har använt villkorssatser för att avgöra vilket anrop som skall göras, eller hur resultatet av anropet ska hanteras, men vi har alltid bara utfört som mest ett anrop. Denna typ av rekursion kallas för enkelrekursion och kan ses som ett alternativ till iteration.

Vi ska nu börja titta på situationer där vi vid varje anrop av funktionen behöver göra flera anrop av samma funktion. Denna typ av rekursion kallas för dubbelrekursion eller multipel rekursion. Detta kan inte på ett lika självklart sätt ersättas med iteration och det är här som rekursion verkligen kommer till sin rätt.

Vi kommer att börja med ett par klassiska matematiska exempel, för att sedan gå in på hur vi kan använda dubbelrekursion för att hantera godtyckligt nästlade strukturer.

Uppgift 10.1 (2p)

Skriv en funktion fib(n) som returnerar fibonaccitalet för position n.

Beräkning av fibonaccital är ett klassiskt exempel på dubbelrekursion. Fibonaccitalen definieras som följer:

$$ F(n)= \begin{cases} 0 & \mbox{om }n=0; \\ 1 & \mbox{om }n=1; \\ F(n-1)+F(n-2) & \mbox{om }n>1. \end{cases} $$

Med andra ord är fibonaccitalet för position n summan av fibonaccitalen för position n-1 och n-2. Detta innebär att för att beräkna F(n) måste vi först beräkna både F(n-1) och F(n-2), vilket i sin tur kräver ytterligare anrop av funktionen.

Du kan läsa mer om fibonaccital på Wikipedia.

OBS! Eftersom denna funktion är rekursiv och gör flera anrop till sig själv kan den bli mycket långsam för större värden av n. För att undvika detta, testa endast din funktion med små värden av n (t.ex. n < 20). Det är värt att veta att det finns mer effektiva sätt att beräkna fibonaccital, men här ska vi fokusera på den dubbelrekursiva implementationen enligt specifikationen ovan.

Exempel

>>> for i in range(20): print(fib(i), end=' ')
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181

Uppgift 10.2 (10p)

Skriv en funktion pascal(row, col) som returnerar talet på rad row och column col i pascals triangel. Du får inte använda den uttryckliga formeln för binomialkoefficienter för att lösa uppgiften.

Du kan läsa om pascals triangel på Wikipedia.

Tips 1: Börja med att sätta upp villkor för vilka värden på row och col som funktionen ska returnera 1, dvs för vilka värden på row och col är värdet högst upp, eller på en ytterkant.

Tips 2: Värdet är högst upp i triangeln när rad 1 efterfrågas. Värdet är på vänsterkanten när kolumnen är 1 och på högerkanten när rad och kolumn är samma tal.

Tips 3: Värdena som inte är på en ytterkant är summan av värdena ovanför. Du kan använda rekursiva anrop med modifierade rad och kolumnvärden för få dessa två värden.

Tips 4: För alla värden i Pascals triangel som inte är högst upp, eller på en ytterkant gäller $pascal(row, col) = pascal(row-1, col-1) + pascal(row-1, col)$

Exempel

>>> pascal(1, 1)
1
>>> pascal(2, 2)
1
>>> pascal(3, 2)
2
>>> pascal(5, 2)
4
>>> pascal(5, 3)
6
>>> pascal(5, 4)
4
>>> pascal(6, 3)
10

Vi ska nu titta på hur vi kan hantera godtyckligt nästlade strukturer med hjälp av rekursion. En godtyckligt nästlad struktur är en struktur som kan innehålla andra strukturer av samma typ (eller av andra kända typer), vilket innebär att vi inte vet i förväg hur djupt nästlingen kan gå.

Uppgifterna ska lösas med rekursion men ni får själva bestämma om ni vill använda explicit dubbelrekursion, en kombination av iteration och rekursion, eller någon form av ömsesidig rekursion. Ett förslag är att ni testar olika approacher på olika uppgifter och känner efter vad ni är mest bekväma med.

Uppgift 10.3 (5p)

Skriv en funktion keep_if_even_all(lst) som gör som keep_if_even i kapitel 4, men den undersöker också listor med godtycklig nästling. Om en lista bara innehåller udda tal ska den tomma listan sparas. Den ursprungliga listan får inte förändras.

Exempel

>>> keep_if_even_all([1, 2, [1, 3], [4, 7], 6])
[2, [], [4], 6]
>> keep_if_even_all([1, 2, [3, 4], [5, [6, 7, [[8]]]]])
[2, [4], [[6, [[8]]]]]

Uppgift 10.4 (5p)

Skriv en funktion is_in_list(lst, element) som returnerar True om element finns i lst, annars returnerar funktionen False. Funktionen ska undersöka även godtyckligt nästlade listor. Den ursprungliga listan får inte förändras.

Exempel

>>> is_in_list(["a", "b", "b", "a"], "b")
True
>>> is_in_list(["a", "b", "b", "a"], "c")
False
>>> is_in_list([1, 2, 3, [4, 5, [6]]], 6)
True
>>> is_in_list([1, 2, 3, [4, 5, [6]]], 7)
False

Uppgift 10.5 (5p)

Skriv en funktion count_all(lst) som returnerar antalet element som finns i lst. Funktionen ska undersöka också hantera godtyckligt nästlade listor. Ett annat sätt att tolka det är att ni ska räkna antalet löv i träd-tolkningen av lst.

Exempel

>>> count_all(["a", "b", "b", "a"])
4
>>> count_all([1, 2, 3, [4, 5, [6]]])
6

Uppgift 10.6 (5p)

Skriv en funktion reverse_rec_all(lst) som gör som reverse_rec från kapitel 4 men den undersöker också godtyckligt nästlade listor. Den ursprungliga listan får inte förändras.

Exempel

>>> reverse_rec_all([1, [2, 3, 4], 5, 6])
[6, 5, [4, 3, 2], 1]
>>> reverse_rec_all([1, [2, 3], 4, [5, [6]]])
[[[6], 5], 4, [3, 2], 1]

Uppgift 10.7 (10p)

Skriv en funktion subst_all(lst, element, new_value) som returnerar en ny lista där alla förekomster av element har byts ut mot new_value. Funktionen ska också ersätta förekomster av element med new_value i godtyckligt nästlade listor. Den ursprungliga listan får inte förändras.

Exempel

>>> subst_all(["a", "b", "b", "a"], "b", "l")
['a', 'l', 'l', 'a']
>>> subst_all([1, 2, 3, [4, 5, [6]]], 6, "x")
[1, 2, 3, [4, 5, ['x']]]

Uppgift 10.8 (10p)

Skriv en funktion remove_duplicates(lst) som returnerar en version av lst där eventuella dubletter tagits bort. Bara den sista förekomsten av ett värde får vara kvar. Den ursprungliga listan får inte förändras.

Tips: Det är lämpligt att ha en variabel, t.ex. kallad seen som håller koll på vilka element som redan tagits med i resultatet och inte ska läggas till igen.

Exempel

>>> remove_duplicates([1, 2, 3, 1, 4, 3])
[2, 1, 4, 3]
>>> remove_duplicates([[1], [2, 3], [[1, 4], [[3]]]])
[[], [2], [[1, 4], [[3]]]]
>>> remove_duplicates([[1], [1, 1], [[1, 1], [[1]]]])
[[], [], [[], [[1]]]]

Använda rättningsskriptet

OBS! Rättningsskriptet kan bara användas från LiUs Linux-miljö, dvs. är inloggad på en Linux-dator i ett PUL på Campus, har anslutit via VSCodes RemoteSSH, är inloggad på en dator i ett PUL via RDP, eller är inloggad via ThinLinc.

Du kan bara köra rättningsskriptet för ett specifikt kapitel (t.ex. Pythonuppgifter, kapitel 2) en gång var åttonde minut. Detta är för att ni även behöver lära er hur ni testar er egen kod; ni ska inte vara beroende av att det finns ett rättningskript som hjälper er.

Innan du kör rättningsskriptet

Kommentera ut egna testanrop i din kodfil innan du kör rättningsskriptet. Rättningsskriptet kommer att köra din kodfil och om det finns testanrop i filen kan det störa rättningen. Du kan kommentera ut rader i Python genom att ställa dig på raden och trycka Ctrl+’ (tangenten ’ är oftast till höger om Ä på ett svenskt tangentbord) i VS Code. Du kan också markera flera rader och trycka samma tangentkombination för att kommentera ut alla markerade rader.

Köra rättningsskriptet

För att rätta din fil skriver du nedanstående ($ skrivs inte utan representerar prompten i terminalen):

1$ /courses/TDDE44/kursmaterial/pyuppg/pytest.sh <kapitel> <kodfil>

• Ersätt <kapitel> med det kapitel vars uppgifter koden löser, t.ex. 1 för att rätta kapitel 1, 2 för kapitel 2, osv.
• Ersätt <kodfil> med namnet på filen som innehåller din kod.
• OBS! Du måste stå i samma katalog som filen som du vill rätta.
• OBS! Du får inte döpa din kodfil till ett namn med en punkt i filnamnet utöver punkten innan ändelsen py. Alltså, pyuppg1.py fungerar, pyuppg_kap.1.py fungerar inte.

Exempel

Exempel för Pythonuppgifter kapitel 2 om filen med dina lösningar är döpt till pythonuppg_2.py

1$ /courses/TDDE44/kursmaterial/pyuppg/pytest.sh 2 pythonuppg_2.py

Exempel för Pythonuppgifter kapitel 3 om filen med dina lösningar är döpt till pyuppg3.py

1$ /courses/TDDE44/kursmaterial/pyuppg/pytest.sh 3 pyuppg3.py

#### POÄNG (100 poäng behövs för GODKÄND UPPG) ####

UPPG 1.1: 5 poäng.
UPPG 1.2: 5 poäng.
UPPG 1.3: 5 poäng.
UPPG 1.4: 5 poäng.
UPPG 1.5: 10 poäng.
UPPG 1.7: 10 poäng.
UPPG 1.8: 10 poäng.
UPPG 1.9: 10 poäng.
UPPG 1.10b: 5 poäng.
UPPG 1.11: 15 poäng.
UPPG 1.12: 15 poäng.


#### SAKNADE UPPGIFTER ####

Kontrollera stavning på din funktioner. Stora och små
bokstäver spelar roll.

UPPG 1.10a saknar funktion: 'first_in_list'
UPPG 1.10c saknar funktion: 'last_in_list'


#### FEL vid TEST ####

Felsök genom att ha testanrop längst ner i din kodfil och
skriv ut resultaten. Kontrollera också så att du har mellanrum
på rätt ställe och att stora/små bokstäver stämmer överrens.

UPPG 1.6: Fel påträffades.

#### ANTAL POÄNG: 95
#### Du är INTE godkänd på Pythonuppgifter 1.
#### 5 poäng saknas.

------------------------ KOPIERA FRÅN RADEN UNDER DENNA ------------------------
dXBwZzEvaW5mby50eHRVVAkAAz99zVc/fc1XdXgLAAEE9QEAAAQUAAAABcHLEcIgEADQO1VsA3FY
zVd1eAsAAQT1AQAABBQAAABQSwMEFAAAAAgAiIElSZnJPKxkAAAAcgAAABgAHABqb2RmbzAxLXB5
AjhLN2E/iophTDike9+T7dQCwWNePC0+AeaCoWBy89Bfgdcutnt01j4K/FR+qxQY1xzjgbdxud6+
AGpvZGZvMDEtcHl1cHBnMS9taW5pZmllZC5weVVUCQADP33NVz99zVd1eAsAAQT1AQAABBQAAACN
UEsDBAoAAAAAAIiBJUkAAAAAAAAAAAAAAAAQABwAam9kZm8wMS1weXVwcGcxL1VUCQADP33NVz99
kstugzAQRfd8hUU3pCGhRMomUlb9jLayDIzBjbEte4iavy/YPEJaqV0gM3fO3Bk/RGu0RWKZqnQb
VcCJBeysolxcIdmcojEm8SDEnjBWKFwAHyYhv/EAqyrqsJdrt7Jo4DPexo6p4NM5oNgAvTLrsSuT
HZyPM+/j5+OKZbZO2Gi+NJ+VuXZSVsVSKCgssMtqKssqkr+rYTmEwVxXoGUlJn6CPPXL4a4m6Lug
hxIjBdJCSJmwVncKU9W1BViqOTWgjYS78kBkj4Q3KrUqGYLqv/kMXZ66+/Yu37rQlgvrkArVb82N
47rHOd3by0eYEXrz6k86D7Rk/3De5ZO1hBJpeEY/6aDvy0aLEqa0L6xBgR32avQFWq2oYi0kxgIX
X+BS13H/E656EM/rVhPZ33xgH/KzQUQG5/Nvxxs8xl7LExr46Im89g8GoSLFjZhbK5TgAixJGkTj
TllWC2y6Yl/qNpOCo+Y8W7BN9A1QSwMEFAAAAAgAiIElSclUPoaqAAAAqAEAAB8AHABqb2RmbzAx
zZoKdEnH7GDmmeo9xVhT5JpzNVmFaOPAK6G5P1BLAwQUAAAACACIgSVJoN99PmsBAABgAwAAGwAc
LXB5dXBwZzEvcHl1cHBnMXRlc3QubG9nVVQJAAM/fc1XP33NV3V4CwABBPUBAAAEFAAAAOPiUgYC
hQD/wy1+7goahgYGCgX5h5fkpSskpWYc3lZWrJB2eFuRgru/izdQhYtCaECAu6YCSA8XF4itYKhn
aKVgCtWkBxMzwiJmjEXMBIuYqZWCoQG6oBk2QXNsghbYBC2xCRoaJGKx3tAgCatoMjZRoN8NMUWN
CgAAAAAAiIElSQAAAAAAAAAAAAAAABAAGAAAAAAAAAAQAO1BAAAAAGpvZGZvMDEtcHl1cHBnMS9V
VAUAAz99zVd1eAsAAQT1AQAABBQAAABQSwECHgMUAAAACACIgSVJmck8rGQAAAByAAAAGAAYAAAA
AAAAUEsBAh4DFAAAAAgAiIElSaDffT5rAQAAYAMAABsAGAAAAAAAAQAAAKSBAAEAAGpvZGZvMDEt
AAABAAAApIFKAAAAam9kZm8wMS1weXVwcGcxL2luZm8udHh0VVQFAAM/fc1XdXgLAAEE9QEAAAQU
UEQhIezoF+LoAw1noLShKUTYpVTh8BKk8C04vFQhoLIkIz+vtKAgPTOtRMFQkUtBgQsAUEsBAh4D
JUnJVD6GqgAAAKgBAAAfABgAAAAAAAEAAACkgcACAABqb2RmbzAxLXB5dXBwZzEvcHl1cHBnMXRl
cHl1cHBnMS9taW5pZmllZC5weVVUBQADP33NV3V4CwABBPUBAAAEFAAAAFBLAQIeAxQAAAAIAIiB
c3QubG9nVVQFAAM/fc1XdXgLAAEE9QEAAAQUAAAAUEsFBgAAAAAEAAQAegEAAMMDAAAAAA==
------------------------- KOPIERA T.O.M. RADEN OVANFÖR -------------------------

Inlämning

När Pythonuppgifter, kapitel 8-10 är färdiga är det dags att lämna in.

Inlämningar för Pythonuppgifter behöver inte redovisas innan inlämning.

• Till varje inlämning av pythonuppgifter ska ni bifoga flera filer. En textfil med rättningskoden för varje kapitel. T.ex. för Pythonuppgifter 1-3 bifogar ni en fil med rättningskoden för kapitel 1, en för kapitel 2 och en för kapitel 3.
• OBS! Ni ska bara göra EN inlämning av rättningskoder per labb, alla rättningskoder tillhörande samma laboration ska alltså bifogas till samma inlämning.
• Hur du använder rättningsskripten står längst ner på varje sida med uppgifter.
• Inlämning av Pythonuppgifter:
  • Sendlab: Pythonuppgifter