#include <stdio.h>
#include <string.h>

char f[3][2][400] = {{"0", "1"}, {"0", "1"}, 0};
char temp[400] = {0}, tmp[400] = {0};
int n;
int max(int a, int b)
{
    if (a > b) return a;
    else  return b;
}
void fix(char *s)
{
     int i, len = strlen(s);
     char t;
     for (i = 0; i < len/2; i++)
     {
         t = s[i];
         s[i] = s[len-1-i];
         s[len-1-i] = t;
     }
}
char *add(char *s1, char *s2)
{
     int i, c, len, len1 = strlen(s1), len2 = strlen(s2);
     fix(s1);
     fix(s2);
     len = max(len1, len2);
     for (i = len1; i < len; i++)      s1[i] = '0';
     for (i = len2; i < len; i++)      s2[i] = '0';
     memset(temp, 0, sizeof(temp));
     for (c = i = 0; i < len; i++)
     {
         c += ((s1[i]-'0')+(s2[i]-'0'));
         temp[i] = (char)(c%10+'0');
         c /= 10;
     }
     if (c > 0)  temp[len++] = (char)(c+'0');
     fix(temp);
     fix(s1);
     fix(s2);
     return temp;
}

int main()
{
    int i;
    while (scanf("%d", &n) != EOF)
    {
          memset(f, 0, sizeof(f));
          f[0][0][0] = f[1][0][0] = f[2][0][0] = '0';
          f[0][1][0] = f[1][1][0] = f[2][1][0] = '1';
          for (i = 2; i <= n; i++)
          {
              strcpy(f[2][0], add(f[0][0], f[0][1]));
              strcpy(f[2][1], add(f[1][1], strcpy(tmp, f[1][1])));
              strcpy(f[0][0], f[1][0]);
              strcpy(f[0][1], f[1][1]);
              strcpy(f[1][0], f[2][0]);
              strcpy(f[1][1], f[2][1]);
          }
          printf("%s\n", f[2][0]);
    }
    //system("pause");
    return 0;
}

试了N次，老是超时！我的递推公式是：  f[n]双0的对数 = (f[n-2]双0的对数） ＋ （f[n-2]中1的个数）

• Re:求助！ 2680 Computer Transformation 超时呀！ (3027) Silgon 2009-02-08 13:14:01