A Fibonacci sequence is calculated by adding the previous two members the sequence,with the first two members being both 1. F(1) = 1,F(2) = 1,F(3) = 1,F(4) = 1,F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4) Your task is to take a number as input,and print that Fibonacci number.
Each line will contain an integers. Process to end of file.
For each case,output the result in a line.
4203968145672990846840663646?
Note: No generated Fibonacci number in excess of 2005 digits will be in the test data,ie. F(20) = 66526 has 5 digits.
?
代码：
#include <iostream>
#include<cstdio>
#include<cmath>
#include<string.h>
#define MAXI 7050
using namespace std;
void bigadd(char a[],char b[],char c[])
{
int i,j,la,lb,lc,flag=0,k=0;
char t;
i=strlen(a)-1;
j=strlen(b)-1;
while(i>=0&&j>=0)
{
t=a[i--]+b[j--]+flag-'0';
flag=(t-'0')/10;
t=t-flag*10;
c[k++]=t;
}
while(i>=0)
{
t=a[i--]+flag;
flag=(t-'0')/10;
t=t-flag*10;
c[k++]=t;
}
while(j>=0)
{
t=b[j--]+flag;
flag=(t-'0')/10;
t=t-flag*10;
c[k++]=t;
}
if(flag)
{c[k]=flag+'0'; c[k+1]=' ';}
else
{ k--;c[k+1]=' ';}
for(i=0,j=strlen(c)-1;i<j;i++,j--)
{
t=c[i];c[i]=c[j];c[j]=t;
}
}
char a[MAXI][2050],c[2050],d[2050];
int main()
{
int i,n;
strcpy(a[1],"1");
strcpy(a[2],"1");
strcpy(a[3],"1");
strcpy(a[4],"1");
for(i=5;i<MAXI;i++)
{
bigadd(a[i-1],a[i-2],c);
bigadd(c,a[i-3],d);
bigadd(d,a[i-4],a[i]);
}
while(~scanf("%d",&n))
{
printf("%sn",a[n]);}
return 0;
}
