Ответ
Числа Фибоначчи — это классическая целочисленная последовательность, где каждое последующее число равно сумме двух предыдущих. Стандартное определение начинается с F₀ = 0 и F₁ = 1:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Формула: Fₙ = Fₙ₋₁ + Fₙ₋₂, где n ≥ 2.
Сравнение подходов к вычислению на PHP:
-
Наивная рекурсия (неэффективно, O(2ⁿ)):
function fibRecursive(int $n): int { if ($n <= 1) return $n; return fibRecursive($n - 1) + fibRecursive($n - 2); } // Не подходит для n > 40 из-за экспоненциального времени. -
Итеративный метод (оптимально по памяти, O(n)):
function fibIterative(int $n): int { if ($n <= 1) return $n; $prev = 0; // F₀ $curr = 1; // F₁ for ($i = 2; $i <= $n; $i++) { $next = $prev + $curr; $prev = $curr; $curr = $next; } return $curr; } echo fibIterative(10); // 55 -
Рекурсия с мемоизацией (O(n)):
function fibMemo(int $n, array &$memo = []): int { if ($n <= 1) return $n; if (!isset($memo[$n])) { $memo[$n] = fibMemo($n - 1, $memo) + fibMemo($n - 2, $memo); } return $memo[$n]; }
Практическое замечание: Для вычисления очень больших чисел Фибоначчи (например, F₁₀₀₀) необходимо использовать библиотеки для работы с большими числами, такие как bcmath или gmp в PHP, так как значения быстро выходят за пределы стандартного целочисленного типа.
Ответ 18+ 🔞
Смотри, вот тебе история про числа Фибоначчи, которые все на собесах спрашивают, а потом нихуя не используют. Это такая последовательность, где каждое следующее число — это сумма двух предыдущих. Начинается с нуля и единицы: 0, 1, 1, 2, 3, 5, 8, 13... Ну ты понял, ёпта.
Формула проще некуда: Fₙ = Fₙ₋₁ + Fₙ₋₂. Вот и вся магия.
А теперь самое интересное — как это на PHP посчитать, чтобы не накрыться медным тазом по производительности.
Первый способ — наивная рекурсия. Это классический пример, как делать НЕ НАДО, если не хочешь, чтобы твой скрипт ебался как конь до второго пришествия. Сложность тут — овердохуища, O(2ⁿ).
function fibRecursive(int $n): int {
if ($n <= 1) return $n;
return fibRecursive($n - 1) + fibRecursive($n - 2);
}
// Для n > 40 уже пиздец как долго. Доверия к такому коду — ебать ноль.Второй способ — итеративный. Вот это уже дело. Работает за O(n), памяти жрёт фиксированно, красота. Самый нормальный вариант в 95% случаев.
function fibIterative(int $n): int {
if ($n <= 1) return $n;
$prev = 0; // F₀
$curr = 1; // F₁
for ($i = 2; $i <= $n; $i++) {
$next = $prev + $curr;
$prev = $curr;
$curr = $next;
}
return $curr;
}
echo fibIterative(10); // 55Третий способ — рекурсия, но с мемоизацией. Тоже умный подход, если очень хочется рекурсию. Результаты запоминаем, чтобы не пересчитывать одно и то же по сто раз. Сложность тоже O(n).
function fibMemo(int $n, array &$memo = []): int {
if ($n <= 1) return $n;
if (!isset($memo[$n])) {
$memo[$n] = fibMemo($n - 1, $memo) + fibMemo($n - 2, $memo);
}
return $memo[$n];
}И главное практическое замечание, чувак.
Если ты вдруг решишь посчитать, например, F₁₀₀₀, то сам от себя охуеешь, потому что число будет просто нереальных размеров. Стандартные целочисленные типы в PHP с таким пизда рулю. Тут надо использовать специальные библиотеки для больших чисел, типа bcmath или gmp, иначе получишь не то, что ожидал. Вот такая, блядь, хитрая жопа у этих, казалось бы, простых чисел.
