迴文數

迴文數

“回文”是指正讀反讀都能讀通的句子,它是古今中外都有的一種修辭方式和文字遊戲,如“我為人人,人人為我”等。在數學中也有這樣一類數字有這樣的特徵,成為迴文數(palindrome number)。

設n是一任意自然數。若將n的各位數字反向排列所得自然數n1與n相等,則稱n為一迴文數。例如,若n=1234321,則稱n為一迴文數;但若n=1234567,則n不是迴文數。

注意:

1.偶數個的數字也有迴文數124421

2.小數沒有迴文數

基本介紹

  • 中文名:迴文數
  • 外文名:palindrome number
  • 定義:正讀倒讀都一樣的整數
基本情況,1千以內的迴文數,平方回數,舉例說明,研究現狀,迴文數算法,對迴文數的探索過程,編程實現,JAVA源程式,用visual basic6.0,用C語言編程,python源程式,求最長迴文數長度的manacher算法(O(n)),

基本情況

1千以內的迴文數

在自然數中,最小的迴文數是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.

平方回數

定義:一個迴文數,它同時還是某一個數的平方,這樣的數字叫做平方回數。例如:121。
100以上至1000以內的平方回數只有3個,分別是:121、484、676。
其中,121是11的平方。
484是22的平方,同時還是121的4倍。
676是26的平方,同時還是169的4倍。

舉例說明

任意某一個數通過以下方式相加也可得到
如:29+92=121 還有 194+491=685,586+685=1271,1271+1721=2992
不過很多數還沒有發現此類特徵(比如196,下面會講到)
另外個別平方數是迴文數
1的平方=1
11的平方=121
111的平方=12321
1111的平方=1234321
……
……
依次類推
3×51=153
6×21=126
4307×62=267034
9×7×533=33579
上面這些算式,等號左邊是兩個(或三個)因數相乘,右邊是它們的乘積。如果把每個算式中的“×”和“=”去掉,那么,它們都變成迴文數,所以,我們不妨把這些算式叫做“回文算式”。還有一些回文算式,等號兩邊各有兩個因數。請看:
12×42=24×21
34×86=68×43
102×402=204×201
1012×4202=2024×2101
不知你是否注意到,如果分別把上面的回文算式等號兩邊的因數交換位置,得到的仍是一個回文算式,比如:分別把“12×42=24×21”等號兩邊的因數交換位置,得到算式是:
42×12=21×24
這仍是一個回文算式。
還有更奇妙的回文算式,請看:
12×231=132×21(積是2772)
12×4032=2304×21(積是48384)
這種回文算式,連乘積都是迴文數。
四位的迴文數有一個特點,就是它決不會是一個質數。設它為abba,那它等於a*1000+b*100+b*10+a,1001a+110b。能被11整除。
六位的也一樣,也能被11整除
還有,人們藉助電子計算機發現,在完全平方數完全立方數中的迴文數,其比例要比一般自然數中迴文數所占的比例大得多。例如11^2=121,22^2=484,7^3=343,11^3=1331,11^4=14641……都是迴文數。

研究現狀

人們迄今未能找到自然數(除0和1)的五次方,以及更高次冪的迴文數。於是數學家們猜想:不存在n^k(n≥2,k≥5;n、k均是自然數)形式的迴文數。
在電子計算器的實踐中,還發現了一樁趣事:任何一個自然數與它的倒序數相加,所得的和再與和的倒序數相加,……如此反覆進行下去,經過有限次步驟後,最後必定能得到一個迴文數。
這也僅僅是個猜想,因為有些數並不“馴服”。比如說196這個數,按照上述變換規則重複了數十萬次,仍未得到迴文數。但是人們既不能肯定運算下去永遠得不到迴文數,也不知道需要再運算多少步才能最終得到迴文數。

迴文數算法

隨意找一個十進制的數,把它倒過來成另一個數,再把這兩個數相加,得一個和數,這是第一步;然後把這個和數倒過來,與原來的和數相加,又得到一個新的和數,這是第二步。照此方法,一步步接續往下算,直到出現一個“迴文數”為n。例如:28+82=110,110+011=121,兩步就得出了一個“迴文數”。如果接著算下去,還會得到更多的“迴文數”。這個過程稱為“196算法”。

對迴文數的探索過程

上而提到的196這個數,是第一個可能的“利克瑞爾數”,因而它受到了最多的關注。由於目前還不可能證明一個數永遠不能形成“迴文數”,所以“196和其他那些(看起來)不能形成迴文數的數是利克瑞爾數”這一命題僅是猜想而非已獲證明。能證明的僅是那些反例,即如果一個數最終能形成“迴文數”,則它不是“利克瑞爾數”。
在電子計算機尚未問世的1938年,美國數學家萊默(D. Lehmer,1905-1991)計算到了第73步,得到了一個沒有形成“迴文數”的35位的和數。至今挑戰此題的數學愛好者從沒有間斷過,並隨著計算機科技的發展,不斷有發燒友編寫不同的程式對此題發起挑戰。據筆者最新調查,領軍人W.V.Landingham到2006年2月已經計算到了699萬步,得到了一個2.89億位以上的和數,之間的結果仍未出現“迴文數”。
另外介紹一個關於達到“迴文數”需要計算步數的世界記錄。它是一個19位數字1,186,060,307,891,929,990,算出“迴文數,,需要了261步。它是由Jason Doucette的算法及程式於2005年11月30日發現的。下表列舉的是各位數字中,到達“迴文數”花費步數最多的代表性數字。
迴文數

編程實現

JAVA源程式

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){//此方法實現判斷數字是不是迴文數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位數到五位數之間的迴文數
if StrReverse(i)=i then print i '用StrReverse函式 判斷倒序後的數和原來數是否相同,如果相同者表示此數為迴文數
next

用C語言編程

#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不是回文!!!\n",x);break;        }    }    if(i ==y-1) printf("是迴文數");}voidmain(){inta[99];printf("請輸入一個正整數:");scanf("%d",&x);separate(a,x);}
另外一種實現方法(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<<"請輸入一個整數:";
cin>>m;
cout<<"輸入了"<<symm(m)<<"個迴文數!";
return 0;
}

python源程式

#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()

求最長迴文數長度的manacher算法(O(n))

#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<queue>#include<algorithm>#include<map>#include<iomanip>#defineINF99999999usingnamespacestd;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個'#',最終的s長度是1~len+len+1即2*len+1,首尾s[0]和s[2*len+2]要插入不同的字元        s[0]='*';//s[0]='*',s[len+len+2]='\0',防止在while時p[i]越界        for(inti=2;i<2*len+1;++i){            if(p[id]+id>i)p[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;}

熱門詞條

聯絡我們