Последовательность Фибоначчи: подробный разбор решения

Почему эта задача важна?

Последовательность Фибоначчи — это фундаментальная математическая последовательность, которая позволяет оценить:

• 🧮 Навыки оптимизации рекурсивных алгоритмов
• 🧠 Понимание принципов динамического программирования
• ⚡ Умение выбирать эффективные алгоритмы в зависимости от контекста
• 🔍 Способность применять математические свойства для ускорения вычислений
• 🌱 Понимание взаимосвязи между математикой и природными явлениями

Постановка задачи

Классическая формулировка:

Последовательность Фибоначчи определяется рекуррентным соотношением:

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

Требуется вычислить n-е число Фибоначчи.

Математическая формулировка:

Для заданного целого неотрицательного числа n найти F(n), где F(n) — n-е число в последовательности Фибоначчи.

Примеры:

// Первый пример ✅
Input: n = 5
Output: 5
Объяснение: F(5) = F(4) + F(3) = 3 + 2 = 5
Последовательность: 0, 1, 1, 2, 3, 5

// Второй пример ✅
Input: n = 10
Output: 55
Объяснение: F(10) = F(9) + F(8) = 34 + 21 = 55
Последовательность: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Рекурсивный подход (наивная реализация) 🔍

function fibonacciRecursive(n) {
  // Базовые случаи
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  // Рекурсивный случай
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

Анализ решения:

✅ Простая и понятная реализация, соответствующая математическому определению

✅ Легко доказать корректность по индукции

❌ Экспоненциальная временная сложность O(2^n)

❌ Многократный пересчет одних и тех же значений (например, F(n-2) вычисляется для F(n) и для F(n-1))

Решение 2: Динамическое программирование (восходящий подход) 📈

function fibonacciDP(n) {
  // Обработка базовых случаев
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  // Создаем массив для хранения чисел Фибоначчи
  const fib = Array(n + 1);
  fib[0] = 0;
  fib[1] = 1;
  
  // Заполняем массив снизу вверх
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  
  return fib[n];
}

Характеристики:

✅ Линейная временная сложность O(n)

✅ Избегает повторных вычислений

✅ Простая итеративная структура

❌ Требует O(n) дополнительной памяти

Решение 3: Оптимизация по памяти 🚀

function fibonacciOptimized(n) {
  // Обработка базовых случаев
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  // Храним только два последних числа
  let a = 0;
  let b = 1;
  let temp;
  
  // Вычисляем следующее число на основе двух предыдущих
  for (let i = 2; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }
  
  return b;
}

Преимущества и недостатки:

✅ Линейная временная сложность O(n)

✅ Постоянная пространственная сложность O(1)

✅ Очень эффективное использование памяти

❌ Не сохраняет промежуточные результаты для повторного использования

Решение 4: Матричный метод (быстрое возведение в степень) 🔧

function fibonacciMatrix(n) {
  // Базовые случаи
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  // Матрица перехода
  let F = [
    [1, 1],
    [1, 0]
  ];
  
  // Возводим матрицу в степень (n-1)
  F = matrixPower(F, n - 1);
  
  // F(n) = F[0][0]
  return F[0][0];
}

function matrixPower(matrix, n) {
  // Вспомогательная функция для возведения матрицы в степень
  if (n === 1) {
    return matrix;
  }
  
  if (n % 2 === 0) {
    // Если степень четная, вычисляем матрицу^(n/2) и умножаем на саму себя
    const halfPower = matrixPower(matrix, n / 2);
    return matrixMultiply(halfPower, halfPower);
  } else {
    // Если степень нечетная, вычисляем матрицу^(n-1) и умножаем на исходную матрицу
    return matrixMultiply(matrix, matrixPower(matrix, n - 1));
  }
}

function matrixMultiply(A, B) {
  // Умножение матриц 2x2
  const C = [
    [0, 0],
    [0, 0]
  ];
  
  for (let i = 0; i < 2; i++) {
    for (let j = 0; j < 2; j++) {
      for (let k = 0; k < 2; k++) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  
  return C;
}

Особенности:

✅ Логарифмическая временная сложность O(log n)

✅ Наиболее эффективный алгоритм для больших значений n

✅ Использует свойства матриц и быстрое возведение в степень

❌ Более сложная реализация по сравнению с другими методами

Решение 5: Формула Бине (аналитическое решение) 📐

function fibonacciBinet(n) {
  // Золотое сечение
  const phi = (1 + Math.sqrt(5)) / 2;
  
  // Формула Бине
  return Math.round((Math.pow(phi, n) - Math.pow(-phi, -n)) / Math.sqrt(5));
}

Анализ решения:

✅ Константная временная сложность O(1)

✅ Очень эффективно для быстрого вычисления

❌ Подвержено ошибкам округления для больших n из-за ограничений чисел с плавающей точкой

❌ Не подходит для очень больших значений n (> 70) без использования библиотек для работы с большими числами

Рекурсия с мемоизацией (нисходящее ДП) 🚀

function fibonacciMemoization(n, memo = {}) {
  // Проверяем, вычисляли ли мы уже это число
  if (n in memo) {
    return memo[n];
  }
  
  // Базовые случаи
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  // Рекурсивный случай с мемоизацией
  memo[n] = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
  return memo[n];
}

Характеристики:

✅ Линейная временная сложность O(n) благодаря мемоизации

✅ Сохраняет элегантность рекурсивного подхода

✅ Избегает повторных вычислений с помощью кеширования

❌ Использует дополнительную память O(n) для хранения промежуточных результатов

❌ Может вызвать переполнение стека для очень больших n

Интуиция за алгоритмами Фибоначчи

Ключевая идея оптимизации алгоритмов для вычисления чисел Фибоначчи заключается в устранении повторных вычислений:

1. Наивная рекурсия создает дерево вызовов с экспоненциальным ростом

2. Динамическое программирование сохраняет результаты подзадач, что сокращает время до O(n)

3. Матричный метод использует математическое свойство:

   [F(n+1), F(n)]   = [1, 1] × [F(n), F(n-1)]
   [F(n), F(n-1)]     [1, 0]
   

   Это позволяет использовать быстрое возведение в степень для достижения сложности O(log n)

4. Формула Бине предоставляет аналитическое решение, но подвержена ошибкам округления

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Для n < 40, простая итеративная реализация с O(1) памятью является оптимальной
   • 📝 Для 40 < n < 10^6, матричный метод с быстрым возведением в степень более эффективен
   • 🧮 Для n > 10^6, требуются специальные библиотеки для работы с большими числами

2. Важные моменты:

   • 📝 Числа Фибоначчи растут экспоненциально, поэтому быстро достигают границ стандартных типов чисел
   • 🔄 При работе с большими числами используйте библиотеки для работы с большими целыми числами
   • 📊 Избегайте наивной рекурсии для любых практических применений

Распространённые ошибки

1. 🤦‍♂️ Использование наивной рекурсии без мемоизации
2. 😅 Некорректная обработка базовых случаев (F(0) и F(1))
3. 🐛 Переполнение для больших значений n при использовании стандартных числовых типов
4. 😕 Некорректное округление при использовании формулы Бине

Математические свойства и закономерности

Отношение последовательных чисел Фибоначчи

Отношение соседних чисел Фибоначчи F(n+1)/F(n) с ростом n стремится к золотому сечению:

function goldenRatioApproximation(maxN) {
  let a = 0;
  let b = 1;
  let temp;
  
  for (let i = 2; i <= maxN; i++) {
    temp = a + b;
    a = b;
    b = temp;
    
    console.log(`F(${i})/F(${i-1}) = ${b/a} ~ ${(1 + Math.sqrt(5)) / 2}`);
  }
}

Связь с последовательностью Люка

Последовательность Люка (L) тесно связана с Фибоначчи:

• L(0) = 2
• L(1) = 1
• L(n) = L(n-1) + L(n-2) для n > 1

Существуют интересные соотношения между этими последовательностями:

function fibonacciLucasRelations(n) {
  // Вычисляем числа Фибоначчи до n
  const fib = [0, 1];
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i-1] + fib[i-2];
  }
  
  // Вычисляем числа Люка до n
  const luc = [2, 1];
  for (let i = 2; i <= n; i++) {
    luc[i] = luc[i-1] + luc[i-2];
  }
  
  // Проверяем некоторые соотношения
  console.log(`L(n) = F(n-1) + F(n+1): ${luc[n] === fib[n-1] + fib[n+1]}`);
  console.log(`F(2n) = F(n) * L(n): ${fib[2*n] === fib[n] * luc[n]}`);
  
  return { fibonacci: fib, lucas: luc };
}

Формула суммы

Сумма первых n чисел Фибоначчи имеет интересное свойство:

function fibonacciSum(n) {
  // Вычисляем числа Фибоначчи до n
  const fib = [0, 1];
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i-1] + fib[i-2];
  }
  
  // Вычисляем сумму
  const sum = fib.reduce((a, b) => a + b, 0);
  
  // Проверяем формулу: сумма = F(n+2) - 1
  console.log(`Sum = ${sum}, F(${n+2}) - 1 = ${fib[n+2] - 1}`);
  console.log(`Formula correct: ${sum === fib[n+2] - 1}`);
  
  return sum;
}

