Questions d'entretiens - Ingénieur logiciel

F(n) = F(n-1) + F(n-2). Where F(n) - the ways to go on top to the last n stairs. function fibb(int n) { int x0 = 0, x1 = 1, x2; for(int i = 2; i <= n; i++) { x2 = x0 + x1; x0 = x1; x1 = x2; } return x1; }

When Google insisted on a formula, you should immediately have know this was not a Fibonacci series! You can solve it with recursion, but solving it recursively for n=4 should lead you to the formula. As an example of the recursive way, suppose n=40. How many different ways are there, following the rules of the question to get there? There are exactly 2 ways to get to the 40th step, either take a single step from 39 to 40 or a single step from 38 to 40. Our total so far is 2. Lets repeat for n=39, now our total is 4. This continues to work until you get to n=1, the special case, since you can only get to it by a single small step from the ground. You probably notice that the formula is f(n) = 2n -1.

The Fibonacci is the right answer ... almost It is true, that F(n) = F(n-1) + F(n-2), but Fibonacci sequence is also defined by the rule F(1) = F(2) = 1. In our case, for n = 1 step we have just one way { 1 }, so F(1) = 1. However, for n = 2 steps, we have two ways { 11, 2 }, so F(2) = 2. Therefore, the answer is F(1) = 1, F(2) = 2, F(n) = F(n-1) + F(n-2). It does not hurt to check this formula for small n: f(1) = 1 : { 1 } f(2) = 2 : { 11, 2 } f(3) = 3 : { 111, 12, 21 } f(4) = 5 : { 1111, 112, 121, 211, 22 } f(5) = 8 : { 11111, 1112, 1121, 1211, 2111, 122, 212, 221 } Obviously, the recursive formula works, while Answer Man's formula f(n) = 2n -1 does not.

I agree with v that it's almost Fibonacci. This question has come up three times in the last two months here on Glassdoor. My answer has been that for n stairs there are Fib(n+1) ways to climb them. This fixes the "off by one" problem and establishes that there is one way to climb zero steps (which seems as good an answer as any).

My previous answer has an error in the case N=5, when it says "That is a total of 1+4+1 = 6", instead it should be "That is a total of 1+4+3 = 8"

J'ai passé un entretien ou l'employeur très gentil me disait ce qu'il attendait de moi etc

Yo

Answer : only one way , from bottom to top