Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи образуют последовательность, в которой каждый новый член равен сумме трёх предыдущих. Если начать с 0, 1 и 1, получим 0, 1, 1, 2, 4, 7, 13, 24 и так далее. Правило напоминает последовательность Фибоначчи, но для следующего шага нужно хранить три значения вместо двух. Это небольшое изменение приводит к другой скорости роста и помогает считать задачи, где очередное состояние достигается тремя способами.
Выберите индекс в калькуляторе: он покажет число и три слагаемых, из которых оно получено. Ниже разберём нумерацию, задачу о ступеньках и алгоритм без повторных вычислений.
Определение и первые члены
Зафиксируем начальные условия , , . Для каждого целого положим
Формула называется рекуррентной: она определяет очередной член через уже известные. Так, , затем , а . Важно учитывать именно индексы: одинаковые единицы на позициях 1 и 2 - два разных члена последовательности.
| Индекс | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 4 | 7 | 13 | 24 | 44 | 81 | 149 |
Существуют и другие соглашения о начале. Например, в OEIS A000073 записаны начальные значения 0, 0, 1: её член с индексом равен нашему . Последовательность значений совпадает со сдвигом, но номер элемента меняется. Поэтому перед сравнением ответов всегда проверяйте три начальных значения и отсчёт индексов. Выбранная здесь конвенция используется и в исследовательской статье о последовательностях трибоначчи.
Как вычислить член по шагам
Пусть нужно найти . Сначала выпишем три начальных числа, а затем будем каждый раз складывать три последних полученных значения:

