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

我用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条回答

      报告相同问题?

      相关推荐 更多相似问题

      悬赏问题

      • ¥15 Python中导入模块中的函数运行出错
      • ¥15 我一点思路没有 《用51单片机实现》 通俗易懂,如何解决?(语言-c语言)
      • ¥15 Halcon 曲线拟合时怎么过滤掉异常点
      • ¥15 edge浏览器最近莫名其妙老是每隔一段时间弹出色情网站,求解决。。
      • ¥15 “glmnet”运行出错
      • ¥30 如何用matlab表达以下公式?
      • ¥15 在arm架构芯片上基于32位linux操作系统做内存检查
      • ¥15 怎么样才能禁止VS自动调整Windows窗体布局
      • ¥15 mysql5.7.40安装到Initializing database报错,如何解决?
      • ¥30 如何降低hdfs中datanode的JVM内存用量