Linear time fibonacci - Using memoized recursion. What is Fib(60) and how much time does it take for its execution.
need to be done in python. tell what your code is doing and show it working please
The above problem can be solved in the following way-
Explanation of code-
Here we are using memoized recursion.
We use this memoization technique along with recursion so that we can avoid re-calculating the values of the same state again and again. That is why when we compute a fibonacci term, we store it in the memory itself(in the F[] array) and check if its already there in memory. If its there, no need to calculate it again.
In the code also, we see that we compute lets say F[5] by computing F[4] and F[3] and adding them up, but since we have already computed F[4] and F[3] previously, on checking if its -1 or not, we see that F[3] and F[4] has some other value than -1, it means it has already been computed, so we do not need to compute again and simply use that value stored in memory itself. In this way, we are reducing the time complexity by a significant margin as it re-calculations are avoided at every step.
PYTHON CODE-
#import time module
import time
#list initialized with -1's to store the fibonacci terms
F = [-1]*101 #global array declaration so that only 1 copy is
maintained for fibonacci sequence
#define the function fib()
#takes in a number as parameter
def fib(n):
#if 'n' is 0 or 1, return 'n'
if n<=1:
return n;
#and if F[n] is not -1, it means it is already computed, so return
F[n]
elif F[n] != -1:
return F[n]
#and for all other cases
else:
#make a recursive call to fib(n-1) and fib(n-2) and store it in
F[n]
F[n] = fib(n-1) + fib(n-2)
#finally return the list
return F[n]
'''this code times the function call to fib(60)
we start the timer and store it in start time and then call the
function fib(60)
and then end the timer. And then print the time by subtracting end
and start'''
start = time.time()
fib(60) #function call
end = time.time()
print("Time taken for execution in secs = %.16f" % (end-start))
#print the time taken
#print the 60th term of fibonacci series, we can use for loop to
print
#the entire fibonacci sequence till 60th term, but here only for
demonstration, I've printed 60th term
print('The 60th term of fibonacci sequence is : ',F[60])
IMAGE OF CODE-
OUTPUT-
If this answer helps, please give an up vote and feel free to comment for any query.
Linear time fibonacci - Using memoized recursion. What is Fib(60) and how much time does it...
Extra Credit - Fibonacci Function (Lec. 5 topic: Recursive function and runtime stack. Use recursion to calculate the Fibonacci Function 1.) Use a recursive function called fib() to calculate the Fibonacci Function for the following values for the variable n. int n = 10; int n = 20; int n = 30; int n = 40; int n = 45; int n = 46; 2.) In addition to calculating and displaying the results, use a "timer" to see how long...
1.Take this recursive Fibonacci implementation and convert it into the caching based version discussed in class. Implement your caching to store a maximum of 5 values. Create 2 variations: one that stores all values and one that only stores even values. Make sure that you don't leave any gaps in your cache — if you have 5 cache entries you must cache 5 unique and valid values. Compare the caching implementations to the recursive implementation using the time utility. How...
If the camera is 47m above the ground when it is dropped, how much time does it take for the camera to reach the ground? What is the velocity before it lands? Please show/explain ALL work. A hot-air balloon is descending at a rate of 1.6 m/s when a passenger drops a camera. Part A If the camera is 47 m above the ground when it is dropped, how much time does it take for the camera to reach the...
The is opened at a certain time. How much time does it take for the current to drop to 1/1000 of its initial value?
How much 96% ethanol do you need to mix with water to prepare 100ml of 60% ethanol? Please show working
A helicopter is rising at 5.0m/s when the pilot releases a bag. How much time does it take for the bag to reach the ground if the helicopter's altitude is 200m? (Hint: the bag keeps rising for a bit before it falls downwards, so don't forget to account for the time and distance it does so)? Please explain how you got your answer
Please help me in this question using MATLAB and Calculations please by hand Problem 2 Consider the causal non-linear discrete-time system characterized b difference equation: y the following n of amplitude P (i.e If we use as input x[n] to this system (algorithim) a step functio rge after several iterations to the square root of P t implements the above recursion to compute the square n)-P uIn), then yIn] will conver roots of 25, 9, 3, and 2. How many...
How much time does it take light to travel from the moon to the earth, a distance of 384000 km ? Correct answer= 1.28 secs Light from the star α Centaurus takes 4.30 years to reach the earth. What is the distance to α Centaurus in kilometers? please answer with 3 significant figures and km for units
Please help as much as you can it’s pretty much just terms What is the main purpose of the python-requests module? What kinds of requests can it make, and what types of responses might be returned? Text? HTML? JSON? Images? What is JSON? How does it compare to CSV? Whern processed using the json.loads) method, what Python data structure does the imported JSON get imported as. What is an HTML Document Object Model (DOM) and how does that relate to...
How do can I update this code (Code A): Code (A) #include using namespace std; int fibonacci(int n) { int a = 0, b = 1, c; if (n <= 1) return n; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; } int fibonacciRecursive(int n) { if (n <= 1) { return n; } return fibonacciRecursive(n-1) + fibonacciRecursive(n-2); } int main() { int n;...