首页 > 代码库 > HDU 1250 大数加法

HDU 1250 大数加法

Hat‘s Fibonacci

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


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.
 
 
大数加法,简单。。。但是这道题给我的感觉是蛋疼。。。可能状态不行,脑残错误搞了1个多小时。
两个数组没初始化。。。然后题目范围没给出,我提交了一遍又一遍总是WA,害的我以为是我代码错误,题目范围从1000试到7100终于过了。。。
 
代码:
 1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <map> 5 #include <iostream> 6 #include <string> 7 using namespace std; 8  9 void add(char *s1,char *s2,char *a)10 {11     int n1=strlen(s1);12     int n2=strlen(s2);13     int c1[3000], c2[3000];14     int i, j, k=0, num;15     memset(c1,0,sizeof(c1));16     memset(c2,0,sizeof(c2));17     for(i=0;i<n1;i++)18     c1[i]=s1[n1-i-1]-0;19     for(i=0;i<n2;i++)20     c2[i]=s2[n2-i-1]-0;21     n1=max(n1,n2);22     for(i=0;i<=n1;i++)23     {24         num=c1[i]+c2[i]+k;25         if(num>=10)26         {27             num-=10;28             k=1;29         }30         else k=0;31         c1[i]=num;32     }33     34     k=n1+2;35     36     while(c1[k]==0)37     k--;38     for(i=0;i<=k;i++)39     a[i]=c1[k-i]+0;40     a[k+1]=\0;41 42 }43 44 char f[8000][2050];45 46 main()47 {48      char a[3000], b[3000];49      int i, j, k, n;50      for(i=1;i<=4;i++)51      strcpy(f[i],"1");52      for(i=5;i<7100;i++)53      {54           add(f[i-1],f[i-2],a);55           add(f[i-3],f[i-4],b);56           add(a,b,f[i]);57      }58   59     while(scanf("%d",&n)==1)60      {61          62          printf("%s\n",f[n]);63      }64 }