Tiling(递推，高精度)

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2067&cid=1158

#include<stdio.h>
#include<string.h>
#define max(a, b) (a>b?a:b)
struct node
{
    int len, a[1000] ;
}dp[251] ;
void add(node a, node b, node &c)
{
    int i ;
    int len = max(a.len, b.len) ;
    for(i=1; i<=len; i++)
    c.a[i] = a.a[i] + b.a[i] ;
    for(i=1; i<=len; i++)
    {
        if(c.a[i]>9)
        {
            c.a[i] -= 10 ;
            c.a[i+1]++ ;
        }
    }
    if(c.a[len+1]!=0)
    c.len = len + 1 ;
    else
    c.len = len ;
}
void mul(node &x)
{
    int i ;
    for (i=1;i<=x.len;i++)
    x.a[i]*=2;
    for (i=1;i<=x.len;i++)
    {
        if (x.a[i]>9)
        {
           x.a[i]-=10;
           x.a[i+1]++;
        }
    }
    if (x.a[x.len+1]!=0)
    x.len++;
}
int main()
{
    int i, n;
    while(scanf("%d", &n)!=EOF)
    {
          memset(dp,0,sizeof(dp));
          dp[0].len=1;
          dp[0].a[1]=1;
          dp[1].len=1;
          dp[1].a[1]=1;
          for (i=2;i<=n;i++)
          {
                mul(dp[i-2]);
                add(dp[i-2],dp[i-1],dp[i]);
          }
          for (i=dp[n].len;i>=1;i--)
          printf("%d",dp[n].a[i]);
          printf("\n");
    }
    return 0;
}

第一次做高精度的题