diff options
| author | Paulo Custodio <pauloscustodio@gmail.com> | 2021-10-28 18:32:37 +0100 |
|---|---|---|
| committer | Paulo Custodio <pauloscustodio@gmail.com> | 2021-10-28 18:32:37 +0100 |
| commit | 502bf3e151d0f9041d8f7b0ae5125906206dfe3d (patch) | |
| tree | c310959ac111c1534714eec7df1de7e500c55b42 /challenge-136/abigail/python/ch-2.py | |
| parent | e9489210c115b86b27ecc5e73c5440bb09c59e9a (diff) | |
| parent | dc82718186854e495ed16900b1c485d170042a18 (diff) | |
| download | perlweeklychallenge-club-502bf3e151d0f9041d8f7b0ae5125906206dfe3d.tar.gz perlweeklychallenge-club-502bf3e151d0f9041d8f7b0ae5125906206dfe3d.tar.bz2 perlweeklychallenge-club-502bf3e151d0f9041d8f7b0ae5125906206dfe3d.zip | |
Merge branch 'master' into devel
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)) |