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

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

    Вы поднимаетесь по лестнице. На каждом шаге вы можете подняться либо на 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);
    }
    


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

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

    image

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

    Сам по себе этот факт уже интересен, однако особенно интересен он в сочетании с алгоритмом быстрого возведения в степень. Применительно к нашей задаче это означает, что мы можем получить ответ за 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-ю разными способами. И что это может быть подсчитано с логарифмической сложностью.

    UPDATE: по итогам чтения комментариев спешу сделать пару замечаний:
    • Недавно уже была статья на очень похожую тему. Статья имеет много дельных комментариев. Было бы недурно на хабре иметь автоматический поиск сходных статей при обубликовании.
    • Все рассуждения про алгоритмы вычисления N-го члена экспоненциально растущей последовательности за O(ln N) операций должны принимать во внимание линейно растущую разрядность чисел. То есть, количество умножений может расти как O(ln N), но сложность каждого отдельно взятого умножения будет все же расти линейно от N. Поэтому общая сложность может оставаться логарифмической, только если достаточно нахождения финального значения по какому-либо модулю.

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 36

      +15
      Мне кажется, что в последнее время на хабре стало черезчур много чисел фибоначи.
        –1
        Поздравляю, вы открыли для себя динамическое программирование
          +5
          Не совсем. Финальный алгоритм не имеет отношения к динамическому программированию.
          +5
          Не может это быть подсчитано с логарифмической сложностью, т. к. вам потребуется использовать «длинную арифметику», которая не умеет перемножать два числа за О(1). Мне одному кажется, что про подсчет чисел Фибоначчи была уже не одна статья на Хабре (зачем тогда изобретать колесо)?
            +1
            Ну вот из статьи в статью такие комментарии кочуют, как же ж вы не понимаете, что сложность считается относительно некоторой величины, более того, подавляющее число людей считает сложность относительно числа арифметических операций, а не числа ассемблерных инструкций.
              0
              Не знаю, как «подавляющее число людей», а математики сложность считают в элементарных операциях. Есть некоторая стандартная модель вычислимости — машина Тьюринга (которая вообще не знает ничего про числа) и несколько ей полиномиально эквивалентных — например, RAM. Если мы разрешим перемножать любые числа за O(1), то можно сгенерировать данные экспоненциального размера за полиномиальное время. Что совсем нехорошо, ибо непонятно, чему это соответствует на машине Тьюринга.
                –1
                Мы с вами разные математики, видимо. Есть такое дело, что в разных областях считаются разные величины. Вы, конечно, тоже правы, но даже так получается O(log(N)) (см ниже).
                  –1
                  Очень разные. Можно узнать точное определение сложности алгоритма в модели машины Тьюринга, которое Вы предлагаете?

                  И не получается так log(N). N-е число Фибоначи имеет ассимптотику ((1+sqrt(5))/2)^N, что дает экспоненциальную величину и линейное количество символов.

                  А вот если считать x1=2, x2=x1*x1, x3=x2*x2, ..., то xN = 2^(2^N), что уже требует экспоненциального числа символов для записи, но линейного числа умножений для вычисления.
                  +1
                  Вы какую то другую математику видимо имеете в виду, какое еще количество элементарных операций? О_О
                    –1
                    Зависит от модели. В МТ — один шаг, в RAM — арифметика с числами ограниченного размера, в CPU — один такт.
                    В общем случае, у нас есть бесконечное пространство состояний, раскладывающееся в произведение бесконечного числа конечных подпространств. Зафиксируем число N, тогда элементарной операцией можно назвать изменение состояне, затрагивающее не более чем N подпространств.
                  –2
                  Вот я даже исчерпывающую математику проведу: если нам надо найти N-е число фибоначчи, то сложность будет (возьмем алгоритм перемножения длинных чисел в лоб) O(log(N)*k^2), где k — максимальная «длина» длинного числа, используемого в алгоритме (k конечно), а O(log(N)*k^2) == O(log(N)) по определению O(), а значит таки да, log(N).
                    +1
                    k — не конечно, оно зависит от N.
                      –2
                      Да, но для любого N существует и конечно max(k(N)) == k, я считаю относительно него, так как это огрубление оценки на O() влияния не произведет.
                        +2
                        Для любого N существует и конечно N = k. Тогда O(N) = O(k) = O(1).
                          +7
                          Вы говорите чушь, читайте теорию :)
                            0
                            Да я уже понял, что полез в чужой огород со своим уставом, конечно вы правы, уже разобрался.
                              +3
                              Не совсем так. Это математика, в ней нет «уставов». В ней есть определения и формальные выводы. И Ваш последний коммент в них ну никак не укладывается.
                                0
                                Именно так. Для меня естественным является вычислитель с атомарной арифметикой действительных (и даже комплексных) чисел. Учитывая, что автор оригинального комментария не сказал, что он говорил о машине тьюринга, так получилось, что я продолжил мыслить в той системе, в которой привык, ну и отсюда и фэйл.
                      0
                      Если бы я не понимал… Зачем, по вашему, оценивают «сложность» некоторого алгоритма? Разве не для того, чтобы потом его сравнить с другим и сказать «асимптотически он будет работать быстрее». А в данном случае, мы не можем принять арифметическую операцию умножения за О(1), т. к. «время», потраченное на ее выполнение, зависит от длины числа (причем, пропорционально квадрату, если использовать «наивный» алгоритм). И, как уже отмечалось в другой статье, как раз использование «длинной арифметики» сильно увеличивает время работы этого алгоритма.

                      P. S. сложность считают относительно числа арифметических операций, когда все числа «влазят» в машинное слово.
                        0
                        То есть по вашем рассуждениям я так понимаю: если я ввожу int, то сложность алгоритма O(log(N)), а если длинное число, то сложность того же самого алгоритма O(log(N)). Либо же вы считаете этот алгоритм другим алгоритмом, как бы расширенным на длинные числа. В этом случае ваши рассуждения вполне понятны, да.
                          0
                          Во второй раз там «не O(log(N))», опечатался.
                            0
                            Естественно. Если Вы используете для ответа int, то Вы считаете не числа Фибоначчи, а числа Фибоначчи по некоторому модулю (скорее всего, 2^32). И их уже действительно без проблем можно найти за логарифмическое время, а длина ответа вообще ограничена константой.
                              0
                              Да, я понял, я просто не привык привязываться к машине тьюринга, вот и не сразу понял, почему я могу быть не прав.
                                0
                                А машина Тьюринга тут совершенно не при чем. Обычный процессор (если не брать в рассчет ограниченность памяти) ей полиномиально эквивалентен.
                            –1
                            Это верное замечание. Действительно, факт того, что числа длинные меняет сложность алгоритма. Константы могуть быть разными, но сложность действительно будет линейной, если только в задаче не достаточно нахождения модуля.
                              0
                              сложность считают относительно числа арифметических операций, когда все числа «влазят» в машинное слово.

                              Если уж до конца занудничать, то при условии, что эти арифметические операции реализованы за константное время, что не для всех машин справедливо. Например в i8080 вообще не было умножения, даже 8-битного
                                +1
                                Это неважно как раз. Даже если умножение машинных слов реализовать руками, с точки зрения алгоритма это все равно будет константа. Весь сыр-бор начинается именно если размер промежуточного и конечного результата не фиксирован, а пропорционален N.
                                  0
                                  Это смотря как реализовывать, по-моему. Если суммированием поразрядных сдвигов (или как это правильно называется? 100 лет не занимался), то константа (относительно сложения), а вот если многократным сложением, то линейная зависимость и, скажем, для факториала получаем сложность O(N) относительно умножения, но при этом O(N2) относительно сложения. Или заблуждаюсь?
                                    0
                                    Я бы ожидал, что используется shift-and-add1, тот, что Вы указали первым. Интересное наблюдение: если при реализации такого алгоритма умножения доступна O(1) проверка «является ли текущий обрабатываемый бит самым крайним слева/справа», то сдвиги-сложения можно остановить в нужный момент, и алгоритм в некотором смысле становится O(ln N).

                                    Еще интересная тема — деление. Вот оно уж точно в той или иной степени итеративное, и количество итераций зависит от входных данных. Другое дело, что современное железо старается эти итерации всячески амортизировать и дать гарантированную оценку сверху сложности операции деления для любых входных данных.
                                      0
                                      Если у нас есть ограничение на размер множителей, т.е. функция умножения определяется на конечном множестве, то ее сложность равна (max_{n <= N,m <= N} time(mul, n, m)) = O(1).
                            +1
                            Черт. Во-первых, алгоритм тривиален, во-вторых, недавно была статья на хабре.
                            Пойду писать статью про поиски в ширину и глубину.
                              0
                              Мда, действительно была статья. Пойду почитаю. Но там не было про «лесенку», думаю и это будет кому-нибудь интересным.
                                +1
                                Да, а давайте еще про все возможные задачи, которые решаются лобовым применением стандартных алгоритмов, статьи писать?
                                  0
                                  Не скажу за «все возможные» задачи, но про наиболее интересные из них с удовольствием почитал бы.
                                    0
                                    А почему нет? Для многих начинающих проблемой является перейти от реальной задачи к абстрактному алгоритму.
                                      +1
                                      Ну вот есть реальные задачи, где используются стандартные алгоритмы (из банального — задача о рюкзаке для разбиения категорий по колонкам как можно ровнее). Но вот эти задачи «о лесенках» как раз являются стандартными задачами на тот или иной стандартный алгоритм. И их подборок уже весьма немало в прекрасном изложении. Выбирать из этих задач одну случайную и писать про нее статью — довольно странная идея, как мне кажется.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое