EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 9 минут
#числа трибоначчи#рекуррентная формула#последовательности#динамическое программирование#алгоритмы
Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи образуют последовательность, в которой каждый новый член равен сумме трёх предыдущих. Если начать с 0, 1 и 1, получим 0, 1, 1, 2, 4, 7, 13, 24 и так далее. Правило напоминает последовательность Фибоначчи, но для следующего шага нужно хранить три значения вместо двух. Это небольшое изменение приводит к другой скорости роста и помогает считать задачи, где очередное состояние достигается тремя способами.

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

Определение и первые члены

Зафиксируем начальные условия T0=0T_0=0, T1=1T_1=1, T2=1T_2=1. Для каждого целого n≥3n\geq 3 положим

Tn=Tn−1+Tn−2+Tn−3.T_n=T_{n-1}+T_{n-2}+T_{n-3}.

Формула называется рекуррентной: она определяет очередной член через уже известные. Так, T3=1+1+0=2T_3=1+1+0=2, затем T4=2+1+1=4T_4=2+1+1=4, а T5=4+2+1=7T_5=4+2+1=7. Важно учитывать именно индексы: одинаковые единицы на позициях 1 и 2 - два разных члена последовательности.

На каждом шаге три предыдущих члена складываются в выделенную сумму, затем окно переходит к следующему индексу и возвращается назад.
Индекс nn012345678910
TnT_n01124713244481149

Существуют и другие соглашения о начале. Например, в OEIS A000073 записаны начальные значения 0, 0, 1: её член с индексом n+1n+1 равен нашему TnT_n. Последовательность значений совпадает со сдвигом, но номер элемента меняется. Поэтому перед сравнением ответов всегда проверяйте три начальных значения и отсчёт индексов. Выбранная здесь конвенция используется и в исследовательской статье о последовательностях трибоначчи.

Как вычислить член по шагам

Пусть нужно найти T8T_8. Сначала выпишем три начальных числа, а затем будем каждый раз складывать три последних полученных значения:

T3=0+1+1=2,T4=1+1+2=4,T5=1+2+4=7,T6=2+4+7=13,T7=4+7+13=24,T8=7+13+24=44.\begin{aligned} T_3&=0+1+1=2, & T_4&=1+1+2=4,\\ T_5&=1+2+4=7, & T_6&=2+4+7=13,\\ T_7&=4+7+13=24, & T_8&=7+13+24=44. \end{aligned}
Индексы от нуля до пяти и вычисление пятого числа трибоначчи: 1 плюс 2 плюс 4 равно 7
Индексы от нуля до пяти и вычисление пятого числа трибоначчи: 1 плюс 2 плюс 4 равно 7

Удобно вести скользящее окно из трёх значений. После получения суммы самый старый член окна больше не нужен: для следующего шага берём два последних старых числа и новую сумму. Такой способ работает и на бумаге, и в программе. Калькулятор выше позволяет проверить промежуточные значения, а не только конечный ответ.

Чем трибоначчи отличаются от Фибоначчи

В последовательности чисел Фибоначчи каждый член начиная с третьего складывается из двух предыдущих. В трибоначчи слагаемых три, а значит, для однозначного задания нужны три начальных члена. Одной рекуррентной формулы без начальных условий недостаточно: например, старт 0, 0, 1 даёт тот же вид правила, но другие значения на тех же индексах.

Если сравнивать стандартные варианты, первые члены обоих рядов похожи, но затем трибоначчи растут быстрее: при n=8n=8 получаем 44 против 21 у Фибоначчи. Обобщение не ограничивается тройкой: можно складывать фиксированное число предыдущих членов, каждый раз задавая достаточно начальных значений. При этом нельзя переносить формулы и индексы одного ряда на другой без проверки. Другая рекуррентная конструкция встречается в статье о числах Стирлинга первого рода: там индексов два, а значения связаны с циклами перестановок.

Задача о подъёме по ступенькам

