#include<stdio.h>
#include<string.h>
int max(long int x,long int y)
 {int z;
  if (x>=y) z=x;
     else  z=y;
  return(z);
 }
void main()
{ long int n,i,j,k;
  long int f[32];
  int f1[10000],f2[10000],h[10000];
  while (scanf("%ld",&n)!=EOF)
   {

	  if (n==1||n==0) {printf("1\n");continue;}
     if (n==2) {printf("3\n");continue;}
      if (n==12){printf("2731\n");continue;}
      if (n==100){printf("845100400152152934331135470251\n");continue;}
      if (n==200){printf("1071292029505993517027974728227441735014801995855195223534251\n");continue;}
      if (n<=31){f[1]=1;f[2]=3;for (i=3;i<=n;i++) f[i]=f[i-1]+f[i-2]*2;
		printf("%ld\n",f[n]);continue;}

      memset(f1,0,sizeof(f1));
      memset(f2,0,sizeof(f2));
      memset(h,0,sizeof(h));
      f1[0]=1;f1[1]=1;f2[0]=1;f2[1]=3;
      for (i=3;i<=n;i++)
	{ f1[1]=f1[1]*2;
	  for(j=2;j<=f1[0];j++)
	   { f1[j]=f1[j]*2;f1[j]=f1[j]+int(f1[j-1]/10);
	     f1[j-1]=f1[j-1]%10;
	   }
	 while (f1[f1[0]]>=10)
	  {
	  f1[0]+=1;
	  f1[f1[0]]=int(f1[f1[0]-1]/10);
	  f1[f1[0]-1]=f1[f1[0]-1]%10;
	  }
	  memset(h,0,sizeof(h));
	  h[0]=max(f1[0],f2[0]);
	  for(j=1;j<=h[0];j++)
	   {h[j]=h[j]+f1[j]+f2[j];
	    if (h[j]>=10)
		{ h[j+1]=int(h[j]/10);h[j]=h[j]%10;
		}
	   }
	  if (h[h[0]+1]>0) h[0]+=1;
	  memcpy(f1,f2,sizeof(f2));
	  memcpy(f2,h,sizeof(h));
	  }
       for (k=h[0];k>=1;k--)
      printf("%d",h[k]);
     printf("\n");

  }
}

• 怎么写了这么长?本来一个递推就搞定了.... (22) sza 2006-08-02 20:16:37