Числа Фибоначчи
Храним два соседних числа последовательности.
Как к ней подойти
Разберитесь, как повторять действие, пока выполняется условие, и вовремя остановить цикл.
Цикл while продолжается, пока условие истинно. Продумайте, какое значение меняется на каждом шаге и почему цикл когда-нибудь завершится. Проверяйте как обычный ввод, так и случай, когда тело цикла выполняется ноль раз.
После k шагов a равно F(k), а b равно F(k+1). Это рекомендуемый вариант для изучения циклов: он простой и хранит только два числа. Для очень большого n ниже приведён более быстрый по числу арифметических операций вариант.
Проверьте перед запуском
- Нумерация начинается с F(0)=0; присваивание пары должно использовать старые значения.
Сравните свой подход
Ниже - готовое решение, другой способ, если он есть, и важные детали проверки.
Ваше принятое решение
Рекомендуемое решение: Две переменные
После k шагов a равно F(k), а b равно F(k+1). Это рекомендуемый вариант для изучения циклов: он простой и хранит только два числа. Для очень большого n ниже приведён более быстрый по числу арифметических операций вариант.
n = int(input())
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
print(a)
Время: O(n) сложений. Память: O(1) целых чисел; O(n) бит.
Другой способ: Таблица значений
Сохраняем все ранее вычисленные числа; удобно для последующих запросов.
n = int(input())
f = [0, 1]
for i in range(2, n + 1):
f.append(f[i - 1] + f[i - 2])
print(f[n])
Время: O(n) сложений. Память: O(n) целых чисел; O(n²) бит.
Другой способ: Быстрое удвоение для больших n
Пара F(n), F(n+1) вычисляется по формулам удвоения из пары для n//2. Это более сложный, масштабируемый алгоритм: рекурсия логарифмическая, зато вместо простых сложений используются умножения больших чисел.
def pair(n):
if n == 0:
return 0, 1
a, b = pair(n // 2)
c = a * (2 * b - a)
d = a * a + b * b
return (d, c + d) if n % 2 else (c, d)
n = int(input())
print(pair(n)[0])
Время: O(log(n + 1)) арифметических операций над растущими целыми. Память: O(log(n + 1)) кадров и O(n) бит значений.