GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
183 views

asked in Algorithms by Loyal (4k points)  
retagged by | 183 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.5k 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 Sep 2017
  1. Habibkhan

    6334 Points

  2. Warrior

    2202 Points

  3. Arjun

    2150 Points

  4. nikunj

    1980 Points

  5. manu00x

    1726 Points

  6. SiddharthMahapatra

    1718 Points

  7. Bikram

    1706 Points

  8. makhdoom ghaya

    1650 Points

  9. A_i_$_h

    1518 Points

  10. rishu_darkshadow

    1512 Points


25,979 questions
33,554 answers
79,348 comments
31,011 users