@keddad
Ученик

В чем ошибка в коде, который расчитывает период Пизано?

Дано: алгоритмическая задача. Необходимо найти модуль от деления n-ного числа Фибоначи на m. Задача решается вычислением периода Пизано и использованием его вместо модуля от исходного n-ного числа (т.к. n может быть очень большим). Я пришел к, как мне казалось, милому и простому решению:

vector<unsigned long long> cache = {0, 1};
vector<unsigned long long> seq = {0, 1};

unsigned long long fib(int n) {
    if (n >= cache.size()) {
        cache.push_back(fib(n-1) + fib(n-2));
    }
    return cache[n];
}

int main() {
    unsigned long long n, m;
    cin >> n >> m;

    for (int i = 2;; ++i) {
        seq.push_back(fib(i) % m);
        if(seq[i] == 1 && seq[i-1] == 0) {
            seq.pop_back();
            seq.pop_back();
            break;
        }
    }

    cout << seq[n % seq.size()];
}


Его можно оптимизировать по памяти, если не хранить seq, но это мелочь. Проблема в том, что это решение работает только для малых чисел. Так, при n=2015 и m=3, выводится 1 - это правильный ответ. Но на больших последовательностях (n=239, m=100) начинает получаться фигня. Я нашел решение этой задачи (ссылка) - идейно оно почти такое же, кроме упомянутой оптимизации. В чем может быть ошибка в моем коде?
  • Вопрос задан
  • 713 просмотров
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
У вас при вычислении cache числа не берутся по модулю. А значит очень быстро переполняют long long и случается фигня. Ведь цикл может начаться на очень больших числах. Вам надо всегда при вычислении брать по модулю m.

И, очевидная оптимизация - так как у вас fib() вызывается от увеличивающихся по порядку индексов, вы вместо функции делайте сразу же seq.push_back((seq[i-2]+seq[i-1]) % m);
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы