我正在嘗試解決一個(gè)問(wèn)題，該問(wèn)題需要我計(jì)算高達(dá) 10^18 mod 10^9+7 的斐波那契數(shù)。在線法官說(shuō)我在小案例中得到了正確的答案（不需要模數(shù)），但在較大的案例中我得到了錯(cuò)誤的答案。否則算法沒(méi)有問(wèn)題，但是將結(jié)果保存到字典中的記憶化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 回答
夢(mèng)里花落0921
TA貢獻(xiàn)1772條經(jīng)驗(yàn) 獲得超6個(gè)贊
背誦沒(méi)什么不好。
可能令您驚訝的是，問(wèn)題在于浮點(diǎn)精度（是的，您的數(shù)字被截?cái)嗔耍?/p>
您應(yīng)該/用整數(shù)除法運(yùn)算符//（雙）替換浮動(dòng)除法運(yùn)算符（單斜杠）。
以下代碼，以及上面提到的唯一修復(fù)，對(duì)我有用：
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
添加回答
舉報(bào)
0/150
提交
取消