前言
【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》,书中是用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