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

Число Фибоначчи

Верните n-е число Фибоначчи.

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

  • Строить последовательность из предыдущих членов
  • Обновлять две переменные одновременно
  • Понять, почему наивная рекурсия медленная

Условие

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

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

# Участник Язык Время Память Оценка ИИ Решение
1 HJhettory Jurash Python 774 ms - 4/5 Посмотреть код
2 KKKaneki Ken Python 858 ms - 5/5 Посмотреть код

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

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

Внимание, спойлер: ниже 2 полных решений Попробуйте сначала решить сами. Вы всегда можете посмотреть код других и AI-обзоры. Войдите и решите задание, чтобы присоединиться к обсуждению.