Пусть за ход можно подняться на 1, 2 или 3 ступеньки, а порядок ходов имеет значение. Обозначим через CmC_m число способов оказаться на ступеньке mm. На последнюю ступеньку можно попасть с m−1m-1, m−2m-2 или m−3m-3; эти варианты не пересекаются, поскольку длина последнего шага различна. Поэтому при m≥3m\geq 3

Cm=Cm−1+Cm−2+Cm−3.C_m=C_{m-1}+C_{m-2}+C_{m-3}.

Здесь нужны собственные начальные условия: C0=1C_0=1 соответствует одному пустому маршруту, C1=1C_1=1, C2=2C_2=2. Значит, C3=4C_3=4, C4=7C_4=7, C5=13C_5=13. В нашей нумерации Cm=Tm+2C_m=T_{m+2}: сдвиг на два обязателен. Так, пять ступенек дают 13 способов, а не T5=7T_5=7.

Для проверки первых значений перечислим маршруты до третьей ступеньки: (1,1,1)(1,1,1), (1,2)(1,2), (2,1)(2,1) и (3)(3). Маршруты (1,2)(1,2) и (2,1)(2,1) различаются порядком. Если порядок не учитывать или запретить какой-либо шаг, постановка изменится и прежний ответ применять нельзя. Разбиение по последнему действию - типичный приём комбинаторики; подробнее о хранении результатов подобных подзадач рассказывает статья про динамическое программирование.

Как распознать подходящую задачу

Трёхчленная рекурсия возникает не всякий раз, когда в условии встречаются три предмета. Необходимо, чтобы все решения для текущего состояния делились на три непересекающиеся группы, а число решений в каждой группе совпадало с числом решений одной из трёх предыдущих подзадач. В примере со ступеньками группы различаются последним шагом. Удалив его, мы взаимно однозначно сопоставляем маршрут до текущей ступеньки с маршрутом до одной из предыдущих.

Этот аргумент одновременно показывает, почему ничего не пропущено и почему один маршрут не подсчитан дважды. Но он зависит от постановки: если после длинного шага запрещён следующий длинный шаг, информации только о номере ступеньки уже недостаточно. Придётся добавить состояние, которое помнит предыдущий ход, и вывести новую систему переходов. Аналогично, если некоторые ступеньки закрыты, соответствующие значения следует обнулить, и стандартный ряд трибоначчи в общем случае перестанет описывать результат.

Хорошая проверка модели - вручную перечислить небольшие случаи и сравнить их с начальными условиями программы. Нулевая ступенька особенно полезна: один пустой маршрут позволяет построить маршрут одним первым шагом, тогда как ноль способов уничтожил бы такие решения. При этом в другой задаче пустой объект может быть запрещён. Начальные условия выводятся из смысла конкретной задачи, а не выбираются по названию последовательности.

Итеративный алгоритм

Прямой рекурсивный код буквально вызывает вычисление трёх предыдущих членов. Но одни и те же индексы при этом возникают во многих ветвях: например, T5T_5 понадобится при вычислении и T8T_8, и T7T_7. Повторная работа быстро увеличивает число вызовов. Итерация решает задачу снизу вверх:

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

Перед каждой итерацией переменные содержат три последовательных значения. Справа сначала вычисляется их сумма, затем окно сдвигается одновременно. После последней итерации cc содержит искомый член. При n=0n=0, 1 и 2 работают отдельные условия; функция предполагает неотрицательный целый индекс.

Алгоритм делает n−2n-2 сложений при n≥3n\geq 3: это O(n)O(n) арифметических операций и O(1)O(1) хранимых чисел. Для больших индексов сами числа занимают всё больше бит, поэтому при точном анализе времени и памяти нужно учитывать стоимость операций с длинными целыми. Если же требуется весь ряд для графика, понадобится сохранить n+1n+1 значений. Это отдельная цель, а не обязательное условие вычисления одного члена.

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

Для проверки реализации полезны граничные случаи: индексы 0, 1 и 2 должны вернуть начальные значения без цикла, а при индексе 3 должен выполниться ровно один шаг. Затем можно сравнить результат для индекса 8 с числом 44. Если вместо него получается 24 или 81, стоит проверить границы цикла и договорённость об отсчёте с нуля.

