Раз дощечка, два дощечка — будет лесенка…

Именно о лесенках хотелось бы немного поговорить. Есть такая относительно распространенная задача с программистских собеседований:

Вы поднимаетесь по лестнице. На каждом шаге вы можете подняться либо на 1 ступеньку, либо на 2. Всего лестница имеет n ступенек. Сколькими разными способами вы можете дойти до конце лестницы?

Задача не сильно сложная, но имеющая пару интересных моментов относительно минимально возможной сложности решения и демонстрирующая «штуки, которые интересно знать».

Очевидно, что так или иначе решение начинается с наблюдения, что на каждом шаге у нас есть выбор из двух действий: сделать один шаг или сделать два шага. В первом случае лестница уменьшается на одну ступеньку, во втором — на две. Общее количество возможных способов обойти лестницу равно сумме количества способов сделать это, если мы начинаем с одной ступеньки, и количества способов, если начинаем с двух. В итоге решение сводится к рекуррентной формуле:

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

Рекурсивная или итеративная реализация данного алгоритма «в лоб» выглядит ненамного длиннее самого соотношения (проблему переполнения оставляем за скобками):

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

Само по себе это решение верное, но его эффективность низка: алгоритм экспоненциален ^[1]. Сложность можно уменьшить, воспользовавшись мемоизацией ^[2]. Интуитивное объяснение: с каждой конкретной ступеньки на лестнице количество способов дойти до конца не зависит от того, как мы попали на эту ступеньку, поэтому ответ имеет смысл запомнить и использовать на следующих шагах расчета. Код приводить не буду — главное, что вкупе с итерацией получается линейное решение. Однако это не все.

Внимательный читатель заметит, что соотношение выше является попросту формулой чисел Фибоначчи ^[3]с поправкой n на единицу (поправка появляется из-за того, что начальные условия другие — Fib(0) = 0, Fib(1) = 1, Fib(2) = 1, а в нашем случае лесенки F(0) = 1, F(1) = 1, F(2) = 2). Известно, что для чисел Фибоначчи имеет место следующее соотношение:

Таким образом, после данного возведения в степень результирующая матрица будет содержать интересующее нас «n+1»-ое число Фибоначчи в первом столбце первой строки (элементы матриц традиционно индексирую с единицы).

Сам по себе этот факт уже интересен, однако особенно интересен он в сочетании с алгоритмом быстрого возведения в степень ^[4]. Применительно к нашей задаче это означает, что мы можем получить ответ за O(ln N) шагов. Код этого решения на языке Python (опять же, чтобы забыть пока про проблему переполнения — Python автоматически переключается на использование big integer, когда это надо) выглядит так:

#!/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)

Собственно, все. Надеюсь, как и я, читатель испытывает удовлетворение от осознания факта, что лестницу длиной в 200 ступенек можно прошагать в соответствии с условиями задачи 453973694165307953197296969697410619233826-ю разными способами. И что это может быть подсчитано с логарифмической сложностью.

Автор: aalexand