求能分解为两个三位数乘积的最大回文数

注：所谓回文数就是正序和倒序相等的数字，好比9009的倒序还是9009

在题目中，我们已经知道了这个回文数是2个三位数的乘积， 那我们可以很轻松的写出代码。

#定义数字倒转函数
def	reverse(num):
    strnum = str(num)[::-1]
    return int(strnum)

max = None
for a in range(100, 1000):
    for b in range(100, 1000):
        rs = a * b
        if rs == reverse(rs) and rs > max:
            max = rs
print max

用这个方法我们是可以得到结果，但是效率好像不尽人意。 现在我们来分析下还可以怎么优化我们的程序：

1. 上述程序中，a和b的乘积会反复出现吗？ 比如当a=132，b=528同a=528， b=132的结果是一样的，那我们通过设置b小于或大于a，是不是可以避免这样的情况。

2. 题目要求我们找的最大的乘积， 那2个三位数肯定也是很大， 我们用从大到小查询，是不是会比从小到大查询快很多呢，当我们找到的后一个回文数没有前一个大，那程序就可以终止了。

3. 两个三位数的乘积肯定是一个六位数， 而这个六位回文数数P我们可以用xyzzyx的形式表示，那我们可以得到下面的公式：
P = 100000x + 10000y + 1000z + 100z + 10y + x
P = 100001x + 10010y + 1100z
P = 11(9091x + 910y + 100z)
在这个公式中我们发现回文数是11的倍数，而11是质数，这也就表示不是a可以被11整除，就是b可以被11整除。那我们合理的利用11作为递进数是不是要比原来的1更效率呢?

通过上述分析，我们来重写代码：

#定义数字倒转函数
def	reverse(num):
    strnum = str(num)[::-1]
    return int(strnum)

max = None
for a in range(999, 99, -1):
    db = -1
    start = 999
    if a % 11 != 0:
        start = 990
        db = -11
    for b in range(start, 99, db):
        rs = a * b
        if rs == reverse(rs):
            if rs > max:
                max = rs
            else:
                break
print max

经测试，原来的程序需要810000次循环，而优化后的程序只需要71533次循环， 性能提高了10倍多。

评论

1 楼 danielzhang0212 2011-01-08  

在euler project做题，不会了就搜到你的帖子了。分析的相当好，学习了！