Programming Question

Run each of the following codes in your favorite program. ADD lines to report the
execution time. Which algorithm is fastest?
Iterative Approach
1 def fib_iter(n):
2
a=1
3
b=1
4
if n==1:
5
print(‘0’)
6
elif n==2:
7
print(‘0′,’1′)
8
else:
9
print(“Iterative Approach: “, end=’ ‘)
10
print(‘0′,a,b,end=’ ‘)
11
for i in range(n-3):
12
total = a + b
13
b=a
14
a= total
15
print(total,end=’ ‘)
16
print()
17
return b
18
19 fib_iter(5)
Output : Iterative Approach : 0 1 1 2 3
Recursive Approach
1 def fib_rec(n):
2
if n == 1:
3
return [0]
4
elif n == 2:
5
return [0,1]
6
else:
7
x = fib_rec(n-1)
8
# the new element the sum of the last two elements
9
x.append(sum(x[:-3:-1]))
10
return x
11 x=fib_rec(5)
12 print(x)
Output – 0, 1, 1, 2, 3
Dynamic Programming Approach
1 There is a slight modification to the iterative approach. We use an additional array.
2
3 def fib_dp(num):
4
arr = [0,1]
5
print(“Dynamic Programming Approach: “,end= ‘ ‘)
6
if num==1:
7
print(‘0’)
8
elif num==2:
9
print(‘[0,’,’1]’)
10
else:
11
while(len(arr)