Проблемы с модулем при расчете фибоначчи - PullRequest
Новая
       64

Проблемы с модулем при расчете фибоначчи

0 голосов
/ 28 декабря 2018

Я пытаюсь решить проблему, которая требует, чтобы я вычислял числа Фибоначчи до 10 ^ 18 мод 10 ^ 9 + 7.Онлайн-судья говорит, что я получаю правильные ответы по маленьким случаям (где по модулю не требуется), но в более крупных случаях я получаю неправильные ответы.

В противном случае нет проблем с алгоритмом, ноЗапоминание, или сохранение результатов в словаре table, похоже, не удалось.Я понятия не имею, почему. 

luku = int(input())
table = {0:0, 1:1, 2:1}

def fib(num):

    if num in table:
        return table[num];

    if num % 2 == 0:
        puoli = num / 2;
        ans = (fib(puoli) * (2 * (fib(puoli + 1)) - fib(puoli))) % 1000000007;
        table[num] = ans;
        return ans;
    else:
        puoli = (num-1) / 2;
        ans = (fib(puoli + 1)*fib(puoli + 1) + fib(puoli)*fib(puoli)) % 1000000007;
        table[num] = ans;
        return ans;


print(fib(luku))

Например, с вводом 54774730983471038 я получаю 946469205 вместо правильного ответа 795317107.

1 Ответ

0 голосов
/ 28 декабря 2018

Ничего плохого в запоминании.

Возможно, к вашему удивлению, проблема в том, что точность с плавающей запятой (да, ваши числа усекаются).

Вы должны заменитьОператор с плавающим делением / (одиночная косая черта) с оператором целочисленного деления // (double).

У меня работает следующий код, с единственным исправлением, упомянутым выше: 

luku = int(input())
table = {0:0, 1:1, 2:1}

def fib(num):
    if num in table:
        return table[num];

    if num % 2 == 0:
        puoli = num // 2;
        ans = (fib(puoli) * (2 * (fib(puoli + 1)) - fib(puoli))) % 1000000007;
        table[num] = ans;
        return ans;
    else:
        puoli = (num-1) // 2;
        ans = (fib(puoli + 1)*fib(puoli + 1) + fib(puoli)*fib(puoli)) % 1000000007;
        table[num] = ans;
        return ans;


print(fib(luku))

См .: 

ibug@ubuntu:~ $ python3 t.py
54774730983471038
795317107
...