有趣的回文數(shù)課件

有趣的回文數(shù)什么是回文數(shù)？

中文里,有回文詩句、對聯(lián),如:"靈山大佛,佛大山靈","客上天然居,居然天上客"等等,都是美妙的符合正念倒念都一樣的回文句.

回文數(shù)則是有類似22、383、5445、12321,不論是從左向右順讀,還是從右向左倒讀,結(jié)果都是一樣的特征.許多數(shù)學(xué)家著迷于此。

回文數(shù)中存在無窮多個素數(shù)11，101，131，151，191……。除了11以外，所有回文素數(shù)的位數(shù)都是奇數(shù)。道理很簡單：如果一個回文素數(shù)的位數(shù)是偶數(shù)，則它的奇數(shù)位上的數(shù)字和與偶數(shù)位上的數(shù)字和必然相等；根據(jù)數(shù)的整除性理論，容易判斷這樣的數(shù)肯定能被11整除，所以它就不可能是素數(shù)。

什么是回文數(shù)？

人們借助電子計算機(jī)發(fā)現(xiàn)，在完全平方數(shù)、完全立方數(shù)中的回文數(shù)，其比例要比一般自然數(shù)中回文數(shù)所占的比例大得多。例如112=121，222=484，73=343,113=1331……都是回文數(shù)。

人們迄今未能找到四次方、五次方，以及更高次冪的回文素數(shù)。于是數(shù)學(xué)家們猜想：不存在nk(k≥4;n、k均是自然數(shù))形式的回文數(shù)。

在電子計算器的實踐中，還發(fā)現(xiàn)了一樁趣事：任何一個自然數(shù)與它的倒序數(shù)相加，所得的和再與和的倒序數(shù)相加，……如此反復(fù)進(jìn)行下去，經(jīng)過有限次步驟后，最后必定能得到一個回文數(shù)。判斷回文數(shù)經(jīng)典的算法是：分別用整除和模除求出兩端的數(shù)位，然后比較，如果相同，則去掉這兩個數(shù)位，再次求出新的兩端的數(shù)位，再比較，如此循環(huán)，直到出現(xiàn)不相同就可以判斷不是回文數(shù)，或者到了中間的數(shù)位仍然相同的話就為回文數(shù)，這種算法的優(yōu)點是，在排除非回文數(shù)的時候會快一些，因為不一定要比較到中間那位也許一開始的頭尾兩位就已經(jīng)不相同了，那么這個判斷的過程就可以很快結(jié)束了，在時間復(fù)雜度上也許會快一些，但缺點也是顯然的，就是如果所判斷數(shù)就是回文數(shù)的話，則必須對每一對數(shù)位都作比較，而且在判斷是否為中位即結(jié)束位置的時候就比較困難了，還要分奇數(shù)位和偶數(shù)位，甚至還要先求出數(shù)字的數(shù)位長度。

判斷回文數(shù)

我的算法是：用模除10讀出低位數(shù)位，然后入隊列，然后用整除10刪除這個數(shù)位，再用模除10讀出新的最低位，再入列，再整除10刪除這個數(shù)位，如此循環(huán)，終止條件是整除后已經(jīng)為0了，這樣就表示整個數(shù)都已經(jīng)從低到高位逐位入列了。然后原來的從低位開始出列，出一位就乘10，然后再出一位累加，再乘10，再累加，直到所有的數(shù)位都出列，實際上出來的結(jié)果就是把原來的數(shù)字倒序了一次，由于倒序后仍然是一個數(shù)字，所以可以直接將原來的數(shù)字和倒序后的數(shù)字比較，如果相同即為回文數(shù)，否則不是判斷回文數(shù)

以上說的只是編程的實現(xiàn)細(xì)節(jié)，簡述一下思路，實際上就是利用了回文數(shù)的特點，就是以中線兩端對稱，所以我就先生成一個原數(shù)的鏡像數(shù)－－即高低位倒序了一下，如果是回文數(shù)的話，肯定和他的鏡像數(shù)相同的，而且由于倒序了后仍是一個整數(shù)，不是字符串，所以可以直接作兩個整數(shù)的比較操作就行了，不用逐個數(shù)位比較，所以無論這個要判斷的數(shù)多長多大，都只是作了一次整數(shù)比較而已。但缺點也是有的，就是一定要把整個整數(shù)的所有數(shù)位都讀出一次，然后再寫進(jìn)并構(gòu)造另一個整數(shù)。但由于比較次數(shù)大大減少，在判斷一個較長較大的整數(shù)時，未必就是更耗費時間的，而且實現(xiàn)起來簡單很多，尤其是判斷終止的時候比較簡單

判斷回文數(shù)下面的比較

while(num){

//原數(shù)num為0則終止

num_reverse*=rad;

//倒序數(shù)增位

num_reverse+=num%rad;

//求出當(dāng)前的最低位并加到新的倒序數(shù)上

num=num/rad;

//原數(shù)num去掉最低位

}

if(number==num_reverse)