JuniorКодОчень частоЕщё не отвечали
Реализуйте подсчёт чисел Фибоначчи
Верните n-е число Фибоначчи, где fib(0) = 0, fib(1) = 1.
Требования:
переменными, а не наивная рекурсия O(2ⁿ).
- O(n) время и O(1) память — итерация снизу вверх с двумя скользящими
- Корректно задайте базовые случаи (
fib(0)=0,fib(1)=1,fib(2)=1). - Используйте
uint64_t;fib(93)— последнее значение, которое в него влезает.
uint64_t fib(int n) {
// ваш код здесь
}Допишите реализацию.
Наивная рекурсия — O(2ⁿ), катастрофически медленно. Итеративный подход снизу вверх использует две переменные и работает за O(n) времени и O(1) памяти. Мемоизация сверху вниз — тоже O(n), но O(n) памяти. Возведение матрицы в степень даёт O(log n).
- ✗Писать наивную рекурсию без мемоизации — fib(40) уже занимает секунды
- ✗Переполнение при больших n — явно используйте
uint64_tили__int128; fib(93) — последнее значение, умещающееся в uint64_t - ✗Ошибка на единицу в базовом случае: fib(0)=0, fib(1)=1, fib(2)=1
- →Как возведение матрицы в степень вычисляет Фибоначчи за O(log n)?
- →Как вычислить fib(n) mod M для очень большого n?
Оглавление
Задача
Реализуйте функцию вычисления n-го числа Фибоначчи тремя способами: наивная рекурсия, мемоизация, итеративный подход.
Решение
#include <vector>
#include <unordered_map>
#include <cstdint>
#include <cassert>
// 1. Наивная рекурсия — O(2^n) время, O(n) стека
uint64_t fibNaive(int n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// 2. Мемоизация (top-down DP) — O(n) время, O(n) память
uint64_t fibMemo(int n, std::unordered_map<int, uint64_t>& cache) {
if (n <= 1) return n;
auto it = cache.find(n);
if (it != cache.end()) return it->second;
return cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
}
// 3. Итеративный (bottom-up DP) — O(n) время, O(1) память ★
uint64_t fibIter(int n) {
if (n <= 1) return n;
uint64_t a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
uint64_t c = a + b;
a = b;
b = c;
}
return b;
}
int main() {
std::unordered_map<int, uint64_t> cache;
for (int i = 0; i <= 10; ++i) {
assert(fibIter(i) == fibMemo(i, cache));
}
// Known values
assert(fibIter(0) == 0);
assert(fibIter(1) == 1);
assert(fibIter(10) == 55);
assert(fibIter(20) == 6765);
// fib(93) is the largest value fitting in uint64_t
assert(fibIter(93) == 12200160415121876738ULL);
}Ключевые моменты
| Подход | Время | Память | Заметки |
|---|---|---|---|
| Наивная рекурсия | O(2ⁿ) | O(n) стека | Только для иллюстрации |
| Мемоизация | O(n) | O(n) | Понятна, но тратит память |
| Итеративный | O(n) | O(1) | Предпочтительный вариант |
fib(93)— последнее значение, умещающееся вuint64_t.- Для больших n используйте
fib(n) % Mс матричным возведением в степень.
Оглавление
