diff options
Diffstat (limited to 'challenge-136/abigail/python/ch-2.py')
| -rw-r--r-- | challenge-136/abigail/python/ch-2.py | 20 |
1 files changed, 14 insertions, 6 deletions
diff --git a/challenge-136/abigail/python/ch-2.py b/challenge-136/abigail/python/ch-2.py index 88960021ef..d114bfdfba 100644 --- a/challenge-136/abigail/python/ch-2.py +++ b/challenge-136/abigail/python/ch-2.py @@ -8,13 +8,21 @@ # Run as: python ch-2.py < input-file # +cache = {} + def _count (target, this_fib, prev_fib): - if target < this_fib: - return (0) - if target == this_fib: - return (1) - return (_count (target - this_fib, this_fib + prev_fib, this_fib) + - _count (target, this_fib + prev_fib, this_fib)) + key = str (target) + ";" + str (this_fib) + if not (key in cache): + if target < this_fib: + cache [key] = 0 + elif target == this_fib: + cache [key] = 1 + else: + cache [key] = \ + _count (target - this_fib, this_fib + prev_fib, this_fib) + \ + _count (target, this_fib + prev_fib, this_fib) + + return cache [key] def count (target): return (_count (target, 1, 1)) |