AltriaT 2021-03-26 23:47 采纳率: 100%
浏览 48
已采纳

我用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条回答 默认 最新

  • 对象被抛出 2021-03-27 11:41
    关注

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

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(3条)

报告相同问题?

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名