回文數(shù) - 正讀倒讀都一樣的整數(shù)
“回文”是指正讀反讀都能讀通的句子，它是古今中外都有的一種修辭方式和文字游戲，如“我為人人，人人為我”等。在數(shù)學(xué)中也有這樣一類數(shù)字有這樣的特征，成為回文數(shù)（palindrome?number）。
設(shè)n是一任意自然數(shù)。若將n的各位數(shù)字反向排列所得自然數(shù)n1與n相等，則稱n為一回文數(shù)。例如，若n=1234321，則稱n為一回文數(shù)；但若n=1234567，則n不是回文數(shù)。
注意：
1.偶數(shù)個(gè)的數(shù)字也有回文數(shù)124421
2.小數(shù)沒有回文數(shù)
基本情況
1千以內(nèi)的回文數(shù)
在自然數(shù)中，最小的回文數(shù)是0，其次是1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,303,313,323,333,343,353,363,373,383,393,404,414,424,434,444,454,464,474,484,494,505,515,525,535,545,555,565,575,585,595,606,616,626,636,646,656,666,676,686,696,707,717,727,737,747,757,767,777,787,797,808,818,828,838,848,858,868,878,888,898,909,919,929,939,949,959,969,979,989,999.
平方回?cái)?shù)
定義：一個(gè)回文數(shù)，它同時(shí)還是某一個(gè)數(shù)的平方，這樣的數(shù)字叫做平方回?cái)?shù)。例如：121。
100以上至1000以內(nèi)的平方回?cái)?shù)只有3個(gè)，分別是：121、484、676。
其中，121是11的平方。
484是22的平方，同時(shí)還是121的4倍。
676是26的平方，同時(shí)還是169的4倍。
舉例說明
任意某一個(gè)數(shù)通過以下方式相加也可得到
如：29+92=121?還有?194+491=685，586+685=1271，1271+1721=2992
不過很多數(shù)還沒有發(fā)現(xiàn)此類特征（比如196,下面會(huì)講到）
另外個(gè)別平方數(shù)是回文數(shù)
1的平方=1
11的平方=121
111的平方=12321
1111的平方=1234321
……
……
依次類推
3×51=153
6×21=126
4307×62=267034
9×7×533=33579
上面這些算式,等號(hào)左邊是兩個(gè) - 或三個(gè)因數(shù)相乘,右邊是它們的乘積。如果把每個(gè)算式中的“×”和“=”去掉，那么，它們都變成回文數(shù)，所以，我們不妨把這些算式叫做“回文算式”。還有一些回文算式，等號(hào)兩邊各有兩個(gè)因數(shù)。請(qǐng)看：
12×42=24×21
34×86=68×43
102×402=204×201
1012×4202=2024×2101
不知你是否注意到，如果分別把上面的回文算式等號(hào)兩邊的因數(shù)交換位置，得到的仍是一個(gè)回文算式，比如：分別把“12×42=24×21”等號(hào)兩邊的因數(shù)交換位置，得到算式是：
42×12=21×24
這仍是一個(gè)回文算式。
還有更奇妙的回文算式，請(qǐng)看：
12×231=132×21（積是2772）
12×4032=2304×21（積是48384）
這種回文算式，連乘積都是回文數(shù)。
四位的回文數(shù)有一個(gè)特點(diǎn)，就是它決不會(huì)是一個(gè)質(zhì)數(shù)。設(shè)它為abba，那它等于a*1000+b*100+b*10+a，1001a+110b。能被11整除。
六位的也一樣，也能被11整除
還有，人們借助電子計(jì)算機(jī)發(fā)現(xiàn)，在完全平方數(shù)、完全立方數(shù)中的回文數(shù)，其比例要比一般自然數(shù)中回文數(shù)所占的比例大得多。例如11^2=121，22^2=484，7^3=343,11^3=1331，11^4=14641……都是回文數(shù)。
研究現(xiàn)狀
人們迄今未能找到自然數(shù) - 除0和1的五次方，以及更高次冪的回文數(shù)。于是數(shù)學(xué)家們猜想：不存在n^k - n≥2,k≥5;n、k均是自然數(shù)形式的回文數(shù)。
在電子計(jì)算器的實(shí)踐中，還發(fā)現(xiàn)了一樁趣事：任何一個(gè)自然數(shù)與它的倒序數(shù)相加，所得的和再與和的倒序數(shù)相加，……如此反復(fù)進(jìn)行下去，經(jīng)過有限次步驟后，最后必定能得到一個(gè)回文數(shù)。
這也僅僅是個(gè)猜想，因?yàn)橛行?shù)并不“馴服”。比如說196這個(gè)數(shù)，按照上述變換規(guī)則重復(fù)了數(shù)十萬次，仍未得到回文數(shù)。但是人們既不能肯定運(yùn)算下去永遠(yuǎn)得不到回文數(shù)，也不知道需要再運(yùn)算多少步才能最終得到回文數(shù)。
回文數(shù)算法
隨意找一個(gè)十進(jìn)制的數(shù)，把它倒過來成另一個(gè)數(shù)，再把這兩個(gè)數(shù)相加，得一個(gè)和數(shù)，這是第一步;然后把這個(gè)和數(shù)倒過來，與原來的和數(shù)相加，又得到一個(gè)新的和數(shù)，這是第二步。照此方法，一步步接續(xù)往下算，直到出現(xiàn)一個(gè)“回文數(shù)”為n。例如:28+82=110,110+011=121，兩步就得出了一個(gè)“回文數(shù)”。如果接著算下去，還會(huì)得到更多的“回文數(shù)”。這個(gè)過程稱為“196算法”。
對(duì)回文數(shù)的探索過程
上而提到的196這個(gè)數(shù)，是第一個(gè)可能的“利克瑞爾數(shù)”，因而它受到了最多的關(guān)注。由于還不可能證明一個(gè)數(shù)永遠(yuǎn)不能形成“回文數(shù)”，所以“196和其他那些 - 看起來不能形成回文數(shù)的數(shù)是利克瑞爾數(shù)”這一命題僅是猜想而非已獲證明。能證明的僅是那些反例，即如果一個(gè)數(shù)最終能形成“回文數(shù)”，則它不是“利克瑞爾數(shù)”。
在電子計(jì)算機(jī)尚未問世的1938年，美國數(shù)學(xué)家萊默 - D.?Lehmer,1905-1991計(jì)算到了第73步，得到了一個(gè)沒有形成“回文數(shù)”的35位的和數(shù)。至今挑戰(zhàn)此題的數(shù)學(xué)愛好者從沒有間斷過，并隨著計(jì)算機(jī)科技的發(fā)展，不斷有發(fā)燒友編寫不同的程序?qū)Υ祟}發(fā)起挑戰(zhàn)。據(jù)筆者最新調(diào)查，領(lǐng)軍人W.V.Landingham到2006年2月已經(jīng)計(jì)算到了699萬步，得到了一個(gè)2.89億位以上的和數(shù)，之間的結(jié)果仍未出現(xiàn)“回文數(shù)”。
另外介紹一個(gè)關(guān)于達(dá)到“回文數(shù)”需要計(jì)算步數(shù)的世界記錄。它是一個(gè)19位數(shù)字1,186,060,307,891,929,990,算出“回文數(shù)，，需要了261步。它是由Jason?Doucette的算法及程序于2005年11月30日發(fā)現(xiàn)的。下表列舉的是各位數(shù)字中，到達(dá)“回文數(shù)”花費(fèi)步數(shù)最多的代表性數(shù)字。
編程實(shí)現(xiàn)
JAVA源程序
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
publicclassPlalindrome{ publicstaticvoidmain - String[]args{ System.out.println - "11is"+ - isPlalindrome - 11?"":"not"+"Plalindromenumber"; System.out.println - "123is"+ - isPlalindrome - 123?"":"not"+"Plalindromenumber"; System.out.println - "17251is"+ - isPlalindrome - 17251?"":"not"+"Plalindromenumber"; System.out.println - "2882is"+ - isPlalindrome - 2882?"":"not"+"Plalindromenumber"; } publicstaticbooleanisPlalindrome - intnumber{ //此方法實(shí)現(xiàn)判斷數(shù)字是不是回文數(shù) Stringnum=String.valueOf - number; returnnewStringBuffer - num.reverse - .toString - .equalsIgnoreCase - num; } } |
—————
11?is?Plalindrome?number
123?is?not?Plalindrome?number
17251?is?not?Plalindrome?number
2882?is?Plalindrome?number
用visual?basic6.0
for?i?=?100?to?99999?'這里從100開始?后面可以隨便填，我這里填99999?表示所有3位數(shù)到五位數(shù)之間的回文數(shù)
if?StrReverse - i=i?then?print?i?'用StrReverse函數(shù)?判斷倒序后的數(shù)和原來數(shù)是否相同，如果相同者表示此數(shù)為回文數(shù)
next
用C語言編程
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include<stdio.h> intx,y; separate - int*data,intn { ????inti,j; ????y=0; ????while - n!=0 ????{ ???????????* - data+y=n%10;n=n/10;y++; ????} ????* - data+y='//0'; ????for - i=0,j=y-1;i<=j;i++,j– ????{ ????????if - * - data+i!=* - data+j{ ????????printf - "%d不是回文!!!/",x;break; ????????} ????} ????if - i?==y-1?printf - "是回文數(shù)"; } voidmain - { inta[99]; printf - "請(qǐng)輸入一個(gè)正整數(shù)："; scanf - "%d",&x; separate - a,x; } |
另外一種實(shí)現(xiàn)方法（c++）更簡便
#include<iostream>
using?namespace?std;
bool?symm - long?m
{
long?temp?=?m,n=0;
while? - temp
{
n?=?n*10+temp%10;
temp?=?temp/10;
}
return? - m?==?n;
}
int?main - int?argc,?_TCHAR*?argv[]
{
long?m;
cout<<"請(qǐng)輸入一個(gè)整數(shù)：";
cin>>m;
cout<<"輸入了"<<symm - m<<"個(gè)回文數(shù)！";
return?0;
}
python源程序
|
1 2 |
#coding:–utf-8– #-*-coding:cp936-*- classHws: def__init__ - self: self.result=[] defhWs - self: forainrange - 1,10000: b=str - a foriinrange - 0,len - b/2+1: ifb[i]==b[len - b-i-1]: self.result.append - a printself.result hws=Hws - hws.hWs - |
求最長回文數(shù)長度的manacher算法（O - n）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<iomanip> #defineINF99999999 usingnamespacestd; ? constintMAX=110000+10; chars[MAX*2]; intp[MAX*2]; ? intmain - { ????while - scanf - "%s",s!=EOF{ ????????intlen=strlen - s,id=0,maxlen=0; ????????for - inti=len;i>=0;–i{//插入'#' ????????????s[i+i+2]=s[i]; ????????????s[i+i+1]='#'; ????????}//插入了len+1個(gè)'#',最終的s長度是1~len+len+1即2*len+1,首尾s[0]和s[2*len+2]要插入不同的字符 ????????s[0]='*';//s[0]='*',s[len+len+2]='//0',防止在while時(shí)p[i]越界 ????????for - inti=2;i<2*len+1;++i{ ????????????if - p[id]+id>ip[i]=min - p[2*id-i],p[id]+id-i; ????????????elsep[i]=1; ????????????while - s[i-p[i]]==s[i+p[i]]++p[i]; ????????????if - id+p[id]<i+p[i]id=i; ????????????if - maxlen<p[i]maxlen=p[i]; ????????} ????????cout<<maxlen-1<<endl; ????} ????return0; } |