30 lines
848 B
Python
30 lines
848 B
Python
#!/usr/bin/env python3
|
|
"""Memoized Fibonacci calculator - returns the n-th fibonacci number."""
|
|
|
|
from functools import lru_cache
|
|
|
|
@lru_cache(maxsize=None)
|
|
def fib(n: int) -> int:
|
|
"""Return the n-th fibonacci number (0-indexed: fib(0)=0, fib(1)=1)."""
|
|
if n < 0:
|
|
raise ValueError("n must be non-negative")
|
|
if n <= 1:
|
|
return n
|
|
return fib(n - 1) + fib(n - 2)
|
|
|
|
def main():
|
|
results = [(n, fib(n)) for n in range(15)]
|
|
print("n | fib(n)")
|
|
print("--+------")
|
|
for n, val in results:
|
|
print(f"{n} | {val}")
|
|
|
|
# Verify known values
|
|
assert fib(0) == 0, "fib(0) should be 0"
|
|
assert fib(1) == 1, "fib(1) should be 1"
|
|
assert fib(10) == 55, "fib(10) should be 55"
|
|
assert fib(14) == 377, "fib(14) should be 377"
|
|
print("\nAll assertions passed!")
|
|
|
|
if __name__ == "__main__":
|
|
main() |