Визуализация роста чисел Фибоначчи

Числа Фибоначчи растут экспоненциально, что можно наглядно продемонстрировать:

n  | F(n)     | log10(F(n))
---|-----------|-----------
0  | 0        | -
1  | 1        | 0
5  | 5        | 0.699
10 | 55       | 1.740
15 | 610      | 2.785
20 | 6,765    | 3.830
25 | 75,025   | 4.875
30 | 832,040  | 5.920
40 | 102,334,155 | 8.010
50 | 12,586,269,025 | 10.100

График логарифма числа Фибоначчи почти линеен, что подтверждает экспоненциальный рост.

Оптимизации и особые случаи

Вычисление больших чисел Фибоначчи

Для работы с очень большими числами можно использовать библиотеки работы с большими числами:

// Использование библиотеки BigInt в JavaScript
function fibonacciBigInt(n) {
  if (n === 0) return BigInt(0);
  if (n === 1) return BigInt(1);
  
  let a = BigInt(0);
  let b = BigInt(1);
  let temp;
  
  for (let i = 2; i <= n; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }
  
  return b;
}

Нахождение остатков от деления на m

Задача нахождения F(n) mod m имеет важное свойство — периодичность (период Пизано):

function fibonacciModulo(n, m) {
  // Находим период Пизано (цикл остатков)
  const pisanoPeriod = findPisanoPeriod(m);
  
  // Используем свойство периодичности
  const remainder = n % pisanoPeriod;
  
  // Вычисляем F(remainder) mod m
  let a = 0;
  let b = 1;
  let temp;
  
  if (remainder === 0) return 0;
  if (remainder === 1) return 1;
  
  for (let i = 2; i <= remainder; i++) {
    temp = (a + b) % m;
    a = b;
    b = temp;
  }
  
  return b;
}

