// 本程序可以求出第n（n<=10^500000000）个回文数

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

template <class T>
void Swap(T &a, T &b)
{
    T  temp;
    temp = a;
    a = b;
    b = temp;
}

void Palindrome(char *n, char *result)
{
    long n_len;

    n_len = strlen(n);

    if(n_len == 1)
    {
        result[0] = n[0] + '0';
        result[1] = '\0';
        return;
    }
 
     long  i, j;

     for(i=0; i<n_len/2; ++i)
    {
        n[i] -= '0';
        n[n_len-i-1] -= '0';
        Swap(n[i], n[n_len-i-1]);
    }
    if(n[i] >= '0')
        n[i] -= '0';

    long  m_len = n_len - 2;
    char  carry = 0;
    for(i=0; i<m_len; ++i)
    {
        n[i] -= 9 + carry;
        if(n[i] < 0)
        {
            n[i] += 10;
            carry = 1;
        }
        else
            carry = 0;
     }
     if(carry > 0)
     {
          for(i=m_len; i<n_len; ++i)
          {
              n[i] -= carry;
              if(n[i] < 0)
              {
                  n[i] += 10;
                  carry = 1;
             }
             else
                  break;
          }
  
          for(i=n_len-1; i>=0; --i)
         {
             if(n[i] == 0)
                  --n_len;
             else
                  break;
         }
     }
 
      if(n_len > m_len+1)
     {
          carry = 9;
          for(i=m_len; i<n_len; ++i)
          {
              n[i] -= carry;
              if(n[i] < 0)
             {
                    n[i] += 10;
                    carry = 1;
             }
             else 
                    break;
          }
  
          ++m_len;
  
          for(i=n_len-1; i>=0; --i)
          {
              if(n[i] == 0)
                  --n_len;
              else
                  break;
          }
     }
 
      j = 0;
      for(i=n_len-1; i>=(n_len>m_len?1:0); --i)
           result[j++] = n[i] + '0';
      for(i=0; i<n_len; ++i)
           result[j++] = n[i] + '0';
 
       result[j] = '\0';
}

int main()
{
     int   len;
     char  *n, *result;

     FILE *fp;

     fp = fopen("test.txt", "rt");
     fseek(fp, 0, SEEK_END);
     len = ftell(fp);
     rewind(fp);
 
     n = (char*)malloc(sizeof(char)*(len+2));
     assert(n);
     result = (char*)malloc(sizeof(char)*(len*2+1));
     assert(result);

     fread(n, sizeof(char), len, fp);
     n[len] = '\0';
     fclose(fp);

     Palindrome(n, result);

     printf("Result is:\n%s\n", result);

     free(n);
     free(result);

     getch();
     return 0;
}

评论