Lets start with a simple but a tricky one :)

You have n number of chocolates. Your best friend asks for the chocolate but you say that he can take only 1 or maximum 2 chocolates at a time.

Find the number of ways in which your friend can take all the chocolates in any number of times.

The first thing to note is that how can you take n chocolates ?

Before having n chocolates you need to have either n-1 or n-2 chocolates (as you can only pick 1 or 2 chocolates).

So if f(n) denotes the number of ways to pick n chocolates then

f(n) = f(n-1) + f(n-2)

Wow it turns out to be a Fibonacci series !!!

Base cases you can work it out :)

Try the extension of this problem here

You have n number of chocolates. Your best friend asks for the chocolate but you say that he can take only 1 or maximum 2 chocolates at a time.

Find the number of ways in which your friend can take all the chocolates in any number of times.

**Approach :**The first thing to note is that how can you take n chocolates ?

Before having n chocolates you need to have either n-1 or n-2 chocolates (as you can only pick 1 or 2 chocolates).

So if f(n) denotes the number of ways to pick n chocolates then

f(n) = f(n-1) + f(n-2)

Wow it turns out to be a Fibonacci series !!!

Base cases you can work it out :)

Try the extension of this problem here

int no_of_ways(int total_coins)

ReplyDelete{

if(0==total_coins ||1==total_coins||2==total_coins) return total_coins;

return (no_of_ways(total_coins-1) + no_of_ways(total_coins-2) );

}

In simple terms.... it is a Fibonacci series :)

ReplyDeletesir,

ReplyDeleteek dum hit nahi howz it fibonacci

shashwat sinha

It can be understood if u look at the problem as a DP. Since u can give only 1 or 2 chocolates at a time so the number of ways can be computed based on the earlier computations. If

ReplyDeleteNumber of ways of giving n chocolates = f(n)

So f(n) = f(n-1) + f(n-2) which is a Fibonacci series.

Regards