Number of Sums

Question

The function for finding the fibonacci series is given as follows : The number of additions taken in evaluating fib(5) is.

Your Answer:

4

Correct Answer: 7    Status: incorrect

Comments

Actually question is ambiguous. Both 7 & 4 are correct. As number of additions depend on how we solve Fibonacci sequence.

---

if you use recursion 7 will come, you can draw the recursion tree and check.

Answer 1

fib (5)  = fib(4) +  fib(3)

fib(4) = fib(3) + fib(2)

fib(3) = fib(2) + fib(1)   

fib(2) = fib(1) + fib(0)    

 

Now, for last simplication, 1 additions. Then we store fib(2) in fibonacci array.

For fib(3), 1 addition. Again we store fib(3).

 

And so on. This is perfect example of dynamic programming.

So, answer = 4