AltriaT
AltriaT
2021-03-26 23:47
采纳率: 50%
浏览 29

我用C++的map<int,vector>去计算斐波那契,卡在11808位算不了,难受。

这是一个题Fibonacci Again     

There are another kind of Fibonacci numbers: F(0) = 7, F(1) = 11, F(n) = F(n-1) + F(n-2) (n>=2).     Input consists of a sequence of lines, each containing an integer n. (n < 1,000,000).       Print the word "yes" if 3 divide evenly into F(n).   Print the word "no" if not.

鄙人知道有规律(n-2)%4==0就YES;但还是想用迭代做一下;

迭代函数到11808就算不了了(用二分凑出来的),查了查map,vector的容量也没超啊(学生党哭哭)

#include<bits/stdc++.h>
#define V vector<int>
using namespace std;
map<int,V> fi;
V add(V &A,V &B);
int num;
V Fibonacci(int n){
	if(n==0)return fi[0];//f(0)=7
	if(n==1)return fi[1];//f(1)=11
	if(fi[n].size()!=0)return fi[n];//存进map里
	//cout<<num++<<endl;
	 Fibonacci(n-1);//递归运算第一个
	 Fibonacci(n-2);//递归运算第二个

	return fi[n]=add(fi[n-1],fi[n-2]);//相加
}
int main(){
	fi[0].push_back(7);
	fi[1].push_back(11);
	Fibonacci(11807); //11808就不行
	//for(int i=0;i<10000;i++){
		 
		//for(int j=fi[11807].size()-1;j>=0;j--)cout<<fi[11807][j];
	//}
	int n;
	while(scanf("%d",&n)!=EOF){
		int sum=0;
		for(int i=fi[n].size()-1;i>=0;i--)sum+=fi[n][i];
		if(sum%3==0)printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
V add(V &A,V &B){//高进度A+B 
	V C;
	int t=0;
	for(int i=0;i<A.size()||i<B.size();i++){
		if(i<A.size())t+=A[i];
		if(i<B.size())t+=B[i];
		C.push_back(t%10);
		t/=10;
	}
	if(t)C.push_back(1);
	return C;
}
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • weixin_43848827
    对象被抛出 2021-03-27 11:41
    已采纳

    首先....你用递归去算这么大的工作量明显不现实, 非常耗时间, 这时候dp快很多

    其次....别说int, 我怀疑long long都不够用....建议写string大数模板....

    点赞 1 评论
  • qq_34124780
    爱晚乏客游 2021-03-27 01:10

    你知道11801是多大了吗?

    点赞 1 评论
  • cpp_learner
    cpp_learner 2021-03-27 11:40

    不知道,反正我用vs2017一运行就报错了。应该是数值计算太大了,超出范围了吧!

     

    点赞 1 评论
  • QA_Assistant
    有问必答小助手 2021-03-27 15:32

    您好,我是问答小助手,看到您的问题已被解答,欢迎您加入CSDN!

    目前问答VIP仅需29元,即可享受5次/月 有问必答服务,了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632

    点赞 评论

相关推荐