Все задачи
Легко Решено: 0 Процент решений: 0%

Числа трибоначчи

Верните n-е число трибоначчи, где каждый член равен сумме трёх предыдущих.

Чему вы научитесь

  • Вычислять последовательность итеративно
  • Хранить только несколько последних членов
  • Сразу возвращать начальные члены

Условие

Числа трибоначчи переносят идею Фибоначчи на три слагаемых: T(0) = 0, T(1) = 0, T(2) = 1, а дальше T(n) = T(n − 1) + T(n − 2) + T(n − 3). Последовательность выглядит так: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, …

Реализуйте tribonacci(n).

Входные данные

n: номер члена, начиная с 0.

Выходные данные

Верните T(n). В каждый момент нужны только три последних члена, так что достаточно цикла с тремя переменными.

Ограничения

0 ≤ n ≤ 74

Примеры

Пример 1
Ввод:
n = 7

Ожидаемый вывод:
expected = 13
Ввод:
long long n = 7;

Ожидаемый вывод:
long long expected = 13;
Ввод:
long n = 7;

Ожидаемый вывод:
long expected = 13;

Пояснение

Члены последовательности: 0, 0, 1, 1, 2, 4, 7, 13, поэтому T(7) = 13.

Пример 2
Ввод:
n = 2

Ожидаемый вывод:
expected = 1
Ввод:
long long n = 2;

Ожидаемый вывод:
long long expected = 1;
Ввод:
long n = 2;

Ожидаемый вывод:
long expected = 1;

Пояснение

T(2) - первая единица в последовательности: 1.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Первые три члена возвращайте сразу.

Подсказка 2

Храните три переменные и на каждом шаге сдвигайте их.

Подсказка 3

Рекурсивное решение без запоминания повторяет одну и ту же работу и слишком медленное.

Ожидаемая сложность

время O(n), доп. память O(1)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

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