42 lines
1.1 KiB
Python
42 lines
1.1 KiB
Python
"""Sophia hat unendlich viele Münzen der Werte 1, 2 und 5 (Yay!). Wie viele Möglichkeiten gibt es, einen bestimmten
|
|
Betrag n zu bilden? Sophia hat sich folgende rekursive Funktion überlegt:
|
|
def coins(n):
|
|
if n == 0:
|
|
return 1
|
|
if n < 0:
|
|
return 0
|
|
return coins(n-1) + coins(n-2) + coins(n-5)
|
|
Hm, ist die Lösung von Sophia richtig? Erklären Sie! Messen Sie die Laufzeit der Funktion mit unserem @timingDecorator für verschiedene n.
|
|
Auch hier hilft Memoization, um die Laufzeit zu verbessern. Warum? Überprüfen Sie das."""
|
|
|
|
from functools import cache
|
|
from laufzeitmessung import timing
|
|
|
|
def coins(n):
|
|
if n == 0:
|
|
return 1
|
|
if n < 0:
|
|
return 0
|
|
return coins(n - 1) + coins(n - 2) + coins(n - 5)
|
|
|
|
@cache
|
|
def coins_cached(n):
|
|
if n == 0:
|
|
return 1
|
|
if n < 0:
|
|
return 0
|
|
return (coins_cached(n-1) + coins_cached(n-2) + coins_cached(n-5))
|
|
|
|
@timing
|
|
def measure_normal(n):
|
|
return coins(n)
|
|
|
|
@timing
|
|
def measure_cached(n):
|
|
coins_cached.cache_clear()
|
|
return coins_cached(n)
|
|
|
|
print("Ohne Memoization: ")
|
|
print(measure_normal(20))
|
|
print("Mit Memoization: ")
|
|
print(measure_cached(20)) |