1250 hat's fibonacci.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

#include <cstdio>
#include <string>
using namespace std;
//2005位的树n大约为7100 
char num[7100][2010];
int len[7100];

inline void plusnum(int x,int y)
{
    int inc,i,mlen;
    
    inc=0;
    mlen=len[x] > len[y] ? len[x] : len[y];
    for(i=1;i<=mlen;i++)
    {
        num[x][i]+=num[y][i]+inc;
        inc=0;
        if(num[x][i]>=10)
        {    inc=1;num[x][i]-=10;}
    }
    if(inc!=0)
    {
        num[x][i++]=inc;
    }
    len[x]=i-1;
} 
int main()
{
    int i,j,n,max;
    
    num[1][1]=num[2][1]=num[3][1]=num[4][1]=1;
    len[1]=len[2]=len[3]=len[4]=1;
    max=4;
    while( scanf("%d",&n)!=EOF )
    {
        if(max<n)
		{
	        for(i=max+1;i<=n;i++)
	        {
	        	plusnum(i,i-1);
	        	plusnum(i,i-2);
	        	plusnum(i,i-3);
	        	plusnum(i,i-4);
	        }
	        max=n;
		}
		for(i=len[n];i>0;i--)
			printf("%d",num[n][i]);
    	printf("\n");
    	//printf("%d\n",len[n]);
    }
    return 0;
}