【算法趣题】Q01 回文十进制数

前言

【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。

回文数    

如果把某个数的各个数字按相反的顺序排列，得到的数和原来的数相同，则这个数就是“回文数”。例如 123454321 就是一个回文数。

问题描述

        求用十进制、二进制、八进制表示都是回文数的所有数字，大于十进制数10的最小值。

例）9（十进制数） = 1001（二进制数） = 11（八进制数）

例中的十进制数9小于10，因此不符合要求。

思路

因为二进制也是一个回文数，则二进制数的最高位和最低位相等，如果是0，明显不对，则只能1.二进制的最低位是1，对应的十进制一定是奇数。

举个例子，给定十进制数13，求对应的二进制的过程如下：

13/2=6 余 1 （余数对应二进制的最低位）

  6/2=3 余 0

  3/2=1 余 1

  1/2=0 余 1

从下往上排列余数后就可以得到二进制数1101。（最低位是1，则第一个除法的余数是1，即十进制数/2的余数是1，则该十进制数定是奇数）

因此，可以从11 开始，按顺序搜索，找到符合条件的数。

JavaScript实现

书中有个用JavaScript版本实现，我嵌套在html代码里，代码如下：

/* 为字符串类型添加返回逆序字符串的方法 */

  String.prototype.reverse = function(){

	return this.split("").reverse().join("");

}

/* 从11开始搜索 */

var num = 11;

while(true){

	if((num.toString() ==num.toString().reverse()) &&

		(num.toString(2) ==num.toString(2).reverse(2)) &&

		(num.toString(8) ==num.toString(8).reverse(8))){

		document.write("<p>十进制数：",num,"</p>");

		document.write("<p>二进制数：",num.toString(2),"</p>");

		document.write("<p>八进制数：",num.toString(8),"</p>");

		break;

	}

	/* 只搜索奇数，每次加2 */

	num += 2;

}

python3实现

python3中十进制数转化为二进制数和八进制数的函数分别为bin()和oct().

ten = 15

two = bin(ten)

eight = oct(ten)

print(str(ten))

print(str(two))

print(str(eight))

15

0b1111

0o17

python中对字符串s的逆序可用 s[::-1]表示：

a = 12345

s = str(a)

s[::-1]

'54321'

由于Python3中的二进制数以0b开头，八进制数以0o（python2中是以0开头的，注意区分）开头，所以转换成字符串后要剔除前缀，剩下数字再来做是否回文的判断。

判断十进制数，对应是二进制数和八进制数是否都是回文，写了个函数：

def isAllHuiwen(a):

    ten = str(a)

    two = str(bin(a))[2:]

    eight = str(oct(a))[2:]

    if ten == ten[::-1] and two == two[::-1] and eight == eight[::-1]:

        print("十进制数："+ten)

        print("二进制数："+two)

        print("八进制数："+eight)

        return True

    else:

        return False

因此该问题比较好解决了：

num = 11

while True:

    if(isAllHuiwen(num)):

        break

    else:

        num = num + 2

结果为：

十进制数：585

二进制数：1001001001

八进制数：1111