Последовательность Фибоначчи начинается с 0, 1, и каждое следующее число — это сумма двух предыдущих: 0, 1, 1, 2, 3, 5, 8, …. F(0) = 0 и F(1) = 1.
Реализуйте функцию fibonacci(n).
Входные данные
n: Позиция в последовательности.
Выходные данные
Верните F(n).
Ограничения
0 ≤ n ≤ 90
Примеры
Пример 1
Ввод:
n = 10
Ожидаемый вывод:
expected = 55Ввод:
long long n = 10;
Ожидаемый вывод:
long long expected = 55;Ввод:
long n = 10;
Ожидаемый вывод:
long expected = 55;Пояснение
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55: F(10) = 55.
Пример 2
Ввод:
n = 0
Ожидаемый вывод:
expected = 0Ввод:
long long n = 0;
Ожидаемый вывод:
long long expected = 0;Ввод:
long n = 0;
Ожидаемый вывод:
long expected = 0;Пояснение
По определению F(0) = 0.
Как подступиться
Сначала попробуйте сами, затем открывайте подсказки по одной.
Подсказка 1
Первые два значения фиксированы, так что начните с базовых случаев.
Подсказка 2
Стройте следующие значения из двух предыдущих вместо повторного вычисления рекурсией.
Подсказка 3
Используйте итеративный подход, чтобы избежать лишней работы и глубокой рекурсии.
Ожидаемая сложность
время O(n), доп. память O(1)
Ссылки
Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.