Что такое числа Фибоначчи?

Что такое числа Фибоначчи?

Числа Фибоначчи — это последовательность целых чисел, в которой каждое число является суммой двух предыдущих чисел. Эта последовательность названа в честь итальянского математика Леонардо Фибоначчи, жившего в XIII веке.

Определение

Последовательность Фибоначчи определяется следующим образом:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) для n ≥ 2

Первые числа последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

Где встречаются в природе

• Спираль раковины — каждая камера больше предыдущей в отношении Фибоначчи
• Лепестки цветов — часто кратны числам Фибоначчи
• Ветвление деревьев — следует паттерну Фибоначчи
• ДНК молекулы — пропорции соответствуют последовательности
• Галактики — спирали имеют форму спирали Фибоначчи

Реализация в C++

1. Рекурсивный подход (неэффективный):

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// Вызов
int result = fibonacci(10);  // 55

Минусы: экспоненциальная сложность O(2^n), очень медленно для больших n.

2. Итеративный подход (эффективный):

int fibonacci(int n) {
    if (n <= 1) return n;
    
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

// Вызов
int result = fibonacci(10);  // 55

Плюсы: линейная сложность O(n), работает очень быстро.

3. С мемоизацией (оптимизация рекурсии):

#include <unordered_map>

std::unordered_map<int, long long> memo;

long long fibonacci(int n) {
    if (n <= 1) return n;
    
    if (memo.find(n) != memo.end()) {
        return memo[n];
    }
    
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

// Вызов
long long result = fibonacci(50);  // быстро, даже для больших чисел

4. С использованием массива:

long long fibonacci(int n) {
    if (n <= 1) return n;
    
    std::vector<long long> fib(n + 1);
    fib[0] = 0;
    fib[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    
    return fib[n];
}

5. Генерация последовательности:

void printFibonacci(int count) {
    long long a = 0, b = 1;
    
    std::cout << a << " ";
    for (int i = 1; i < count; i++) {
        std::cout << b << " ";
        long long temp = a + b;
        a = b;
        b = temp;
    }
    std::cout << std::endl;
}

// Вывод: 0 1 1 2 3 5 8 13 21 34
printFibonacci(10);

Сравнение подходов

Свойства чисел Фибоначчи

• Золотое сечение: отношение F(n+1)/F(n) стремится к 1.618... (φ)
• Делимость: если m делит n, то F(m) делит F(n)
• НОД: НОД(F(m), F(n)) = F(НОД(m, n))
• Сумма: F(1) + F(2) + ... + F(n) = F(n+2) - 1

Практическое применение

• Компьютерная графика — алгоритмы поиска, оптимизация
• Алгоритмы — хеширование, структуры данных
• Финансы — технический анализ рынков
• Кодирование — сжатие данных