Числа трибоначчи переносят идею Фибоначчи на три слагаемых: 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
Примеры
Ввод:
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.
Ввод:
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. Следуйте условию и ограничениям выше.