function findPisanoPeriod(m) {
  let a = 0;
  let b = 1;
  let period = 0;
  
  do {
    const temp = (a + b) % m;
    a = b;
    b = temp;
    period++;
  } while (!(a === 0 && b === 1) && period < m * m);
  
  return period;
}

Вычисление F(n) по модулю с использованием матричного метода

function fibonacciMatrixModulo(n, m) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  // Матрица перехода
  let F = [
    [1, 1],
    [1, 0]
  ];
  
  // Возводим матрицу в степень (n-1) по модулю m
  F = matrixPowerModulo(F, n - 1, m);
  
  // F(n) mod m = F[0][0]
  return F[0][0];
}

function matrixPowerModulo(matrix, n, m) {
  if (n === 1) {
    return matrixModulo(matrix, m);
  }
  
  if (n % 2 === 0) {
    const halfPower = matrixPowerModulo(matrix, n / 2, m);
    return matrixMultiplyModulo(halfPower, halfPower, m);
  } else {
    const power = matrixPowerModulo(matrix, n - 1, m);
    return matrixMultiplyModulo(matrix, power, m);
  }
}

function matrixMultiplyModulo(A, B, m) {
  const C = [
    [0, 0],
    [0, 0]
  ];
  
  for (let i = 0; i < 2; i++) {
    for (let j = 0; j < 2; j++) {
      for (let k = 0; k < 2; k++) {
        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % m;
      }
    }
  }
  
  return C;
}

