Hat's Fibonacci

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5800 Accepted Submission(s): 1926

Problem Description

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.

Input

Each line will contain an integers. Process to end of file.

Output

For each case, output the result in a line.

Sample Input

100

Sample Output

4203968145672990846840663646 Note: No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.

Author

戴帽子的

Recommend

Ignatius.L

http://acm.hdu.edu.cn/showproblem.php?pid=1250

大数题，我先是用打表的方法，发现数字到达7037的时候，数字规模才能达到2005 ...然后用7037*2005 ---->已经超过内存，所以这条路实不可取的。。。唯一的方法，只好暴力法，但又担心会超时，可是，喜感就是，竟然过了，还应458ms。。。。哎!！！。

贴下代码：

   #include<stdio.h>

   #include<string.h>

   #define maxn 2006

   int a[maxn],b[maxn],c[maxn],d[maxn],ans[maxn];

   int main()

   {

       int i,j,e,s,up,num;

       while(scanf("%d",&num)!=EOF)

       {

           if(num<=)

           printf("");

          else

          {

          memset(a,,sizeof a);

          memset(b,,sizeof b);

          memset(c,,sizeof c);

          memset(d,,sizeof d);

          memset(ans,,sizeof ans);

          a[]=b[]=c[]=d[]=;

       for(i=,up=;i<num;i++)

       {

          for(j=,e=;j<=up;j++)

          {

             s=a[j]+b[j]+c[j]+d[j]+e;

             ans[j]=s%;

             e=(s-ans[j])/;

             if(s>&&j==up) up++;

             a[j]=b[j];

             b[j]=c[j];

             c[j]=d[j];

             d[j]=ans[j];

          }

       }

          for(j=maxn;ans[j]==;j--);

          for(i=j;i>=;i--)

          {

           printf("%d",ans[i]);

          }

       }

          printf("\n");

      }

  return ;

  }

巴特西

HDUOJ----1250 Hat's Fibonacci

Hat's Fibonacci

最新文章

热门文章