Pythonuppgifter 3
Innehåll
För att underlätta för dig när du gör pythonuppgifterna finns det ett rättningsskript (instruktioner står efter uppgifterna) som du kan köra till varje uppgift. Rättningsskriptet testar koden du skrivit och berättar för dig vilka uppgifter du gjort fel på och räknar ut din poäng. Du får också reda på vilka uppgifter som saknas.
Skriv lösningarna till uppgifterna i en och samma fil och testa koden själv innan du använder rättningsskriptet. Att kunna testa sin kod är en nödvändig del av att programmera!
3.1 Dictionaries
Att lära dig från uppgifterna
- lägga till nyckel-värde-par till ett dictionary
- slå upp värde i ett dictionary med hjälp av nyckel
- ändra värde för en nyckel i ett dictionary
Godkänt
För att få godkänt krävs 100 poäng. Försök dock att lösa alla uppgifter då inte alla fel upptäcks av rättningsskriptet men om ni har lite marginal kan ni kanske bli godkända även om assistenten som rättar hittar något sådant fel.
Uppgifter
Uppgift 3.1.1 (10p)
Skriv funktionen key_exists(key, d)
som tar in ett dictionary och returnerar
True
om nyckeln key
finns bland dictionaryts nycklar. Annars returneras
False
.
Tips: Använd operatorn in
.
Uppgift 3.1.2 (10p)
Skriv funktionen value_exists1(value, d)
som tar in ett dictionary och
returnerar True
om värdet value
finns bland dictionaryts värden.
Returnera False
om det inte finns.
Anta att dictionaryt bara innehåller siffror eller strängar.
Tips: Använd operatorn in
eller en . (Om ni redan löst uppgiften med for
-loopfor
är det ok i år, givet att ni loopar över rätt sak.)
Uppgift 3.1.3 (10p)
Skriv funktionen add_to_dict(key, value, d)
som lägger till värdet value
till dictionaryt d
. Du behöver inte bry dig om värdet eller nyckeln redan
finns. Funktionen behöver inte returnera dictionaryt.
Uppgift 3.1.4 (10p)
Skriv funktionen add_new_only_to_dict(key, value, d)
som lägger till värdet
value
till dictionaryt d
fast bara om nyckeln key
inte finns i
dictionaryt. Funktionen behöver inte returnera dictionaryt.
Uppgift 3.1.5 (20p)
Skriv funktionen increment_dictionary_value1(key, d)
som tar in ett dictionary
vars värden är heltal eller flyttal (du behöver inte kontrollera detta). Nyckeln
key
kommer att finnas i dictionaryt. Funktionen ska lägga till 1 till värdet
som tillhör nyckeln key
. Funktionen behöver inte returnera dictionaryt.
Uppgift 3.1.6 (20p)
Skriv funktionen increment_dictionary_value2(key, d)
som tar in ett dictionary
vars värden är heltal eller flyttal (du behöver inte kontrollera detta). Om
nyckeln key
finns i dictionaryt ska du öka dess värde med 1. Om nyckeln inte
finns i dictionaryt ska nyckeln läggas till och dess värde sättas till 1.
Funktionen behöver inte returnera dictionaryt.
Uppgift 3.1.7 (20p)
Skriv funktionen add_to_value_list1(key, value, d)
som tar in ett nyckel, ett
värde och ett dictionary. Värdena i dictionaryt kommer att vara listor (du
behöver inte kontrollera detta) och den angivna nyckeln kommer att finnas.
Värdet ska läggas till till listan som tillhör nyckeln key
i dictionaryt.
Funktionen behöver inte returnera dictionaryt.
Uppgift 3.1.8 (10p)
Skriv funktionen return_value_list1(prefix, d)
som tar in en sträng och ett
dictionary. Funktionen ska returnera en lista som innehåller alla värden som
tillhör nycklar som börjar på strängen prefix
. Alla nycklar kommer att vara
strängar i dictionaryt.
Uppgift 3.1.9 (20p)
Skriv funktionen value_exists2(value, d)
som tar in ett dictionary och
returnerar True
om värdet value
finns bland dictionaryts värden.
Returnera False
om det inte finns.
Dictionaryts värden ska kunna vara siffror, strängar eller icke-nästlade listor.
Funktionen ska även leta efter värdet value
i eventuella listor. Om vi letar
efter värdet 'hejsan'
i dictionaryt
|
|
så ska funktionen returnera True
3.2 Nästlade strukturer
Att lära dig från uppgifterna
- Bearbetning av nästlade-strukturer
Godkänt
För att få godkänt krävs 100 poäng. Försök dock att lösa alla uppgifter då inte alla fel upptäcks av rättningsskriptet men om ni har lite marginal kan ni kanske bli godkända även om assistenten som rättar hittar något sådant fel.
Uppgifter
Uppgift 3.2.1 (10p)
Skriv funktionen sum_of_ints2(value_list)
som tar in en lista med listor av
värden som argument. Funktionen ska returnera summan av alla heltal som finns i
de nästlade listorna.
Exempel: sum_of_ints2([["a", 1], [2, 3.0, "hej"]])
ska returnera 3
.
Uppgift 3.2.2 (10p)
Skriv funktionen flatten_list1(list_of_lists)
som får in en nästlad lista. De
inre listorna innehåller inga listor. Funktionen ska returnera en icke-nästlad
lista som innehåller alla värden i de inre listorna.
Om list_of_values
är [[1, 2], [3], [1, 2, 3]]
så ska funktionen returnera
listan [1, 2, 3, 1, 2, 3]
.
Uppgift 3.2.3 (20p)
Skriv funktionen flatten_list2(list_of_lists)
som får in en lista som både
innehåller listor och vanliga värden. De inre listorna innehåller dock inga
listor. Funktionen ska returnera en icke-nästlad lista som innehåller alla
värden i de inre listorna, samt värdena som ligger direkt i listan.
Om list_of_values
är [[1, 2], [3], 4, [1, 2, 3], 4, 5]
så ska funktionen
returnera listan [1, 2, 3, 4, 1, 2, 3, 4, 5]
.
Uppgift 3.2.4 (10p)
Skriv funktionen get_first_column(matrix)
som tar in en nästlad lista som
representerar en matris. Varje element i matrix
är alltså en lista som
representerar en rad i matrisen. Alla listor är lika långa. Se exemplet nedan.
|
|
Funktionen get_first_column(matrix)
ska returna en lista som innehåller
värdena i den första kolumnen i matrisen som en lista. För m1
ska alltså
listan [1, 3, 0]
returneras. För m2
ska [1, 3, 0]
returnaeras. För m3
ska [1, 3, 0, 4]
returneras.
Tips: För att komma åt det första elementet i den första
listan i m
definierad ovan, skriver man m[0][0]
. För att komma åt det tredje
elementet i den andra listan skriver man m[1][2]
.
Uppgift 3.2.5 (20p)
Skriv funktionen get_nth_column(n, matrix)
som tar in en nästlad lista som
representerar en matris. Varje element i matrix
är alltså en lista som
representerar en rad i matrisen. Alla listor är lika långa.
Funktionen get_nth_column(n, matrix)
ska returnera kolumnen n
, där den
första kolumnen har n == 1
.
Uppgift 3.2.6 (20p)
Skriv funktionen get_all_columns(matrix)
som tar in en nästlad lista som
representerar en matris. Varje element i matrix
är alltså en lista som
representerar en rad i matrisen. Alla listor är lika långa.
Funktionen get_all_columns(matrix)
ska returnera alla kolumner i matrisen
matrix
som en lista. Följande lista ska alltså returneras givet m1
som
definierad i uppgift 3.2.4:
|
|
Uppgift 3.2.7 (20p)
Skriv funktionen scalar_product(vec1, vec2)
som tar in två vektorer bestående
av listor och returnerar skalärprodukten för listorna. Båda listorna är lika
långa.
Skalärprodukten räknas ut enligt nedan:
(1,2,4)⋅(1,3,0)=1×1+2×3+4×0=7
Exempel:
|
|
Uppgift 3.2.8 (25p)
Skriv funktionen matrix_square(matrix)
som ska returnera kvadraten av matrisen
matrix
. Varje element aij i den nya matrisen fås av skalärprodukten av
rad i med kolumn j.
Om vi använder oss av samma matris om i exemplet i uppgift 3.2.4
|
|
så är elementet på den första raden i den första kolumnen i den nya matrisen
skalärprodukten av den första raden i m
och den första kolumnen i m
.
Elementet på första raden, andra kolumnen är (1,2,4)⋅(2,0,5)=22
och så vidare. Den nya matrisen som matrix_square(matrix)
ska returnera givet
m
som input är alltså
|
|
Du får använda funktionerna du skrivit i tidigare uppgifter.
3.3 Rekursion
Att lära dig från uppgifterna
- Hur man skriver rekursiva funktioner.
OBS! Alla uppgifter ska lösas rekursivt! Du får alltså inte använda
for
- eller while
-loopar.
Godkänt
För att få godkänt krävs 100 poäng. Försök dock att lösa alla uppgifter då inte alla fel upptäcks av rättningsskriptet men om ni har lite marginal kan ni kanske bli godkända även om assistenten som rättar hittar något sådant fel.
Uppgift 3.3.1 (10p)
Skriv en funktion fac_rec(n)
som tar in ett tal och beräknar
n!=n×(n−1)×(n−2)×…×1.
Uppgift 3.3.2 (10p)
Skriv en funktion fib(n)
som returnerar fibonaccitalet för position n
.
Om du är obekant med fibonaccital kan du läsa mer om det på
wikipedia.
Uppgift 3.3.3 (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 mer 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 0 efterfrågas. Värdet är på vänsterkanten när kolumnen är 0 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)
Uppgift 3.3.4 (10p)
Skriv en funktion keep_if_even(lst)
vars argument lst
är en lista med
heltal. Funktionen returnerar en ny lista med de heltal i lst
som är jämna.
Exempel:
|
|
Uppgift 3.3.5 (10p)
Skriv en funktion reverse_rec(lst)
som tar en lista som inargument och
returnerar en ny lista i omvänd ordning. Du ska inte undersöka
listor-i-listor.
Exempel:
|
|
Exempel:
|
|
Uppgift 3.3.6 (15p)
Skriv en funktion keep_if_even_all(lst)
som gör som keep_if_even
i uppgift
3.3.4, men den undersöker också listor-i-listor. Om en lista bara innehåller
udda tal ska den tomma listan sparas.
Exempel:
|
|
Exempel:
|
|
Uppgift 3.3.7 (15p)
Skriv en funktion reverse_rec_all(lst)
som gör som reverse_rec
men den
undersöker också listor-i-listor.
Exempel:
|
|
Exempel:
|
|
Uppgift 3.3.8 (15p)
Skriv en funktion is_in_list(lst, element)
som returnerar True
om element
finns i lst
, annars returnerar funktionen False
. Funktionen ska undersöka
listor-i-listor.
Exempel:
|
|
Exempel:
|
|
Uppgift 3.3.9 (15p)
Skriv en funktion count_all(lst)
som returnerar antalet element som finns i
lst
. Funktionen ska undersöka listor-i-listor.
Exempel:
|
|
Exempel:
|
|
Uppgift 3.3.10 (20p)
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 undersöka listor-i-listor.
Exempel:
|
|
Exempel:
|
|
Uppgift 3.3.11 (15p)
Skriv funktionen multiply(factor1, factor2)
som utför multiplikationen genom att addera factor1
till factor1
, factor2
antal gånger med hjälp av rekursion.
Exempel:
|
|
Uppgift 3.3.E1
Extra uppgift (ingår ej bland rättade uppgifter). Bra övning inför Del 2 på tentan.
Skriv en funktion linear_serch(key, seq)
som söker efter key
(ett tecken
eller ett listelement) i sekvensen seq
(en sträng eller rak lista) och
returnerar positionen. Om key
ej finns i sekvensen så ska -1 returneras.
Exempel:
|
|
Tips 1
När man gör en rekursiv lösning och vill använda ett index behöver man införa
det som ett argument. linear_search
kan därför definieras som:
|
|
linear_search_hlp(key, seq, index)
är en ‘hjälpfunktionen’ till
linear_search(key, seq)
som innehåller den faktiska koden.
Tips 2
Ett alternativ är att använda argument med default-värde (gås
igenom på Föreläsning 4.1): linear_search(key, seq, index=0)
Uppgift 3.3.E2
Extra uppgift (ingår ej bland rättade uppgifter). Bra övning inför Del 2 på tentan.
Linjär sökning är ett ineffektivt sätt att söka. Ett betydligt snabbare sätt är att gör binär sökning. Binärsökning söker igenom en sorterad lista. Binärsökning börjar med att jämföra elementet i mitten av listan med det sökta värdet. Om det sökta värdet är lika med elementet i mitten av listan, returneras dess position i listan. Om det sökta värdet är mindre eller större än elementet i mitten av listan, så fortsätter sökningen i den lägre respektive högre halvan av listan, rekursivt
Skriv en funktion binary_search(key, sorted_lst)
som söker efter key
i den
sorterade listan sorted_lst
och returnerar positionen för key. Om key
ej
finns i sekvensen så ska -1 returneras.
Exempel:
|
|
Tips: Använd två extra argument för low
resp high
för att
representera index för start och slut på det listsegment du undersöker. Initialt
är low = 0 och high = len(seq)-1
Uppgift 3.3.E3
Extra uppgift (ingår ej bland rättade uppgifter). Bra övning inför Del 2 på tentan.
Skriv rekursiva versioner av funktionerna insert_at_asc_place(values, new_value)
och sort_asc(values)
från uppgift 2.3.10-11. Namnge dem
insert(lst, new_value)
resp insertion_sort(lst)
Exempel:
|
|
Uppgift 3.3.E4
Extra uppgift (ingår ej bland rättade uppgifter). Bra övning inför Del 2 på tentan.
Ett effektivare sätt att sortera listor på är med mergesort som är av typen “söndra och härska”. Om en lista har längden 1 är den sorterad och kan returneras, annars delas listan i två delar som sorteras och sedan sätts ihop.
Skriv de rekursiva funktionerna merge_sort(lst)
och merge(sorted_lst1, sorted_lst2)
där merge()
tar två sorterade listor och sätter samman dem
till en sorterad lista.
Exempel:
|
|
Rättningsskriptet
OBS! Rättningsskriptet kan bara användas från LiUs Linux-miljö, dvs när du antingen är inloggad via ThinLinc, har anslutit via VSCodes RemoteSSH, inloggad på en dator i en Linux-sal via RDP, eller inloggad på en faktisk Linux-dator i en Linux-sal på Campus.
Du kan bara köra rättningsskriptet för en specifik uppgift (t.ex. Pythonuppgifter 1.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.
För att rätta din fil skriver du nedanstående ($
skrivs inte utan
representerar prompten i terminalen):
|
|
- Ersätt
<uppgift>
med den uppgift koden löser, t.ex.1_1
för att rätta Pythonuppgifter 1.1,1_2
för Pythonuppgifter 1.2,2_3
för Pythonuppgifter 2.3, 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 (dvs utöver punkten innan ändelsen
py
.pyuppg1.1.py
fungerar alltså inte.
Exempel
Exempel för Pythonuppgifter 1.1 om filen med dina lösningar är döpt till pythonuppg1_1.py
|
|
Exempel för Pythonuppgifter 2.3 om filen med dina lösningar är döpt till pyuppg23.py
|
|
Inlämning
Alla tre delar lämnas in samtidigt och med Pythonuppgift_2 som “Current lab” i Sendlab.
Inlämningar för Pythonuppgifter 1-3 behöver inte redovisas innan inlämning.
- Bifoga en textfil med rättningskoden för varje deluppgift. T.ex. för Pythonuppgifter 1 laddar ni upp 3 textfiler, en med rättningskoden för 1.1, en för 1.2 och en för 1.3.
- Hur du använder rättningsskripten står längst ner på varje sida med uppgifter.
- Inlämning av Pythonuppgifter:
Pythonuppgifter 3 består av följande tre delar:
Alla tre delar lämnas in samtidigt och med Pythonuppgift_3 som “Current lab” i Sendlab.
Inlämningar för Pythonuppgifter 1-3 behöver inte redovisas innan inlämning.
- Bifoga en textfil med rättningskoden för varje deluppgift. T.ex. för Pythonuppgifter 1 laddar ni upp 3 textfiler, en med rättningskoden för 1.1, en för 1.2 och en för 1.3.
- Hur du använder rättningsskripten står längst ner på varje sida med uppgifter.
- Inlämning av Pythonuppgifter:
Sidansvarig: Johan Falkenjack
Senast uppdaterad: 2024-02-01