Реализация на языках программирования
1. Наивная рекурсия (Python)
Сложность: O(2^n) — медленно для больших n
Классический учебный пример, повторяющий математическую формулу, но пересчитывающий одни и те же значения многократно.
def fib_recursive(n: int) -> int:
if n <= 1:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
print(fib_recursive(10)) # Вывод: 55
2. Итеративный метод (JavaScript)
Сложность: O(n) по времени, O(1) по памяти
Оптимальный способ для повседневных задач: хранит только два последних значения и вычисляет результат за один проход цикла.
function fibIterative(n) {
if (n <= 1) return BigInt(n);
let prev = 0n, curr = 1n;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}
console.log(fibIterative(50).toString()); // 12586269025
3. Формула Бине (C++)
Сложность: O(1) — мгновенный расчёт
Позволяет найти n-е число без циклов через Золотое сечение, но ограничена точностью чисел с плавающей точкой (обычно до n ≈ 70).
#include <iostream>
#include <cmath>
long long fibBinet(int n) {
double phi = (1.0 + std::sqrt(5.0)) / 2.0;
return std::round(std::pow(phi, n) / std::sqrt(5.0));
}
int main() {
std::cout << fibBinet(12) << std::endl; // Вывод: 144
return 0;
}