求回文数算法

时间:2021-07-29 10:57:07

问题:

    求第N个回文数palindrome。

    一个正数如果顺着和反过来都是一样的(如13431,反过来也是13431),就称为回文数。约束:

    回文数不能以0开头

    回文数从1开始。

首先我们要写一个算法求回文数。刚开始我想到用用字符串来存储数,然后判断原序和逆序是否相等。

 

void func1(char a[])
{
printf(
"%d",strlen(a));

char *p=a;
char *q=a+strlen(a)-1;
bool flag=true;
while(q>p)
{
if(*q!=*p)
{
flag
=false;
break;
}
q
--;p++;
}
if(flag)
printf(
"%s 是回文数\n",a);
else
printf(
"%s 不是回文数\n",a);


}
int main()
{

char s[50];
while(scanf("%s",s)!=0)
{
printf(
"%d",strlen(s));
func1(s);

}

 

注意,用strlen的时候只检测什么时候到‘\0'位置,与sizeof无关,如果是sizeof的话char a[]做函数参数a会降级为指针

虽然这样做可以,但还是有点小问题,如果输入010,输出回文。不满足回文的定义。

回文数不能以0开头

  一开始就思考使用循环:从1开始,判断该数是否是回文数,然后用一

个计数器记下回文数,一直到计数器得到N,返回第N个回文数。比较常用的是以下这种方法来判断是

否回文数:

 

static boolean isPN(int num) {
int o = num;
int tmp = 0;
//使用循环把数字顺序反转
while(num != 0) {
tmp
*= 10;
tmp
+= num % 10;
num
/= 10;
}
//如果原始数与反转后的数相等则返回true
if(tmp == o)
return true;
return false;
}

 

这种思路的确可得到正确结果,但随着用来测试的N的增大,效率的问题就浮现了。因为是一重

循环,效率是O(n)。所以当N非常大时,所花的时间还是十分大的。

 

另一种思路:

 

    回文数的个数其实是有规律的。如:

 

    1位回文数: 9个

 

    2位回文数: 9个

 

    3位回文数: 90个

 

    4位回文数: 90个

 

    5位回文数: 900个

 

    6位回文数: 900个

 

    …

 

    我们看到9、90、900,是不是很有规律,那是什么原因?很简单,我们把回文数拆开两半

 

[123321]来看。两半的变化一样的,那我们只算其中一半就行了。首位不能是0,所以左半最小为

 

100,最大为999,共有999-100+1=900个,如此类推。

 

    所以我们可以基于以下原则:

 

    1、 回文数的数位每增长2,回文数的个数为原来的10倍。如从个位回文数到百位回文数,个数

 

从9个变为90个。

 

    2、 个位回文数的个数是9,1、2、3、…、9。

 

    总之理解原理后一切好办,步骤就偷懒不写了,看代码吧!

 

 

 

核心代码:

 

static long find(int index) {
int count = 0;
int number = 9; //记录数位上的回文数,如个位回文数为9
int w = 0; //记录数位

long half; //保存回文数的左半边的结果
long h = 1; //回文数的左半边的起始基数
long res; //结果

while(true) {
if(w > 0 && w%2 == 0) { //每进两个数位,回文数乘以10
number *= 10;
}
w
++; //数位加一
if(count + number > index) //回文数大于查找的回数,跳出
break;

count
+= number; //回文数加上当前数位上的回文数
}

index
-= count; //在当前数位上的位置。如w=5,index=50,则万位上的第50个回文数是我们所求

for(int i = 0; i < (w-1) / 2; i++) { //求回文数的左半边的基数,如回文数在万位上,则为100
h *= 10;
}

half
= h + index; //回文数的左半边,如100 + 50 = 150

res
= half;

if(w%2 != 0) //如果为奇数,则中间那个数不必算入右半边了!
half /=10;

while(half != 0) { //拼接回文数
res = res *10 + half % 10;
half
/= 10;
}

return res;
}

 

全部代码:

package com.icescut.classic.algorithm;
//数位指个位,十位,百位,千位。。。
class PalindromicNumber {
public static void main(String[] args) {
int input = Integer.parseInt(args[0]);
long res = find(input);
System.
out.println("res:" + res);

}

static long find(int index) {
int count = 0;
int number = 9; //记录数位上的回文数,如个位回文数为9
int w = 0; //记录数位

long half; //保存回文数的左半边的结果
long h = 1; //回文数的左半边的起始基数
long res; //结果

while(true) {
if(w > 0 && w%2 == 0) { //每进两个数位,回文数乘以10
number *= 10;
}
w
++; //数位加一
if(count + number > index) //回文数大于查找的回数,跳出
break;

count
+= number; //回文数加上当前数位上的回文数
}

index
-= count; //在当前数位上的位置。如w=5,index=50,则万位上的第50个回文数是我们所求

for(int i = 0; i < (w-1) / 2; i++) { //求回文数的左半边的基数,如回文数在万位上,则为100
h *= 10;
}

half
= h + index; //回文数的左半边,如100 + 50 = 150

res
= half;

if(w%2 != 0) //如果为奇数,则中间那个数不必算入右半边了!
half /=10;

while(half != 0) { //拼接回文数
res = res *10 + half % 10;
half
/= 10;
}

return res;
}
}

说明:

    因为按规律计算,效率为O1,不论数量级多大,能马上得到结果(不发生溢出情况下)。对比循环判断回文数的方法,大大的改善了。

转自:http://www.cnblogs.com/icescut/archive/2009/11/09/PalindromicNumber.html

 

 

 

 

缺8数、回文数的秘密

 人们把12345679叫做“缺8数”,这“缺8数”有许多让人惊讶的特点,比如用9的倍数与它相乘,乘积竟会是由同一个数组成,人们把这叫做“清一色”。比如:

 

12345679*9=111111111

12345679*18=222222222

12345679*27=333333333

……

12345679*81=999999999

这些都是9的1倍至9的9倍的。

还有99、108、117至171。最后,得出的答案是:

12345679*99=1222222221

12345679*108=1333333332

12345679*117=1444444443

 。。。

12345679*171=2111111109

 

回文数

中文里,有回文诗句、对联,如:"灵山大佛,佛大山灵","客上天然居,居然天上客"等等,都是美妙的符合正念倒念都一样的回文句.

回文数则是有类似22、383、5445、12321,不论是从左向右顺读,还是从右向左倒读,结果都是一样的特征.许多数学家着迷于此。

回文数中存在无穷多个素数11,101,131,151,191……。除了11以外,所有回文素数的位数都是奇数。道理很简单:如果一个回文素数的位数是偶数,则它的奇数位上的数字和与偶数位上的数字和必然相等;根据数的整除性理论,容易判断这样的数肯定能被11整除,所以它就不可能是素数。附整除原理11整除的特征。

能被11整除的数的特征
把一个数由右边向左边数,将奇位上的数字与偶位上的数字分别加起来,再求它们的差,如果这个差是11的倍数(包括0),那么,原来这个数就一定能被11整除.
例如:判断491678能不能被11整除.
—→奇位数字的和9+6+8=23

—→偶位数位的和4+1+7=12 23-12=11
因此,491678能被11整除.
这种方法叫"奇偶位差法".
除上述方法外,还可以用割减法进行判断.即:从一个数里减去11的10倍,20倍,30倍……到余下一个100以内的数为止.如果余数能被11整除,那么,原来这个数就一定能被11整除.
又如:判断583能不能被11整除.
用583减去11的50倍(583-11×50=33)余数是33, 33能被11整除,583也一定能被11整除.

 

 )。

人们借助电子计算机发现,在完全平方数、完全立方数中的回文数,其比例要比一般自然数中回文数所占的比例大得多。例如11^2=121,22^2=484,7^3=343,11^3=1331……都是回文数。

人们迄今未能找到四次方、五次方,以及更高次幂的回文素数。于是数学家们猜想:不存在nk(k≥4;n、k均是自然数)形式的回文数。

 

在电子计算器的实践中,还发现了一桩趣事:任何一个自然数与它的倒序数相加,所得的和再与和的倒序数相加,……如此反复进行下去,经过有限次步骤后,最后必定能得到一个回文数