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

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

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

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

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

什么是回文數(shù)？

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

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

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

判斷回文數(shù)

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

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