std::map 似乎找到了不存在的元素

Question

所以我尝试创建一个简单的程序来计算第 n 个斐波那契数 mod 10^9+7 使用 doubling formula 与 F[0]=0 和 F[1]=1.并且该程序似乎可以在我的计算机上使用编译器 VS2010 和带有 MinGW 的 CodeBlocks 但是在 ideone returns 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;
}

Answer 1

您对这样的表达式有疑问：

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;

Answer 2

另一种可能的解决方法是添加两个临时变量让我们说 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;

为了避免将 F[n/2-1] 和 F[n/2] 搜索到

return F[n] = (a*a+b*b)%1000000007;

std::map 似乎找到了不存在的元素

std::map seems to find elements which are not there

c++

fibonacci