有趣的回文数.ppt

有趣的回文数,什么是回文数？,中文里,有回文诗句、对联,如:灵山大佛,佛大山灵,客上天然居,居然天上客等等,都是美妙的符合正念倒念都一样的回文句.回文数则是有类似22、383、5445、12321,不论是从左向右顺读,还是从右向左倒读,结果都是一样的特征.许多数学家着迷于此。回文数中存在无穷多个素数11，101，131，151，191。除了11以外，所有回文素数的位数都是奇数。道理很简单：如果一个回文素数的位数是偶数，则它的奇数位上的数字和与偶数位上的数字和必然相等；根据数的整除性理论，容易判断这样的数肯定能被11整除，所以它就不可能是素数。,什么是回文数？,人们借助电子计算机发现，在完全平方数、完全立方数中的回文数，其比例要比一般自然数中回文数所占的比例大得多。例如112=121，222=484，73=343,113=1331都是回文数。人们迄今未能找到四次方、五次方，以及更高次幂的回文素数。于是数学家们猜想：不存在nk(k4;n、k均是自然数)形式的回文数。在电子计算器的实践中，还发现了一桩趣事：任何一个自然数与它的倒序数相加，所得的和再与和的倒序数相加，如此反复进行下去，经过有限次步骤后，最后必定能得到一个回文数。,判断回文数,一个经典的题目，而且有一种经典的算法，也是当时我遇到的那个题目的标准答案。回文数，即一个整数，无论从左到右看还是从右到左看都是同一个数字，即以中间的那个数字左右对称。例如737，59395，12321之类的。,判断回文数,经典的算法是：分别用整除和模除求出两端的数位，然后比较，如果相同，则去掉这两个数位，再次求出新的两端的数位，再比较，如此循环，直到出现不相同就可以判断不是回文数，或者到了中间的数位仍然相同的话就为回文数，这种算法的优点是，在排除非回文数的时候会快一些，因为不一定要比较到中间那位也许一开始的头尾两位就已经不相同了，那么这个判断的过程就可以很快结束了，在时间复杂度上也许会快一些，但缺点也是显然的，就是如果所判断数就是回文数的话，则必须对每一对数位都作比较，而且在判断是否为中位即结束位置的时候就比较困难了，还要分奇数位和偶数位，甚至还要先求出数字的数位长度。,判断回文数,我的算法是：用模除10读出低位数位，然后入队列，然后用整除10删除这个数位，再用模除10读出新的最低位，再入列，再整除10删除这个数位，如此循环，终止条件是整除后已经为0了，这样就表示整个数都已经从低到高位逐位入列了。然后原来的从低位开始出列，出一位就乘10，然后再出一位累加，再乘10，再累加，直到所有的数位都出列，实际上出来的结果就是把原来的数字倒序了一次，由于倒序后仍然是一个数字，所以可以直接将原来的数字和倒序后的数字比较，如果相同即为回文数，否则不是,判断回文数,以上说的只是编程的实现细节，简述一下思路，实际上就是利用了回文数的特点，就是以中线两端对称，所以我就先生成一个原数的镜像数即高低位倒序了一下，如果是回文数的话，肯定和他的镜像数相同的，而且由于倒序了后仍是一个整数，不是字符串，所以可以直接作两个整数的比较操作就行了，不用逐个数位比较，所以无论这个要判断的数多长多大，都只是作了一次整数比较而已。但缺点也是有的，就是一定要把整个整数的所有数位都读出一次，然后再写进并构造另一个整数。但由于比较次数大大减少，在判断一个较长较大的整数时，未必就是更耗费时间的，而且实现起来简单很多，尤其是判断终止的时候比较简单,判断回文数,另外，上面所说借助队列也只是为了说明的更加清晰更加易懂而已，用堆栈来实现是同样的道理，这只是为了构造那个倒序数的一个手段而已，实际上，细心考虑一下，其实可以根本不必借助这些数据结构的，在读出了低位后直接就写入新的那个倒序数就可以了，代码如下：（C+）boolis_huiwen(longnumber,intrad)/number是要判断的整数，rad是判断基于的数制，一般为10进制，即rad等于10，也可以等于2,8,16等/返回的是一个bool类型的值，为true即number是回文数，为false则否longnum=number;/原数longnum_reverse=0;/倒序数if(num=0/只有一个数位则直接返回true，不必再做,判断回文数,下面的比较while(num)/原数num为0则终止num_reverse*=rad;/倒序数增位num_reverse+=num%rad;/求出当前的最低位并加到新的倒序数上num=num/rad;/原数num去掉最低位if(number=num_reverse)/只作一次比较，而且只是整数比较returntrue;elsereturnfalse;,再见,