Once a plank, two plank - there will be a ladder ...

It is about the ladders would like to talk a little. There is such a relatively common task with programmer interviews:



You go up the stairs. At each step, you can climb either 1 step or 2. In total, the staircase has n steps. How many different ways can you reach the end of the stairs?



The task is not very difficult, but it has a couple of interesting points about the minimum possible complexity of the solution and demonstrates "things that are interesting to know."

')

Obviously, one way or another, the decision begins with the observation that at each step we have a choice of two actions: take one step or take two steps. In the first case, the ladder is reduced by one step, in the second - by two. The total number of possible ways to get around the ladder is equal to the sum of the number of ways to do this if we start with one step, and the number of ways if we start with two. As a result, the solution is reduced to a recurrent formula:



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



A recursive or iterative implementation of this algorithm "in the forehead" looks a little longer than the relation itself (we leave the problem of overflow behind the brackets):

int f(int n) { if (n == 0 || n == 1) return 1; return f(n-1) + f(n-2); } 

In itself, this solution is correct, but its efficiency is low: the algorithm is exponential . The complexity can be reduced by using the standard technique of dynamic programming - memoization . Intuitive explanation: with each concrete step on the stairs the number of ways to reach the end does not depend on how we got to this step, so it makes sense to remember the answer and use it in the next steps of the calculation. I will not give the code - the main thing is that together with the iteration a linear solution is obtained. However, this is not all.



An attentive reader will notice that the ratio above is simply a formula of Fibonacci numbers with an amendment n per unit (the correction arises because the initial conditions are different - Fib (0) = 0, Fib (1) = 1, Fib (2) = 1 , and in our case, the ladders F (0) = 1, F (1) = 1, F (2) = 2). It is known that for Fibonacci numbers the following relationship holds:







Thus, after this exponentiation, the resulting matrix will contain the “n + 1” -th Fibonacci number in the first column of the first row of interest to us (matrix elements are traditionally indexed from one).



By itself, this fact is already interesting, but it is especially interesting in combination with the algorithm of fast exponentiation . Applied to our problem, this means that we can get an answer in O (ln N) multiplications. The code of this Python solution (again, to forget about the overflow problem - Python automatically switches to using big integer when it is needed) looks like this:

 #!/usr/bin/env python # You are climbing a stair case. Each time you can either make 1 step or 2 # steps. The staircase has n steps. In how many distinct ways can you climb the # staircase? def mul(a, b): return ((a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]), (a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1])) def pow(a, N): """Fast matrix exponentiation""" assert N >= 1 if N == 1: return a x = pow(a, N / 2) ret = mul(x, x) if N % 2: ret = mul(ret, a) return ret def num_stair_ways(N): x = pow(((1, 1), (1, 0)), N) return x[0][0] for i in range(1, 1001): print i, num_stair_ways(i) 

Actually, everything. I hope, like me, the reader is satisfied with the realization that the 200-step staircase can be walked in accordance with the conditions of the problem 453973694165307953197296969697410619233826 in various ways. And that this can be calculated with logarithmic complexity.



UPDATE: following the results of reading comments, I hasten to make a couple of comments:

• Recently there was already an article on a very similar topic. The article has many practical comments. It would be nice for Habré to have an automatic search for similar articles when publishing.
• All arguments about the algorithms for calculating the Nth term of an exponentially growing sequence for O (ln N) operations should take into account the linearly increasing digit capacity of numbers. That is, the number of multiplications can grow as O (ln N), but the complexity of each individual multiplication will still grow linearly from N. Therefore, the overall complexity can remain logarithmic only if it is enough to find the final value for some module.