Memoization is a technique used to speed up computations by storing and reusing previously computed results. When a function is called with certain inputs, memoization checks if the result for those inputs has already been calculated and stored. If so, it returns the cached result; otherwise, it calculates the result and stores it for future use, reducing redundant computations.
Problem Statement:
You are given a positive integer n. Implement a function to calculate the Fibonacci series up to the n-th term using memoization.
Function Signature:
def fibonacci(n):
pass
Input Format:
A single integer n (0 ≤ n ≤ 100)
Output Format:
Return a list containing the Fibonacci series up to the n-th term.
Constraints:
The input integer n represents the number of terms in the Fibonacci series to be calculated. The value of n will not exceed 100.
Sample Input:
7
Sample Output:
[0, 1, 1, 2, 3, 5, 8]
SOLUTION
def fibonacci(n, memo={}):
if n <= 1:
return n
elif n in memo:
return memo[n]
else:
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
def fibonacci_series(n):
return [fibonacci(i) for i in range(n)]
n = int(input())
result = fibonacci_series(n)
print(result)
- The core of the program lies in the recursive fibonacci function, which computes Fibonacci numbers efficiently by utilizing memoization to store and retrieve intermediate results.
- Memoization in the Fibonacci function transforms the recursive algorithm into a dynamic programming approach, making it more efficient by eliminating repetitive calculations.
- The memoization dictionary (memo) stores Fibonacci numbers as key-value pairs, where the key is the index n and the value is the corresponding Fibonacci number.
- The Fibonacci function handles base cases (where n is 0 or 1) explicitly, returning the value of n in those cases without further computation.
Comments
Post a Comment