Числа Фибоначчи
Вы решили задачу. Теперь можно сравнить подходы.
Храним два соседних числа последовательности.
Авторский разбор для локальной версии на основе условия задачи. Это не выгрузка чужих посылок и не официальное решение исходного сайта.
Ваше принятое решение
Рекомендуемое решение: Две переменные
После 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) бит значений.
На что обратить внимание
- Нумерация начинается с F(0)=0; присваивание пары должно использовать старые значения.
Рекомендация учитывает сложность и читаемость для этой задачи. Единственного самого быстрого решения для всех размеров входа и всех компьютеров может не быть.