3076. 斐波那契数列

标准的大数运算题，附C代码

#include <stdio.h>
int main(void)
{
    int T;
    scanf("%d",&T);
    int i, j, fib[121][27], n;
    for(i=0; i<121; i++) for(j=0; j<27; j++) fib[i][j]=0;
    fib[1][0]=1;
    for(i=2; i<121; i++)
        for(j=0; j<26; j++)
        {
            fib[i][j]+=(fib[i-1][j]+fib[i-2][j]);
            fib[i][j+1]=fib[i][j]/10;
            fib[i][j]%=10;
        }
        for(i=0; i<T; i++)
        {
            scanf("%d",&n);
            printf("case #%d:\n",i);
            for(j=26; j+1; j--)
                if(fib[n][j]) break;
            for(;j+1; j--)
                printf("%d",fib[n][j]);
            if(n==0) printf("0");
            printf("\n");
        }
    return 0;
}

高精度+高精度，封装的好一点，另外，可以先全部算好，要什么输出什么（离线计算）

include

using namespace std;
typedef vector BIG;
vector V;
int T;

BIG create(int aa)
{
BIG ret;
ret.push_back(aa);
while(ret[ret.size()-1]>=10)
{
int top=ret.size()-1;
ret.push_back(ret[top]/10);
ret[top]%=10;
}
return ret;
}
BIG operator+(const BIG& aa,const BIG& bb)
{
BIG ret;
for(int i=0;ibb.size())
for(int i=bb.size();i<aa.size();i++) ret.push_back(aa[i]);
else if(aa.size()<bb.size())
for(int i=aa.size();i=10) { int top=ret.size()-1; ret.push_back(ret[top]/10); ret[top]%=10; } return ret; } void print(const BIG& aa) { for(int i=aa.size()-1;i>=0;i–) cout<<aa[i];
cout<<endl;
return;
}
void init()
{
V.push_back(create(0));
V.push_back(create(1));
for(int i=2;i<=120;i++) V.push_back(V[V.size()-1]+V[V.size()-2]);
return;
}
void solve()
{
int n;
cin>>n;
print(V[n]);
return;
}
int main()
{
scanf(“%d”,&T);
init();
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

基本的大数题，做法很多，来个巨傻的字符串打法……

include

using namespace std;
int plu(char s1[],char s2[],char s3[],int l1,int l2)
{
int cnt=0;
int jin=0;

while(l1>=0&&l2>=0)
{
   int num=s1[l1]-'0'+s2[l2]-'0'+jin;
   jin=num/10;
   num=num%10;
   s3[cnt]=num+'0';
   cnt++;
   l1--,l2--;
}
while(l1>=0)
{
     int num=s1[l1]-'0'+jin;
   jin=num/10;
   num=num%10;
   s3[cnt]=num+'0';
   cnt++;
   l1--;
}
  while(l2>=0)
{
     int num=s2[l2]-'0'+jin;
   jin=num/10;
   num=num%10;
   s3[cnt]=num+'0';
   cnt++;
   l2--;
}
if(jin!=0) s3[cnt++]=jin+'0';

return cnt-1;

}
void solve()
{
char s1[50],s2[50],s3[50];
strcpy(s1,”0”);
strcpy(s2,”1”);
int l1=strlen(s1)-1,l2=strlen(s2)-1;
int l3;
int n;
cin>>n;
if(n==0) cout<<s1<<endl;
else if(n==1) cout<<s2<<endl;
else{
for(int i=2;i<=n;i++)
{l3=plu(s1,s2,s3,l1,l2);
for(int i1=0;i1<=l2;i1++) s1[i1]=s2[i1];
for(int i1=0;i1<=l3;i1++) s2[i1]=s3[l3-i1];
l1=l2;
l2=l3;
}
for(l3;l3>=0;l3–) cout<<s3[l3];
cout<>T;
for(int i=0;i<T;i++)
{
printf(“case #%d:\n”,i);
solve();
}
}

这么裸的大数+斐波那契，直接用python实现吧，使用记忆化搜索降低时间复杂度:

dp = [-1 for i in range(125)]
def F(n):
    if(n == 0): return 0
    if(n == 1 or n == 2): return 1
    if(dp[n] != -1): 
        return dp[n]
    else:
        dp[n] = F(n-1) + F(n-2)
        return dp[n]

T = int(input())
for i in range(T):
    n = int(input())
    print("case #%d:"%i)
    print(F(n))