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 70 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

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 summan av alla positiva heltal från och med n till och med m. Antag att n är mindre än m.

Exempel:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

>>> 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:

1
2
3
4

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

Uppgift 4.2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

>>> required_storage(1, 2)
2
>>> required_storage(10, 2)
16
>>> required_storage(100, 2)
128
>>> required_storage(1000, 2)
1024
>>> required_storage(10000, 2)
16384

4.2.2 (5p)

Det är lite onödigt att behöva skriva startvärdet 2 när det alltid är just 2. 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)
2
>>> 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)
2
>>> 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)
2
>>> 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.

1
2
3
4
5
6
7
8

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

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

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:

1
2
3
4

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

1
2
3
4
5
6
7
8

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

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:

1
2

>>> 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:

1
2
3
4
5
6

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

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:

1
2
3
4
5
6
7
8

>>> 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:

1
2
3
4
5
6
7
8

>>> 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:

1
2
3
4
5
6
7
8

>>> 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]