为什么这个简单的Python脚本会返回错误答案？

Question

我又在做Project Euler的题目了，这次是第4题。这个脚本的目的是找出两个三位数相乘得到的最大回文数。回文数就是正着读和反着读都一样的数字。我觉得这个问题应该比较简单，但我得到的答案太低了。具体来说，我得到的是580085，而正确答案是906609。

有人能告诉我哪里出错了吗？

#!/usr/bin/env python
# encoding: utf-8
"""
P4.py

Created by Andrew Levenson on 2010-06-29.
Copyright (c) 2010 __MyCompanyName__. All rights reserved.
"""

import sys
import os


def main():
    for x in range(100, 1000):
        for y in range(100, 1000):
            z = str( x * y )
            s = str( z[::-1] ) # Reverse z
            if z == s:
                t = z
    print t


if __name__ == '__main__':
    main()

Answer 1

这个问题是要找出最大的回文数。你现在的做法是只找到最后一个回文数，而不是最大的。你以为最后一个就是最大的，但其实并不是这样，因为你是在检查所有可能的组合。

举个例子，你在考虑200乘以101的时候，其实之前已经考虑过101乘以999了。

Answer 2

这里有一种巧妙但正确的方法，可以用一个表达式来完成...:

def main():
  print max(p for x in range(100, 1000) for y in range(x, 1000)
              for p in (x * y,) if str(p) == str(p)[::-1])

其中的关键在于那个单个的 for p 语句，它的作用就像是一个赋值（这样可以避免多次计算那个乘积;-）。

需要注意的是，接受的答案是错误的（还有其他几个也是），因为它查找的是字符串 "max"，而这和整数 max 是不同的——试着运行一下，你就会明白了！-)

Answer 3

你的代码没有确保它打印出最大的乘积，因为后面可能会出现一个更小的乘积来替代它。要解决这个问题，可以把 t 初始化为零，然后把你的条件改成

if z==s and int(z)>t:
    t = int(z)

或者可以这样写，效果是一样的：

if z==s:
    t = max(t,int(z))

编辑: 上面修复了整数和字符串的问题。不过这样写会更简洁，避免了把数字转换成字符串再转回整数：

def isPalindrome(x):
    s = str(x)
    return s == s[::-1]

t = 0
for x in range(100, 1000):
    for y in range(100, 1000):
        z = x * y
        if isPalindrome(z) and z > t:
            t = z
print t