关于大数加法的解法

1.字符串结题（不会超内存，但是代码较长）

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <algorithm>
 5 #include <cmath>
 6 #include <string.h>
 7 #include <malloc.h>
 8 using namespace std;
 9 void add(char *a,char *b,char *c)
10 {
11     int i,j,k,t,lmax,lmin,tmp;
12     char *s,*pmax,*pmin;
13     lmax=strlen(a);
14     lmin=strlen(b);
15     if(lmax<lmin)
16     {
17         tmp=lmax;lmax=lmin;lmin=tmp;
18         pmax=b;pmin=a;
19     }
20     else
21     {
22         pmax=a;pmin=b;
23     }
24     s=(char*)malloc(sizeof(char)*(lmax+1));
25     s[0]='0';//注意此处很容易被忽略
26     for(i=lmax-1,j=lmin-1,k=lmax;j>=0;i--,j--,k--)
27         s[k]=pmax[i]-'0'+pmin[j];
28     for(;i>=0;i--,k--)
29     s[k]=pmax[i];
30     for(i=lmax;i>=0;i--)
31     if(s[i]>'9')
32     {
33         s[i]-=10;
34         s[i-1]++;
35     }
36     if(s[0]=='0')
37     {
38         for(i=0;i<=lmax;i++)
39         c[i-1]=s[i];
40         c[i-1]='';
41     }
42     else
43     {
44         for(i=0;i<=lmax;i++)
45         c[i]=s[i];
46         c[i]='';
47     }
48     free(s);
49 }
50 char dp[8001][2301];
51 int main(void)
52 {
53     for(int i=1;i<=4;i++)
54     strcpy(dp[i],"1");
55     for(int i=5;i<8000;i++)
56     {
57         char a[2301],b[2301];
58         add(dp[i-1],dp[i-2],a);
59         add(dp[i-3],dp[i-4],b);
60         add(a,b,dp[i]);
61     }
62     int n;
63     while(cin>>n)
64     {
65         cout<<dp[n]<<endl;
66     }
67     return 0;
68 }

View Code

2.int型数组（容易超内存，代码比较简便）

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19702

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 int dp[100][51];
 7 int main()
 8 {
 9     int len,a,b,c,k,t,sum;
10     while(cin>>a>>b>>c)
11     {
12         len=0;k=50;
13         memset(dp,0,sizeof(dp));
14         while(a)
15         {
16             dp[0][k--]=a%10;
17             a/=10;
18         }
19         if(len<50-k)
20         len=50-k;
21         k=50;
22         while(b)
23         {
24             dp[1][k--]=b%10;
25             b/=10;
26         }
27         if(len<50-k)
28         len=50-k;
29         k=50;
30         while(c)
31         {
32             dp[2][k--]=c%10;
33             c/=10;
34         }
35         if(len<50-k)
36         len=50-k;
37         for(int i=3;i<100;i++)
38         {
39             sum=0;
40             for(int k=50;k>50-len;k--)
41             {
42                 sum=sum+dp[i-1][k]+dp[i-2][k]+dp[i-3][k];
43                 dp[i][k]=sum%10;
44                 sum/=10;
45                 while(k==50-len+1&&sum>0)
46                 {
47                     dp[i][50-len]=sum;
48                     len++;
49                     break;
50                 }
51             }
52         }
53         for(t=0;t<50;t++)
54         if(dp[99][t]!=0)
55         break;
56         for(;t<=50;t++)
57         cout<<dp[99][t];
58         cout<<endl;
59     }
60     return 0;
61 }

View Code