Please use Python as the language to solve this set of problems. Thank you. Part
ID: 3745783 • Letter: P
Question
Please use Python as the language to solve this set of problems. Thank you.
Part 1 Implement two separate programs that generate the n-th Fibonacci number. The programs should both take n as command line input. The first algorithm one should implement the recursive algorithm (fib1 on Page 3 of the textbook), and the second one should implement the iterative algorithm (fib2 on Page 4). You should measure the time it takes for each of these versions (use for example, the timeit module in python) to calculate the n-th Fibonacci number for the following values of n: 1, 5, 10, 15, 20, 25, 30, 35, 40, 41, 42, 43. Finally, create a table of all your results and plot (using for example, the matplotlib library) the time taken to compute the Fibonacci numbers using fib1 and fib2, with n on the x-axis and time on the y-axis.Explanation / Answer
please give thumbs up, thanks
CODE:
import time
import matplotlib.pyplot as plt
def fib1(n):
if n<0:
print("Incorrect input")
# First Fibonacci number is 0
elif n==1:
return 0
# Second Fibonacci number is 1
elif n==2:
return 1
else:
return fib1(n-1)+fib1(n-2)
def fib2 (n):
if( n == 0):
return 0
else:
x = 0
y = 1
for i in range(1,n):
z = (x + y)
x = y
y = z
return y
def main():
data=[1,5,10,15,20,25,30];
A=list();
B=list();
for i in data:
print("1st")
start_time=time.clock();
number =fib1(int(i));
end_time=time.clock();
A.append(end_time-start_time);
start_time=time.clock();
number =fib2(int(i));
end_time=time.clock();
B.append(end_time-start_time);
print("2nd")
plt.plot(data,A,data,B)
plt.show()
main()