首页 > 代码库 > UVa12050

UVa12050

12050 Palindrome Numbers
A palindrome is a word, number, or phrase that reads the same forwards as backwards. For example,
the name “anna” is a palindrome. Numbers can also be palindromes (e.g. 151 or 753357). Additionally
numbers can of course be ordered in size. The first few palindrome numbers are: 1, 2, 3, 4, 5, 6, 7, 8,
9, 11, 22, 33, ...
The number 10 is not a palindrome (even though you could write it as 010) but a zero as leading
digit is not allowed.
Input
The input consists of a series of lines with each line containing one integer value i (1  i  2  109).
This integer value i indicates the index of the palindrome number that is to be written to the output,
where index 1 stands for the first palindrome number (1), index 2 stands for the second palindrome
number (2) and so on. The input is terminated by a line containing ‘0’.
Output
For each line of input (except the last one) exactly one line of output containing a single (decimal)
integer value is to be produced. For each input value i the i-th palindrome number is to be written to
the output.
Sample Input
1
12
24
0
Sample Output
1
33
151

题意:

       将回文数从小到大依次排列,输入一个正整数n,需要输出第n小的回文数。

分析:

       开一个数组存储长度为i的回文数一共有几个,这样就可以根据输入的n先确定要输出的回文数的长度len,并确定第n小的回文数是长度为len的回文数中的第几个,然后依次求出每一位的数即可得到最终的答案。

技术分享
 1 #include <cstdio> 2 #define MAX_BIT 20 3 // ans数组记录答案,下标从1开始 4 int bit_num[MAX_BIT + 2],n,ans[MAX_BIT + 2]; 5 void set_bitnum(){ 6     bit_num[0] = 0; 7     bit_num[1] = bit_num[2] = 9; 8     for(int i = 3 ; i <= MAX_BIT ; i += 2) 9         bit_num[i] = bit_num[i + 1] = 10 * bit_num[i - 1];10 }11 int calc_bit(int& n){12     int bitnum = 0;13     while(n > bit_num[bitnum])14         n -= bit_num[bitnum],bitnum++;15     return bitnum;16 }17 int main(){18     set_bitnum();19     while(scanf("%d",&n) == 1 && n){20         int len = calc_bit(n);21         //printf("len: %d\n",len);22         int index = len / 2 + 1;23         n = n - 1; // 需要从零开始排列24         while(n)25             ans[index++] = n % 10,n /= 10;26         for(int i = index ; i <= len ; i++)27             ans[i] = 0;28         ans[len] += 1;29         for(int i = 1 ; i <= len / 2 ; i++)30             ans[i] = ans[len - i + 1];31         for(int i = 1 ; i <= len ; i++)32             printf("%d",ans[i]);33         puts("");34     }35     return 0;36 }
View Code

 

UVa12050