Stairs.
I came across this one sometime back. After spending sometime and solving it, imagine my suprise when I looked at the solution, it was something very very familiar. Actually if you are an CS student or do coding for a living, I'm dead sure that you would have atleast once *already* written code to exactly solve this problem. Lets see if you are able to recollect it when it comes wrapped in the form of a puzzle:
I look striaght ahead and see stairs going up. There are 'n' steps in it. I can either take one step at a time or 2 at a time. Ofcourse I can mix and match the two, i.e., I could first climb juse one step and then next climb 2 etc etc.. Question is how many different ways are there for me to climb the stairs. Can you also figure out what was the program that I'm reffering too (which I'm so sure of that you would have coded when you learnt a programming language such as C).
Ex: If n were 3. The answer is 3.
The number of ways for me to climb the stairs is 3 as below (+1 means climb one step, a +2 means climb two).
1. +1,+1,+1
2. +1, +2
3. +2 +1
I look striaght ahead and see stairs going up. There are 'n' steps in it. I can either take one step at a time or 2 at a time. Ofcourse I can mix and match the two, i.e., I could first climb juse one step and then next climb 2 etc etc.. Question is how many different ways are there for me to climb the stairs. Can you also figure out what was the program that I'm reffering too (which I'm so sure of that you would have coded when you learnt a programming language such as C).
Ex: If n were 3. The answer is 3.
The number of ways for me to climb the stairs is 3 as below (+1 means climb one step, a +2 means climb two).
1. +1,+1,+1
2. +1, +2
3. +2 +1

4 Comments:
Interesting one for sure. With the clues I thought it should be fibonocci series for sure.
I had to confirm it though by writing down the combinations. It came as
1 2 3 5 8 13.... for 'n' 1 2 3 4 5 6... respectively.
I should have started from 4,5,6 steps. I directly started with 6 then came to 5 and then to 4 (backtrack). In between made a mistake which gave 12 ways for 6 and 7 ways for 5 but 5 ways for 4. Hence series was'nt clear and had to rework ;)
Bingo!
You are right guhan. Actually its much clearer when you try to write it as a program. Blame it on my math illitracy, I tried writing a program for this and as I started thinking about writing it, I saw that the problem was recursive in nature, i.e., To reach the nth step, I could either get to the n-2th step and then climb 2 or get to the n-1th step and climb 1. So,
the number of ways = the number of way to reach n-1th + the number of ways to reach the n-2th step.
IOW,
numofways(n) = numofways(n-1) + numofways(n-2).
Now that looks very familiar.
Ever since I saw your mail, my inclination was to represent this in mathematical form. Somehow I thought this combinations problem can be represented using nCr. However, I still have not arrived at respresenting this using nCr.
You guys can suggest?
ok.. Here goes the nCr version.
For Even Numbers, it is:
nCn + (n-1)C(n-2) + (n-2)C(n-4) + ... + (n/2)C(0)
For odd numbers:
nCn + (n-1)C(n-2) + (n-2)C(n-4) + ... + ((n+1)/2)C(1)
Where nCr is n!/((n-r)!r!)
-Chandra Sekhar
Post a Comment
<< Home