用Python求三位数的最大回文数

Question

在 http://projecteuler.net/ 的问题4中，它说：

回文数指从左到右和从右到左读取都相同的数字。由两个2位数相乘得到的最大回文数是9009 = 91 * 99。

请找出由两个3位数相乘得到的最大回文数。

以下是我这里的代码：

def isPalindrome(num):
    return str(num) == str(num)[::-1]
def largest(bot, top):
    for x in range(top, bot, -1):
        for y in range(top,bot, -1):
            if isPalindrome(x*y):
                return x*y
print largest(100,999)

我应该找到最大的回文数，它输出了580085，我认为这是正确的，但是项目欧拉不这样认为，我出了什么问题吗？

---

当我反转for循环时，我没有好好思考，我删除了检查最大值的东西，太傻了。这是可行的代码。

def isPalindrome(num):
    return str(num) == str(num)[::-1]
def largest(bot, top):
    z = 0
    for x in range(top, bot, -1):
        for y in range(top,bot, -1):
            if isPalindrome(x*y):
                if x*y > z:
                    z = x*y
    return z
print largest(100,999)

它输出 906609

- FabianCook

---

因为我得到了995 * 583 = 580085。 - FabianCook

请访问http://forum.projecteuler.net/viewforum.php?f=50&sid=96f5f001e9fdeae0f2af2e049d872f9e，并更具体地访问http://forum.projecteuler.net/viewtopic.php?f=50&t=1989。 - Andbdrew

没有看过论坛...我应该删除这个吗？ - FabianCook

这并不违反规定...它只是不在论坛上.. - FabianCook

Answer 1

反向迭代并不会找到最大的x*y，而是找到具有最大x的回文数。存在比580085更大的答案；它有一个较小的x但有一个较大的y。

- John Kugelman

---

嗯，让我们稍微改变一下，马上回来。 - FabianCook

同意。你需要测试每个组合并跟踪最大值，而不是一旦找到回文就返回。 - japreiss

Answer 2

这个写法可以更高效地改写为：

from itertools import product

def is_palindrome(num):
    return str(num) == str(num)[::-1]

multiples = ( (a, b) for a, b in product(xrange(100,999), repeat=2) if is_palindrome(a*b) )
print max(multiples, key=lambda (a,b): a*b)
# (913, 993)

如果你在Python中做Euler题目，itertools和生成器会非常有用。

- Jon Clements

---

我只使用Python，因为它是一种解释性语言，否则我会使用Java。 - FabianCook

@SmartLemon 好的 - Haskell 也非常有用 ;) - Jon Clements

@SmartLemon 对于这类问题，一定要看看欧拉答案板上的Haskell解决方案，对于你已经解决的问题，你会找到代码片段（我认为还有一个网站，其中也写了前'n'个问题的Haskell代码）。 - Jon Clements

Answer 3

虽然不是最高效的答案，但我喜欢它足够紧凑，可以放在一行上。

print max(i*j for i in xrange(1,1000) for j in xrange(1,1000) if str(i*j) == str(i*j)[::-1])

- user3833942

Answer 4

尝试使其更加高效，同时保持易读性：

def is_palindrome(num):
    return str(num) == str(num)[::-1]

def fn(n):
    max_palindrome = 1
    for x in range(n,1,-1):
        for y in range(n,x-1,-1):
            if is_palindrome(x*y) and x*y > max_palindrome:
                max_palindrome = x*y
            elif x * y < max_palindrome:
                break
    return max_palindrome

print fn(999)

- blueberryfields

Answer 5

以下是我的Python代码：

max_pal = 0
for i in range(100,999):
    for j in range(100,999):
      mult = i * j 
      if str(mult) == str(mult)[::-1]: #Check if the number is palindrome
          if mult > max_pal: 
              max_pal = mult
print (max_pal)

- Irmak Aydeniz

---

添加几行注释/解释您的方法会很有用。 - Yannis

Answer 6

这里我添加了两个 'break' 来提高程序的速度。

def is_palindrome(num):
    return str(num) == str(num)[::-1]
def max_palindrome(n):
    max_palindrome = 1
    for i in range(10**n-1,10**(n-1)-1,-1):
        for j in range(10**n-1,i-1,-1):
            if is_palindrome(i*j) and i*j > max_palindrome:
                max_palindrome = i * j
                break
            elif i*j < max_palindrome:
                break
    return max_palindrome
n=int(raw_input())
print max_palindrome(n)

- CooLee

---

非常欢迎您在代码中添加注释以进行说明。 - olyv

Answer 7

这是我解决这个问题的代码。

lst = []
for i in range(100,1000): 
    for n in range(2,i) : 
        lst.append (i* n) 
        lst.append(i*i)

lst2=[]
for i in lst: 
    if str(i) == str(i)[::-1]:
        lst2.append(i)
print max(lst2) 

- Darshi

Answer 8

每次都不必从999开始，因为它已经被找到了。下面是一种使用字符串函数查找三位数中最大回文数的简单方法。

def palindrome(y):
    z=str(y)
    w=z[::-1]
    if (w==z):
        return 0
    elif (w!=z):
        return 1        
h=[]
a=999
for i in range (999,0,-1):
    for j in range (a,0,-1):
    l=palindrome(i*j)
    if (l==0):
        h=h+[i*j]               
    a-=1
print h
max=h[0]

for i in range(0,len(h)):
    if (h[i] > max):
    max= h[i]
print "largest palindrome using multiple of three digit number=%d"%max  

- Anoop M

Answer 9

这是我的解决方案：

lst1 = [x for x in range(1000)]
palindrome = []

def reverse(x):
    a = str(x)[::-1]
    return int(a)

x = 0
while x < len(lst1):
    for y in range(1000):
        z = lst1[x] * y
        if z == reverse(z):
            palindrome.append(z)
    x += 1

duppal = set(palindrome)
sortpal = sorted(duppal)
total = sortpal[-1]
print(sortpal)
print('Largest palindrome: ' + str(total))

- Mark Mamore

Answer 10

580085 = 995 X 583，而 906609 = 993 X 913。 只有通过从上到下的穷举才发现这个规律！

- Abdul Hasib Uddin