map似乎找到了不存在的元素
map似乎找到了不存在的元素
提问于 2018-06-05 03:03:23
所以我尝试创建一个简单的程序来计算第n个斐波那契数mod 10^9+7，使用带有F[0]=0和F[1]=1的doubling formula。这个程序似乎可以在我的电脑上使用编译器VS2010和CodeBlocks以及MinGW运行，但是在ideone上测试我的程序时，每次输入都会返回0。似乎在第一次迭代之后，F.find(n)实际上找到了不应该存在的元素。以下是我的代码(在VS2010中，我刚刚更改了包含)。
#include <bits/stdc++.h>
using namespace std;
std::map<unsigned long long,unsigned long long> F;
unsigned long long fib(unsigned long long n)
{
if(n==-1) return 0; // Shifting index by 1
if(n==0) return 1;
if(n==1) return 1;
if(F.find(n) != F.end()) return F[n]; // This seems to be the problem,
else
{
if(n%2==0) //
{
F[n/2-1] = fib(n/2-1)%1000000007;
F[n/2] = fib(n/2)%1000000007;
return F[n] = (F[n/2-1]*F[n/2-1]+F[n/2]*F[n/2])%1000000007;
}
else
{
F[n/2] = fib(n/2)%1000000007;
F[n/2+1] = fib(n/2+1)%1000000007;
return F[n] = (F[n/2]*(2*F[n/2+1]-F[n/2]))%1000000007;
}
}
}
int main() {
unsigned long long int broj;
cin >> broj; // input the number
cout << fib(broj-1) << endl;
return 0;
}回答 2
Stack Overflow用户
回答已采纳
发布于 2018-06-05 03:08:11
您对下面这样的表达式有疑问：
F[n/2-1] = fib(n/2-1)%1000000007;由于未定义std::map上operator[]的求值顺序，因此可能会在fib(n/2-1)之前调用它，并在其中创建一个空元素。您应该将缓存值存储在计算它的函数中。
另外，使用与std::map::find相同的key调用std::map::operator[]也是很浪费的。
可能的修复方法：
auto p = F.emplace( n, 0 );
if( p.second ) {
// element was not there
// calculate and store at p.first->second
}
return p.first->second;Stack Overflow用户
发布于 2018-06-05 04:02:26
另一个可能的解决方法是添加两个temp变量，比如unsigned long long a,b;，并更改行
F[n/2-1] = fib(n/2-1)%1000000007;
F[n/2] = fib(n/2)%1000000007;至
a = fib(n/2-1)%1000000007;
b = fib(n/2)%1000000007;
F[n/2-1] = a;
F[n/2] = b;这样，map是否创建元素然后赋值都无关紧要。它还可以优化以下行
return F[n] = (F[n/2-1]*F[n/2-1]+F[n/2]*F[n/2])%1000000007;要避免将Fn/2-1和Fn/2搜索到
return F[n] = (a*a+b*b)%1000000007;页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50687175
复制相关文章
相似问题