Pythonuppgifter 4 - Enkelrekursion

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 viktig del av att programmera!

Att lära dig från uppgifterna

• Förstå hur upprepning kan implementeras genom funktionsanrop.
• Förstå hur sekvenser kan bearbetas och genereras rekursivt.

Man kan få max 105 poäng och för att få godkänt krävs 60 poäng (90 för väl godkänt). Försök dock att lösa alla 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.

Uppgift 4.1

Följande uppgifter går ut på att ackumulera ett numeriskt värde.

4.1.1 (5p)

Skriv en funktion sum_rec(n) som returnerar summan av alla positiva heltal från 0 till och med n.

4.1.2 (5p)

Skriv en funktion fac_rec(n) som tar in ett tal och beräknar fakulteten av n. Fakulteten av $n$, skrivet $n!$, beräknas som $n!=n\times (n-1)\times (n-2) \times … \times 1$. Dvs. produkten av alla positiva heltal från och med $n$ till och med $1$

4.1.3 (5p)

Skriv en funktion product_n_to_m(n, m) som returnerar produkten av alla positiva heltal från och med n till och med m. Antag att n är mindre än m.

Exempel

>>> product_n_to_m(0, 10)
0 # Vilket tal som helst multiplicerat med 0 blir ju 0
>>> product_n_to_m(2, 5)
120
>>> product_n_to_m(1, 5)
120 # Vilket tal som helst multiplicerat med 1 blir ju sig självt
>>> product_n_to_m(3, 7)
2520
>>> product_n_to_m(5, 15)
54486432000

4.1.4 (5p)

Skriv funktionen multiply(factor1, factor2) som utför multiplikationen genom att addera factor1 till factor1, factor2 antal gånger med hjälp av rekursion. Den inbyggda multiplikationsoperatorn * får inte användas, bara + och -.

Exempel

>>> multiply(3, 7)
21
>>> multiply(7, 3)
21

Uppgift 4.2

Vi vill lagra filer i en molntjänst. De olika storlekar på lagringsutrymmen man kan köpa består av 2-potenser ($2^n$, dvs. $2^0=1$, $2^1=2$, $2^2=4$, $2^3=8$, $2^4=16$, $2^5=32$, …). Vi vill använda ett så litet lagringsutrymme som möjligt för att inte behöva betala för onödigt lagringsutrymme.

4.2.1 (5p)

Skriv en funktion required_storage(filesize, start) som tar en filstorlek, filesize, representerat som ett heltal och en initial storlek att testa, start. Utgå från att start alltid är en 2-potens eftersom de tillgängliga storlekarna är 2-potenser. Om den initiala storleken start inte räcker till så ska funktionen testa med nästa större 2-potens. Funktionen ska returnera den första storlek den hittar som är tillräcklig. Använd rekursion.

Exempel

>>> required_storage(1, 2) # 2 är redan tillräckligt
2
>>> required_storage(1, 32) # 32 är redan tillräckligt
32
>>> required_storage(1, 1) # 1 är redan tillräckligt
1
>>> required_storage(10, 1) # 1 är inte tillräckligt
16
>>> required_storage(100, 1)
128
>>> required_storage(1000, 1)
1024
>>> required_storage(10000, 1)
16384

4.2.2 (5p)

Det är lite onödigt att behöva skriva startvärdet 1 när det egentligen alltid ska vara just 1. Skriv en funktion required_storage2(filesize) som inte behöver ett startvärde. Funktionen ska anropa required_storage.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

>>> required_storage2(1)
1
>>> required_storage2(10)
16
>>> required_storage2(100)
128
>>> required_storage2(1000)
1024
>>> required_storage2(10000)
16384

4.2.3 (5p)

Det är lite onödigt att ha en funktion på toppnivå som alltid bara anropas av en annan funktion. Skriv en funktion required_storage3(filesize) som inte behöver ett startvärde. Funktionen ska ska ha en inre funktion (en funktion definierad inne i en annan funktion) som utför själva rekursionen.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

>>> required_storage3(1)
1
>>> required_storage3(10)
16
>>> required_storage3(100)
128
>>> required_storage3(1000)
1024
>>> required_storage3(10000)
16384

4.2.4 (5p)

I Python kan vi lösa problemet med det överflödiga startvärdet utan att definiera två funktioner. Istället kan vi använda en standardparameter (default parameter). Ta reda på hur det fungerar och använd det för att implementera required_storage4.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

>>> required_storage4(1)
1
>>> required_storage4(10)
16
>>> required_storage4(100)
128
>>> required_storage4(1000)
1024
>>> required_storage4(10000)
16384

Uppgift 4.3 (10p)

Skriv en funktion roll_n_dice(dice, sides) som simulerar summan av dice stycken tärningsslag med en tärning med sides sidor.

Tips: Återanvänd lösningen från roll_dice från första uppsättningen pythonuppgifter för att simulera ett enskilt tärningsslag.

Exempel

Obs!: Tänk på att tärningsslagen är slumpmässiga och att dina resultat kan se helt annorlunda ut.

>>> roll_n_dice(1, 6)
2
>>> roll_n_dice(1, 6)
5
>>> roll_n_dice(3, 6)
5
>>> roll_n_dice(3, 6)
15

Uppgift 4.4

