Вычисление N-го числа Фибоначчи с помощью табуляции

Вычисление N-го числа Фибоначчи с помощью табуляции

Помимо того, что вычисление N-го числа Фибоначчи является обычным вопросом на собеседовании, это интересное упражнение, поскольку существует множество различных реализаций, которые необходимо найти для решения. В предыдущей статье, которую я написал, я продемонстрировал итеративный метод, рекурсивный метод, а затем мы модифицировали рекурсивный алгоритм, чтобы воспользоваться преимуществами мемоизации, чтобы уменьшить экспоненциальную сложность времени выполнения. Если вы не знакомы с этими методами, вы можете прочитать эту статью здесь. В этой статье я хочу продемонстрировать еще одну технику расчета Фибоначчи с помощью табуляции. Прежде чем мы начнем, я хочу отметить, что этот вопрос задается по-разному. Некоторые интервьюеры ожидают, что вы начнете с 0, а некоторые — с 1. Кроме того, я встречал некоторых интервьюеров, которые считают N индексом в массиве, а другие считают, что N — это визуальная нумерация элементов, что означает отсутствие реального 0-го числа. элемент. В этой статье мы начнем нашу последовательность с 0 и будем считать, что 0-й элемент также равен 0.

Что такое табуляция?

Табуляция на самом деле является методом динамического программирования. Это очень просто описать, но может быть сложно правильно реализовать. С моей точки зрения, это не интуитивные связи, которые вы видите сразу, но по мере того, как вы углубляетесь в проблемы, вы можете начать понимать, как можно сгенерировать решение табуляции. Лично я бы сначала решил проблему по-другому, чтобы убедиться, что вы полностью ее понимаете, прежде чем переходить к табличному решению. Все средства табулирования решают проблему путем построения какой-либо таблицы. Как только таблица построена, где-то в таблице, исходя из проблемы, мы найдем решение нашей проблемы, и затем мы можем вернуть его.

Применение табуляции к задаче Фибоначчи

Задачу вычисления N-го числа Фибоначчи можно разбить на несколько основных математических шагов. Скажем, мы начинаем с первых двух чисел последовательности, 0, 1. Затем мы можем очень легко вычислить третье число, добавив 0 + 1 = 1. Теперь у нас есть 0, 1, 1. Конечно, следующее число будет быть 1 + 1, что было бы 2. Это должно быть ясно, потому что Фибоначчи рассчитывается путем сложения двух предыдущих чисел. Это вся основа решения табличной версии Фибоначчи.

Вы можете видеть, что каждое значение на диаграмме имеет цвет. Стрелка того же цвета пытается показать, как эти значения влияют на последующие значения в строке. Таким образом, здесь мы видим, что, например, первое значение розового цвета влияет на следующие две позиции и так далее по мере продвижения по строке. Как только мы дойдем до фиолетового цвета, у нас будет ответ 3. Итак, из этой диаграммы видно, что для каждого значения, которое мы итерируем, мы должны добавить это значение к следующим двум индексам перед ним. По сути, это табулирование и правильное решение для данного алгоритма. Давайте попробуем закодировать это.

Начнем с создания нашей таблицы. Мы хотим начать с нуля и закончить N-й позицией, поэтому нам понадобится массив длиной N + 1. Кроме того, мы делаем некоторое сложение, поэтому имеет смысл для начала заполнить массив нулями. Здесь нам нужно подумать о наших «базовых случаях». Мы сказали, что будем начинать с 0, так что это должно быть в позиции 0, и мы знаем, что второе число равно 1, поэтому мы устанавливаем это в позицию 1 в нашем массиве. Последний шаг — прокрутить таблицу и для каждой позиции индекса взять значение, хранящееся в этой позиции, и добавить к значениям в следующих двух позициях индекса. Это расчет Фибоначчи путем продвижения значений вперед путем сложения, а не традиционный подход, когда оглядываются на два последних вычисленных значения для расчета следующего. Как только мы достигли конца нашего цикла, нам теперь просто нужно вернуть N-ю позицию в нашей таблице. Эта табличная версия Фибоначчи очень хорошо масштабируется. Для выполнения этого вычисления требуется время O(N). Обратите внимание, что мы проверяем, чтобы убедиться, что мы не устанавливаем значения за пределы массива, потому что это вызовет бесконечный цикл.

Вывод

Это просто введение в табулирование. Эта конкретная версия вычисления N-го числа Фибоначчи на первый взгляд может показаться не такой интуитивно понятной. Когда вы просмотрите диаграммы и увидите решение в коде, вы увидите, как табуляция пытается построить результаты вызовов функций по мере того, как мы итерируемся по таблице, а затем, когда мы завершили заполнение таблицы, нам просто нужно вернуть правильное положение с правильным номером.