回文数算法

大家好，欢迎来到IT知识分享网。

一、概念

一个正数如果顺着和反过来都是一样的（比如12321，反过来也是12321），那么就称为回文数。

注意：（1）回文数不能以0开头。

　　　（2）回文数从1开始。

二、初始想法

写一个循环算出逆序的值，判断原序和逆序是否相等。

这种思路可以算出正确结果，但是随着N的增大，效率太低。

三、回文数算法

发现回文数的个数的规律，如下：

1位回文数：9个

2位回文数：9个

3位回文数：90个

4位回文数：90个

5位回文数：900个

6位回文数：900个

…….

我们将数拆成两半看，比如[]拆成123来看，两半的变化是一样，所以算一半即可。

因为首位不能是0，所以左半最小为100，最大为999，共有999-100+1=900个，以此类推。

因此，总结规律如下：

（1）回文数的数位每增长2，回文数的个数为原来的10倍。如从个位回文数到百位回文数，个数从9变为90个。

（2）个位回文数的个数是9个，回文数是1,2,3,4,5…..,9

四、代码实现

（1）问题：给一个index，返回第index个回文数的值

（2）c++代码：

#include<iostream> using namespace std; int cal(int index){ //返回第index个回文数的值 int w=0; //存储这个回文数的数位 int count=0; //计算总的回文数的个数 int number=9; //存储当前位数的回文数的个数,如个位回文数为9 while(true){ if(w>0 && w%2==0){ //每进2位，个数*10 number *= 10; } w++; if(count+number>index){ //序号超出当前的回文数总数，跳出循环 break; } count += number; }//while index -= count; //转化为计算当前数位的第index个回文数 //算出回文数的一半，然后拼接就好 long h=1; //算出一半的基数 for(int i=0; i<(w-1)/2; i++){ //求回文数的左半边的基数，如回文数在万位上，则为100 h*=10; } long half = h+index; long res = half; if(w%2 != 0) //如果数位是奇数位，去掉最中间的那个数 { half/=10; } //拼接 while(half){ res=res*10+half%10; half/=10; } return res; } int main(){ int index; while(cin>>index){ cout<<cal(index)<<endl; } return 0; }