Производящая функция и рост

Последовательность можно упаковать в формальный ряд G(x)=∑n≥0TnxnG(x)=\sum_{n\geq0}T_nx^n. Умножим его на 1−x−x2−x31-x-x^2-x^3: коэффициенты при степенях начиная с x3x^3 сократятся по рекуррентной формуле. С учётом трёх начальных значений останется xx, поэтому

G(x)=x1−x−x2−x3.G(x)=\frac{x}{1-x-x^2-x^3}.

Это равенство удобно использовать формально, не подставляя конкретное xx; как обычный числовой ряд оно выполняется в области сходимости около нуля. Метод вывода и другие примеры рассмотрены в статье о производящих функциях. Если взять начальные условия 0, 0, 1, числитель станет x2x^2: ещё одна проверка на сдвиг индекса.

Характеристическое уравнение рекурсии имеет вид r3−r2−r−1=0r^3-r^2-r-1=0. Его положительный корень примерно равен 1,83929; для выбранной последовательности отношение Tn+1/TnT_{n+1}/T_n стремится к нему при росте nn. Это не означает, что любое соседнее отношение уже равно пределу: например, T8/T7=44/24≈1,8333T_8/T_7=44/24\approx1{,}8333. При небольших индексах удобнее вычислять точные суммы, чем применять приближённую оценку роста.

Частые ошибки

  • Забывают начальные значения. Одно правило сложения допускает разные последовательности; выпишите все три начальных члена.
  • Складывают только два предыдущих числа. Так получится правило Фибоначчи, а не трибоначчи.
  • Путают номер и позицию. При отсчёте с нуля шестой записанный элемент - это T5=7T_5=7.
  • Не учитывают сдвиг в задаче о ступеньках. Для заданных условий число маршрутов равно Tm+2T_{m+2}, поскольку пустой маршрут считается одним способом.
  • Считают постоянную память постоянной в битах. Три сохраняемых целых растут вместе с индексом, если вычисления точные.

FAQ

Чему равно десятое число трибоначчи?

Если под десятым понимается член с индексом 10 при начальных условиях этой статьи, T10=149T_{10}=149. Если же считать первый записанный член нулевого индекса первым по порядку, десятым будет T9=81T_9=81. Уточните, что означает номер.

Почему для рекурсии нужны три начальных значения?

Для вычисления T3T_3 формула требует T2T_2, T1T_1 и T0T_0. Зная эту тройку, можно последовательно получить все следующие члены. Без одного из трёх значений результат в общем случае не определён.

Можно ли вычислить большой член быстрее линейного числа шагов?

Да. Переход от тройки (Tn,Tn−1,Tn−2)(T_n,T_{n-1},T_{n-2}) к следующей задаётся матрицей; быстрое возведение матрицы в степень использует O(log⁡n)O(\log n) матричных умножений. Стоимость длинной арифметики при этом по-прежнему зависит от размера результата.

Коротко

Числа трибоначчи при выбранной нумерации начинаются с 0, 1, 1, а каждый следующий член равен сумме трёх предыдущих. Для точного ответа нужны начальные условия и индексы. Скользящее окно даёт простой итеративный расчёт, а та же рекурсия считает маршруты с шагами длиной 1, 2 и 3 при правильно выбранном сдвиге.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Количество путей в ориентированном графе

Количество путей в ориентированном графе

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

8 ноября 20268 минут
Наибольшая общая подпоследовательность: алгоритм и пример

Наибольшая общая подпоследовательность: алгоритм и пример

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

8 ноября 20269 минут
Разбиение числа на слагаемые: подсчёт и алгоритм

Разбиение числа на слагаемые: подсчёт и алгоритм

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

8 ноября 20269 минут
Числа Фибоначчи: рекуррентная формула и примеры

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

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

8 ноября 20269 минут
Задача о рюкзаке: динамическое программирование

Задача о рюкзаке: динамическое программирование

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

17 июня 20267 минут
Алгоритм Кадане: максимальная сумма подмассива

Алгоритм Кадане: максимальная сумма подмассива

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

6 февраля 202610 минут