Innan nästa uppgift ska vi definiera två hjälp-funktioner, first och rest. Funktionen first ska returnera det första elementet i en sekvens och funktionen rest ska returnera “resten”, dvs. hela sekvensen utom det första elementet.

Tips: Gå tillbaka till pythonuppgifterna om sekvenser och fräscha upp hur indexering och utsnitt fungerar.

Exempel

>>> first([1, 2, 3, 4])
1
>>> rest([1, 2, 3, 4])
[2, 3, 4]
>>> first(rest("abcde"))
'b' # första elementet i resten av listan
>>> first(rest(rest("abcde")))
'c' # första elementet i resten av resten av listan

4.4.1 (5p)

Funktionen first ska returnera det första elementet i en sekvens.

4.4.2 (5p)

Funktionen rest ska returnera “resten” av en sekvens, dvs. hela sekvensen utom det första elementet.

Uppgift 4.5

Följande uppgifter går ut på att bearbeta sekvenser med hjälp av rekursion. Använd funktionerna first och rest för att hämta ut olika delar av sekvensen.

4.5.1 (5p)

Skriv en funktion sum_list_rec(lst) som tar en lista av värden och returnerar resultatet av att “slå ihop” värdena. Antag att lst alltid har minst 1 element. Funktionen ska fungera både om lst består enbart av tal och om lst består enbart av strängar.

Tips: Basfallet bör inte vara att lst är tom.

Exempel

>>> sum_list_rec([6, 2, 9])
17
>>> sum_list_rec(['hej', 'på', 'dig'])
hejpådig

4.5.2 (5p)

Skriv funktionen value_in(val, seq) som tar ett värde val och en sekvens seq och returnerar True om val är ett element i seq. Den inbyggda operatorn in får inte användas utan uppgiften skall lösas genom att stega igenom seq med hjälp av rekursion.

Tips: Uppgiften kan lösas med en if-sats med 3 klausuler där det rekursiva anropet görs i else-klausulen.

Exempel

>>> value_in(3, [1, 'a', 3, 2.1])
True
>>> value_in(3, [1, 'a', '3', 2.1])
False
>>> value_in('d', 'abcde')
True
>>> value_in('f', 'abcde')
False

4.5.3 (5p)

Skriv en funktion add_strings(lst) som tar en lista av tal och strängar. Funktionen ska returnera resultatet av att konkatenera alla strängar i lst, övriga element ska ignoreras.

Uppgift 4.6

Följande uppgifter går ut på att inte bara bearbeta utan också ackumulera en sekvens. Använd funktionerna first och rest där det passar.

4.6.1 (5p)

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

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

4.6.2 (5p)

Skriv en funktion filter_type(lst, type_) som tar en lista lst och en typ type_ (t.ex. str, int eller float). Notera att den andra parametern ska heta type_ med understreck i slutet så att namnet inte krockar med funktionen type, som kommer behöva användas i filter_type.

Exempel

>>> filter_type([1, 'eggs', 2.0, 3.7, 4, 'spam'], float)
[2.0, 3.7]
>>> filter_type([1, 'eggs', 2.0, 3.7, 4, 'spam'], int)
[1, 4]
>>> filter_type([1, 'eggs', 2.0, 3.7, 4, 'spam'], str)
['eggs', 'spam']

4.6.3 (5p)

Skriv en funktion reverse_rec(lst) som tar en lista som inargument och returnerar en ny lista i omvänd ordning.

Exempel

1
2

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

Uppgift 4.7

Python har en funktion range som används för att generera talserier.I de här uppgifterna ska vi implementera en egen version av range med hjälp av rekursion. Du kan alltid testa att din lösning ger samma resultat som den riktiga range-funktionen genom att jämföra ditt resultat med resultatet av att köra list(range(*samma argument som till din funktion*)).

4.7.1 (5p)

Skriv en funktion range_list_stop(stop) som tar ett heltal stop och returnerar en lista med alla heltal från 0 till men inte med stop.

Exempel

>>> range_list_stop(0)
[]
>>> range_list_stop(1)
[0]
>>> range_list_stop(2)
[0, 1]
>>> range_list_stop(5)
[0, 1, 2, 3, 4]

4.7.2 (5p)

Skriv en funktion range_list_start(start, stop) som tar två heltal start och stop och returnerar en lista med alla heltal från start till men inte med stop. Antag att start är mindre än stop.

Exempel

>>> range_list_start(0, 0)
[]
>>> range_list_start(0, 5)
[0, 1, 2, 3, 4]
>>> range_list_start(3, 6)
[3, 4, 5]
>>> range_list_start(-2, 2)
[-2, -1, 0, 1]

4.7.3 (5p)

Skriv en funktion range_list_step(start, stop, step) som tar tre heltal start, stop och step, där step kan vara positivt eller negativt. Funktionen ska returnera en lista med alla heltal från start till men inte med stop i inkrement om step. Antag att start och stop kommer i rätt ordning i förhållande till om step är positivt eller negativt.

Exempel

>>> range_list_step(0, 0, 1)
[]
>>> range_list_step(-2, 2, 1)
[-2, -1, 0, 1]
>>> range_list_step(6, 1, -1)
[6, 5, 4, 3, 2]
>>> range_list_step(10, -10, -3)
[10, 7, 4, 1, -2, -5, -8]