Удобно вести скользящее окно из трёх значений. После получения суммы самый старый член окна больше не нужен: для следующего шага берём два последних старых числа и новую сумму. Такой способ работает и на бумаге, и в программе. Калькулятор выше позволяет проверить промежуточные значения, а не только конечный ответ.
Чем трибоначчи отличаются от Фибоначчи
В последовательности чисел Фибоначчи каждый член начиная с третьего складывается из двух предыдущих. В трибоначчи слагаемых три, а значит, для однозначного задания нужны три начальных члена. Одной рекуррентной формулы без начальных условий недостаточно: например, старт 0, 0, 1 даёт тот же вид правила, но другие значения на тех же индексах.
Если сравнивать стандартные варианты, первые члены обоих рядов похожи, но затем трибоначчи растут быстрее: при получаем 44 против 21 у Фибоначчи. Обобщение не ограничивается тройкой: можно складывать фиксированное число предыдущих членов, каждый раз задавая достаточно начальных значений. При этом нельзя переносить формулы и индексы одного ряда на другой без проверки. Другая рекуррентная конструкция встречается в статье о числах Стирлинга первого рода: там индексов два, а значения связаны с циклами перестановок.
Задача о подъёме по ступенькам
Пусть за ход можно подняться на 1, 2 или 3 ступеньки, а порядок ходов имеет значение. Обозначим через число способов оказаться на ступеньке . На последнюю ступеньку можно попасть с , или ; эти варианты не пересекаются, поскольку длина последнего шага различна. Поэтому при
Здесь нужны собственные начальные условия: соответствует одному пустому маршруту, , . Значит, , , . В нашей нумерации : сдвиг на два обязателен. Так, пять ступенек дают 13 способов, а не .
Для проверки первых значений перечислим маршруты до третьей ступеньки: , , и . Маршруты и различаются порядком. Если порядок не учитывать или запретить какой-либо шаг, постановка изменится и прежний ответ применять нельзя. Разбиение по последнему действию - типичный приём комбинаторики; подробнее о хранении результатов подобных подзадач рассказывает статья про динамическое программирование.
Как распознать подходящую задачу
Трёхчленная рекурсия возникает не всякий раз, когда в условии встречаются три предмета. Необходимо, чтобы все решения для текущего состояния делились на три непересекающиеся группы, а число решений в каждой группе совпадало с числом решений одной из трёх предыдущих подзадач. В примере со ступеньками группы различаются последним шагом. Удалив его, мы взаимно однозначно сопоставляем маршрут до текущей ступеньки с маршрутом до одной из предыдущих.
Этот аргумент одновременно показывает, почему ничего не пропущено и почему один маршрут не подсчитан дважды. Но он зависит от постановки: если после длинного шага запрещён следующий длинный шаг, информации только о номере ступеньки уже недостаточно. Придётся добавить состояние, которое помнит предыдущий ход, и вывести новую систему переходов. Аналогично, если некоторые ступеньки закрыты, соответствующие значения следует обнулить, и стандартный ряд трибоначчи в общем случае перестанет описывать результат.
Хорошая проверка модели - вручную перечислить небольшие случаи и сравнить их с начальными условиями программы. Нулевая ступенька особенно полезна: один пустой маршрут позволяет построить маршрут одним первым шагом, тогда как ноль способов уничтожил бы такие решения. При этом в другой задаче пустой объект может быть запрещён. Начальные условия выводятся из смысла конкретной задачи, а не выбираются по названию последовательности.
Итеративный алгоритм
Прямой рекурсивный код буквально вызывает вычисление трёх предыдущих членов. Но одни и те же индексы при этом возникают во многих ветвях: например, понадобится при вычислении и , и . Повторная работа быстро увеличивает число вызовов. Итерация решает задачу снизу вверх:
def tribonacci(n):
if n == 0:
return 0
if n <= 2:
return 1
a, b, c = 0, 1, 1
for _ in range(3, n + 1):
a, b, c = b, c, a + b + c
return c
Перед каждой итерацией переменные содержат три последовательных значения. Справа сначала вычисляется их сумма, затем окно сдвигается одновременно. После последней итерации содержит искомый член. При , 1 и 2 работают отдельные условия; функция предполагает неотрицательный целый индекс.
Алгоритм делает сложений при : это арифметических операций и хранимых чисел. Для больших индексов сами числа занимают всё больше бит, поэтому при точном анализе времени и памяти нужно учитывать стоимость операций с длинными целыми. Если же требуется весь ряд для графика, понадобится сохранить значений. Это отдельная цель, а не обязательное условие вычисления одного члена.
Результат также можно получить мемоизацией: функция сохраняет однажды найденный ответ для каждого индекса и при повторном обращении возвращает его из памяти. Это сохраняет наглядную рекурсивную запись, но требует таблицы и использует стек вызовов. Скользящее окно короче по используемой памяти, когда нужен только один ответ и зависимости ограничены тремя предыдущими членами.
Для проверки реализации полезны граничные случаи: индексы 0, 1 и 2 должны вернуть начальные значения без цикла, а при индексе 3 должен выполниться ровно один шаг. Затем можно сравнить результат для индекса 8 с числом 44. Если вместо него получается 24 или 81, стоит проверить границы цикла и договорённость об отсчёте с нуля.
Производящая функция и рост
Последовательность можно упаковать в формальный ряд . Умножим его на : коэффициенты при степенях начиная с сократятся по рекуррентной формуле. С учётом трёх начальных значений останется , поэтому
Это равенство удобно использовать формально, не подставляя конкретное ; как обычный числовой ряд оно выполняется в области сходимости около нуля. Метод вывода и другие примеры рассмотрены в статье о производящих функциях. Если взять начальные условия 0, 0, 1, числитель станет : ещё одна проверка на сдвиг индекса.
Характеристическое уравнение рекурсии имеет вид . Его положительный корень примерно равен 1,83929; для выбранной последовательности отношение стремится к нему при росте . Это не означает, что любое соседнее отношение уже равно пределу: например, . При небольших индексах удобнее вычислять точные суммы, чем применять приближённую оценку роста.
Частые ошибки
- Забывают начальные значения. Одно правило сложения допускает разные последовательности; выпишите все три начальных члена.
- Складывают только два предыдущих числа. Так получится правило Фибоначчи, а не трибоначчи.
- Путают номер и позицию. При отсчёте с нуля шестой записанный элемент - это .
- Не учитывают сдвиг в задаче о ступеньках. Для заданных условий число маршрутов равно , поскольку пустой маршрут считается одним способом.
- Считают постоянную память постоянной в битах. Три сохраняемых целых растут вместе с индексом, если вычисления точные.
FAQ
Чему равно десятое число трибоначчи?
Если под десятым понимается член с индексом 10 при начальных условиях этой статьи, . Если же считать первый записанный член нулевого индекса первым по порядку, десятым будет . Уточните, что означает номер.
Почему для рекурсии нужны три начальных значения?
Для вычисления формула требует , и . Зная эту тройку, можно последовательно получить все следующие члены. Без одного из трёх значений результат в общем случае не определён.
Можно ли вычислить большой член быстрее линейного числа шагов?
Да. Переход от тройки к следующей задаётся матрицей; быстрое возведение матрицы в степень использует матричных умножений. Стоимость длинной арифметики при этом по-прежнему зависит от размера результата.
Коротко
Числа трибоначчи при выбранной нумерации начинаются с 0, 1, 1, а каждый следующий член равен сумме трёх предыдущих. Для точного ответа нужны начальные условия и индексы. Скользящее окно даёт простой итеративный расчёт, а та же рекурсия считает маршруты с шагами длиной 1, 2 и 3 при правильно выбранном сдвиге.
Читайте также

Количество путей в ориентированном графе
Как найти количество путей в ориентированном графе: подсчёт в DAG, динамическое программирование, матрица смежности, заданная длина и влияние циклов на ответ.

Наибольшая общая подпоследовательность: алгоритм и пример
Как найти наибольшую общую подпоследовательность двух строк: таблица динамического программирования, восстановление ответа, пример на словах и оценка сложности.

Разбиение числа на слагаемые: подсчёт и алгоритм
Разбиение числа на слагаемые без учёта порядка: примеры, отличие от упорядоченных сумм, рекуррентная формула и алгоритм динамического программирования.

Числа Фибоначчи: рекуррентная формула и примеры
Числа Фибоначчи и рекуррентная формула: начальные значения, вычисление по шагам, пример со ступеньками, вычисление членов, формула Бине и связь последовательности с золотым сечением.

Задача о рюкзаке: динамическое программирование
Разбор задачи о рюкзаке (0/1 Knapsack) методом ДП: таблица dp[i][w], рекуррентный переход, traceback-восстановление набора. Пошаговые примеры и анализ сложности O(n*W).

Алгоритм Кадане: максимальная сумма подмассива
Алгоритм Кадане за линейное время находит подмассив с наибольшей суммой. Разбираем идею динамического программирования, ловушку отрицательных чисел и реализацию.