计算斐波那契时模数的问题

Question

我正在尝试解决一个问题，该问题需要我计算最大为 10^18 mod 10^9+7 的斐波那契数列。在线法官说我在小案件中得到正确答案（不需要 modulo），但在大案件中我得到错误答案。

算法在其他方面没有问题，但记忆化也就是将结果保存到字典中 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。

Answer 1

背诵没问题

可能出乎您的意料，问题是浮点精度（是的，您的数字被截断了）。

您应该将浮点除法运算符 /（单斜杠）替换为整数除法运算符 //（双斜杠）。

下面的代码，加上上面提到的唯一修复，对我有用：

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

计算斐波那契时模数的问题

Problems with modulo when calculating fibonacci

python

python-3.x

fibonacci

modulo