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