Fibonacci Numbers 基于大数加法
发布时间:2020-12-14 04:10:50 所属栏目:大数据 来源:网络整理
导读:Problem description ??Fibonacci数列是一个典型的递归数列,F1 = F2 = 1;Fn = Fn-2 + Fn-1,当n=3时。 Input ??每一行一个整数,直到EOF。 Output ??每一行输出对应的Fibonacci数。本题的输出都不会超过1000位。 Sample Input 10020 Sample Output 3542248
? //AC的代码,VC++6.0通过 #include<iostream> #include<string> using namespace std; const int M=6000;//这道题坑爹的卡数据 string add(string st1,string st2) { string st; int a[1100]={0},b[1100]={0}; int len1,len2,len,i; len1=st1.length(); len2=st2.length(); for(i=len1-1;i>=0;i--) a[len1-1-i]=st1[i]-'0'; for(i=len2-1;i>=0;i--) b[len2-1-i]=st2[i]-'0'; len=(len1>len2)?len1:len2; for (i=0;i<len;i++) { a[i]=a[i]+b[i]; if (a[i]>=10) { a[i+1]+=a[i]/ 10; a[i]%=10; if (i==len-1) len++; } } st=""; for (i=0;i<len;i++) st+=a[len-1-i]+'0'; return st; } int main() { int n,i; string p[M]; p[0]="0"; p[1]="1"; for(i=2;i<4800;i++)//卡数据 p[i]=add(p[i-1],p[i-2]); while(cin>>n) { cout<<p[n]<<endl; } return 0; } ? 原文出处:http://hi.baidu.com/zch109/item/daf7a3a123328899141073df
HUNNU OJ 10509 ? 下面是超时的代码: ? #include<iostream> #include<string> using namespace std; const int M=1000; string p[M]; string sum(string s1,string s2) { if(s1.length()<s2.length()) { string temp=s1; s1=s2; s2=temp; } int i,j; for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--) { s1[i]=char(s1[i]+(j>=0? s2[j]-'0':0)); if(s1[i]-'0'>=10) { s1[i]=char((s1[i]-'0')%10+'0'); if(i) s1[i-1]++; else s1='1'+s1;//?求解释 } } return s1; } int main() { int n; while(cin>>n) { p[0]="0"; p[1]="1"; for(int i=2;i<=n;i++) p[i]=sum(p[i-1],p[i-2]); cout<<p[n]<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |