6/03/main.cpp - master - s-evg/cpps

6/03/main.cpp
61 строка2 KB
s-evg
fix: hw-6 fibonacci
23 апр 2026, 07:54
23 апр 2026, 07:545a1e808
// Числа Фибоначчи вычисляются по формуле:
// F(n) = F(n-1) + F(n-2)

#include <iostream>
#include <cstdint>


// чтобы не выйти за пределы int64_t (F(92) — последнее, что влезает)
const int MAX_FIB = 92;


// рекурсивная функция с мемоизацией
int64_t fibonacci(int n, int64_t memo[]) {
    // базовые случаи
    if (n == 0) return 0;
    if (n == 1) return 1;

    // если уже считали — берём из кэша
    if (memo[n] != -1) {
        return memo[n];
    }

    // считаем и сохраняем
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    std::cout << "F(" << n << ") = " << memo[n] << std::endl;
    return memo[n];
}


int main() {
    int count;
    std::cout << "Введите число: ";
    std::cin >> count;

    // защита от отрицательных чисел
    if (count < 0) {
        std::cout << "Отрицательные числа недопустимы!\nВведите положительное число." << std::endl;
        return 0;
    }

    // защита от выхода за границы массива
    if (count > MAX_FIB) {
        std::cout << "Будет ограничено до: " << MAX_FIB << std::endl;
        count = MAX_FIB;
    }

    // инициализация кэша: -1 означает «ещё не считали»
    // Добавляем единицу, так нам нужно именно число 92 с индексом 93
    int64_t memo[MAX_FIB + 1] = {0};
    for (int i = 0; i <= MAX_FIB; i++) {
        memo[i] = -1;
    }

    std::cout << "Числа Фибоначчи: ";
    for (int i = 0; i <= count; i++) {
        std::cout << fibonacci(i, memo) << " ";
    }
    std::cout << std::endl;

    return 0;
}