function matrixModulo(matrix, m) {
  const result = [
    [matrix[0][0] % m, matrix[0][1] % m],
    [matrix[1][0] % m, matrix[1][1] % m]
  ];
  
  return result;
}

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

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

Число является числом Фибоначчи тогда и только тогда, когда 5n² + 4 или 5n² - 4 является идеальным квадратом:

function isFibonacciNumber(n) {
  const test1 = 5 * n * n + 4;
  const test2 = 5 * n * n - 4;
  
  const isPerfectSquare = (num) => {
    const sqrt = Math.sqrt(num);
    return Math.floor(sqrt) === sqrt;
  };
  
  return isPerfectSquare(test1) || isPerfectSquare(test2);
}

Генерация чисел Фибоначчи с использованием генераторов

function* fibonacciGenerator() {
  let a = 0;
  let b = 1;
  
  yield a;
  yield b;
  
  while (true) {
    const temp = a + b;
    yield temp;
    a = b;
    b = temp;
  }
}

// Использование
function generateNFibonacciNumbers(n) {
  const generator = fibonacciGenerator();
  const numbers = [];
  
  for (let i = 0; i < n; i++) {
    numbers.push(generator.next().value);
  }
  
  return numbers;
}

Последовательность Фибоначчи в природе и искусстве

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

• 🌱 В расположении листьев и ветвей растений (филлотаксис)
• 🐚 В спиралевидных структурах раковин и рогов
• 🌼 В расположении семян в цветах (например, в подсолнухе)

Золотой прямоугольник, основанный на отношении Фибоначчи, часто встречается в искусстве и архитектуре:

function drawGoldenRectangle(ctx, x, y, width) {
  const height = width / ((1 + Math.sqrt(5)) / 2);
  
  // Рисуем прямоугольник
  ctx.strokeRect(x, y, width, height);
  
  // Рисуем спираль Фибоначчи
  drawFibonacciSpiral(ctx, x, y, width, height, 10);
}

function drawFibonacciSpiral(ctx, x, y, width, height, iterations) {
  // Код для рисования спирали Фибоначчи внутри золотого прямоугольника
  // ...
}

Заключение

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

• 🧮 Выбор алгоритма критически важен и зависит от размера входных данных
• 🔄 Динамическое программирование и матричный метод предоставляют эффективные решения для большинства практических задач
• 📊 Числа Фибоначчи быстро растут, поэтому для больших индексов требуются специальные подходы
• 🧠 Использование математических свойств (формула Бине, периодичность остатков) может значительно ускорить вычисления
• 🌱 Последовательность имеет многочисленные связи с природными явлениями и предметами искусства

Последовательность Фибоначчи служит превосходным примером того, как простое математическое определение может привести к богатому набору свойств, алгоритмов и приложений. От элементарных рекурсивных вычислений до сложных оптимизаций, эта задача демонстрирует множество фундаментальных концепций в алгоритмике и математике. 🌟