GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
128 views

asked in Algorithms by Loyal (3.9k points)   | 128 views

1 Answer

+3 votes
Best answer
okay,it can be solved using Dynamic Programming

and once one is computed, it can be easily found by going through the table.

and we can write it like

T(12)=T(10)+T(9)

T(10)=T(8)+T(7)

T(9)=T(7)+T(6)

T(8)=T(6)+T(5)

T(7)=T(5)+T(4)

T(6)=T(4)+T(3)

T(5)=T(3)+T(2)

T(4)=T(2)+T(1)

T(3)=T(1)+T(0)

T(2)=T(0)+T(-1)

We need one function call for each unique T(x)

here we need function calls T(-1),T(0),T(1),T(2,)T(3),T(4),T(5),T(6),T(7),T(8),T(9),T(10),T(12)

13 function calls

so it should be the answer
answered by Veteran (18.4k points)  
selected by
Are..it was this easy..I was complicating it unnecessarily. Thanks :)
Happens!
Btw,whats the answer?

yes..ur answer is correct. But the explaination was this.

ya, they did the same! i did table manner, they did tree approach! do not worry. Same thing.Even they missed something in last level
ok..actually they did not count all function calls, and counted T(5) twice, so I assumed it to be wrong.
^ they r consistent :P


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arunav Khare

    1464 Points

  10. Arjun

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,062 answers
63,294 comments
24,160 users