Fibonacci Explorer

Применение чисел Фибоначчи в реальном мире

Последовательность Фибоначчи и золотое сечение встречаются в самых неожиданных местах - от природы до финансовых рынков.

Природа

  • Расположение листьев на стебле (филлотаксис)
  • Спирали раковин моллюсков
  • Расположение семян в подсолнухе
  • Ветвление деревьев

Искусство и архитектура

  • Пропорции в классической архитектуре (Парфенон)
  • Композиция в живописи (Леонардо да Винчи)
  • Музыкальные композиции (Бетховен, Дебюсси)
  • Дизайн логотипов и брендинг

Алгоритмы и информатика

  • Поиск Фибоначчи (улучшенный бинарный поиск)
  • Кучи Фибоначчи в алгоритмах графов
  • Динамическое программирование
  • Технический анализ финансовых рынков

Технические применения

Поиск Фибоначчи

Алгоритм поиска в отсортированном массиве, который делит массив на части, соответствующие числам Фибоначчи.

function fibonacciSearch(arr, x, n):
    fibMMm2 = 0  # (m-2)-ое число Фибоначчи
    fibMMm1 = 1  # (m-1)-ое число Фибоначчи
    fibM = fibMMm2 + fibMMm1  # m-ое число
    
    while fibM < n:
        fibMMm2 = fibMMm1
        fibMMm1 = fibM
        fibM = fibMMm2 + fibMMm1
    
    offset = -1
    
    while fibM > 1:
        i = min(offset+fibMMm2, n-1)
        
        if arr[i] < x:
            fibM = fibMMm1
            fibMMm1 = fibMMm2
            fibMMm2 = fibM - fibMMm1
            offset = i
        
        elif arr[i] > x:
            fibM = fibMMm2
            fibMMm1 = fibMMm1 - fibMMm2
            fibMMm2 = fibM - fibMMm1
        
        else:
            return i
    
    if fibMMm1 and arr[offset+1] == x:
        return offset+1
    
    return -1

Фибоначчиевые кучи

Структура данных, используемая для эффективной реализации алгоритмов Дейкстры и Прима.

  • Амортизированное время вставки: O(1)
  • Амортизированное время извлечения минимума: O(log n)
  • Амортизированное время уменьшения ключа: O(1)