Friday, November 18, 2011

Jumping stairs

There is a stair with N step. You can jump either 1 step or 2 steps at time. How many different ways do you want to reach the top?

Solution

N = 1 --> 1
N = 2 ,,  1s+1s, 2s -> 2
N = 3 , 1s+1s+1s, 2s+1s, 1s+2s -> 3
N = 4, 1s+1s+1s+1s, 1s+1s+2s, 1s+2s+1s, 2s+1s+1s, 2s+2s -> 5
N = 5, 1s+1s+1s+1s+1s, 1s+1s+1s+2s, 1s+1s+2s+1s, 1s+2s+1s+1s, 2s+1s+1s+1s, 1s+2s+2s, 2s+1s+2s, 2s+2s+1s = 8

so and why?

2 comments:

  1. I got this one during the interview, and I must say the answer is rather surprising.

    Thanks for the good blog,
    Lukasz.

    ReplyDelete
  2. Fibonacci series...
    For explanation read http://tech-queries.blogspot.com/2011/07/fit-12-dominos-in-2n-strip.html

    ReplyDelete