Help to find an algorithm

A patient has n pills to take. Each day he can take either 1 pill or 2 pills until all pills are gone. What will be the total number of different ways of taking n pills?

My approach as follows:

Each day take only one pill - 1 way

Take 2 pill only a single day, other days take only 1 pill - (n-1)C1 ways

Take 2 pill only 2 days, other days take 1 pill - (n-2)C2 ways

Take 2 pill on (n/2) days - (n/2)C(n/2) ways.

Is my algorithm correct? If yes, how can I find its closed form? If not, what might be the correct way?

Hello,

This seems to be a really good modification of the Fibonacci Sequence with base cases:

F(1) = 1;

F(2) = 2;

F(N) = F(N-1) + F(N-2), N > 2;

Like this, there’s one way to take 1 pill, 2 ways to take two pills, 3 ways to take three pills (2 on first day and one on second day, the reverse, and one per day, until the third day) and so on…

Don’t you think so?

Best regards,

Bruno

3 Likes

Hello again,

So, as to write a short tutorial about this problem, we first read the statement again, putting key points in bold:

A patient has N pills to take. Each day he can take either 1 pill or 2 pills until all pills are gone. What will be the total number of different ways of taking N pills?

I have put in bold the statement “each day”, because actually, if you think on it carefully, the number of days that the patient takes is irrelevant as he/she only wants to have N total pills taken, with the restriction that he/she can only take either 1 pill or 2 pills per day.

So the patient can take two days OR one day to have 2 pills (either he has one pill per day during two days, or he has two pills on the first day).

Having this knowledge with us, we can actually rephrase the statement into a more well-known classical problem:

Given an integer N, how many different ways are there to obtain it if we can only use the numbers 1 and 2?

It turns out that the answer to this problem is precisely F(N), where F(N) is the N-th Fibonacci number.

N = 1 --> There is only one way;

N = 2 —> There are two ways: 1+1 or 2;

N = 3 —> There are 3 ways: 1+1+1, 1+2, 2+1;

If you look more closely at these three cases, you can see that F(3) = F(2) + F(1).

From here, the generalization is obvious :slight_smile:

Hope this helps!

Best regards,

Bruno

1 Like

Hi, thanks for your quick answer. It seems your algorithm is correct for all the test cases I tried. But I don’t understand how it could be equivalent to Fibonacci Sequence. I’m in a learning stage of algorithms and please bear my dumb questions. But can you kindly provide me some tutorial which will help me to understand this?

I mean I want to know the relation of the problem with Fibonacci number.

Hello!
Yes, if you are interested I can write you a tutorial for this problem :smiley:

if you can that’ll be really helpful.

I will do it as soon as I can, hopefully in less than 1 hour :smiley:

Also, I know this might sound hypocrite to ask for, but, if you find any answer given to your question helpful, you can and should upvote that answer :smiley:

It is a good indicator not only for us who provide help, but also for people who will read this in the future :slight_smile:

Thank you very much for detailed description. It was very much helpful. After some searching on relation of combinatorics with fibonacci I found the following relation

F(n) = Sum((n-k)C k) where 0<=k<=n/2

And this is the relation I derived in my initial solution of the algorithm.

@azizul_fahim here is a similar problem that reinforces the same logic… http://www.codechef.com/problems/CLMBSTRS

Thanks.

Given your algorithm expertise, can you take a look on the following link?

http://discuss.codechef.com/questions/25395/help-with-variation-of-scheduling-algorithm