c++ - std::map 似乎找到了不存在的元素
问题描述
因此,我尝试创建一个简单的程序来计算第 n 个斐波那契数模,10^9+7
使用加倍公式和. 并且该程序似乎可以在我的计算机上使用编译器 VS2010 和带有 MinGW 的 CodeBlocks 但是在 ideone 上测试我的程序会为每个输入返回 0。似乎在第一次迭代之后 F.find(n) 实际上找到了不应该存在的元素。这是我的代码(在 VS2010 中我只是更改了包含)。F[0]=0
F[1]=1
#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;
}
解决方案
您对这样的表达式有疑问:
F[n/2-1] = fib(n/2-1)%1000000007;
由于未定义operator[]
on的评估顺序,它可能会在之前调用它并在那里创建一个空元素。您应该将缓存值存储在计算它的函数中。std::map
fib(n/2-1)
同样调用与您使用std::map::operator[]
的相同是浪费。key
std::map::find
可能的修复:
auto p = F.emplace( n, 0 );
if( p.second ) {
// element was not there
// calculate and store at p.first->second
}
return p.first->second;
推荐阅读
- javascript - 如何将数据从 Node 发送到另一台服务器
- powershell - 使用 powershell 在多台机器上远程运行安装文件 (.exe)
- json - 如何使用 volley 库在 android 中发出 JSONObject 的请求(类型:POST)?
- codeigniter-3 - 在 Codeigniter 中的 php 7.2 中出现错误“未定义的函数 mcrypt_create_iv()”
- javascript - 链接即使打开也没有激活
- python - 如何在清除子集总和时修复此错误?
- ios - AVPlayer/AVFoundation 播放指定 HLS 带宽和分辨率
- debugging - 如何在 sonarqube 中查找错误/漏洞的初始数量
- java - hashCode 方法在 equals 方法支持通配符的情况下
- java - 将序列化/json java 类迁移到新版本