0

回文数的两种读法都是一样的。由两个 2 位数乘积构成的最大回文数是 9009 = 91 × 99。
求由两个 3 位数乘积构成的最大回文数。

http://projecteuler.net/problem=4

以下是我对这个问题的解决方案。它有效，但我注意到另一个使用的解决方案

if x*y < max_seen: continue

像这样：

def biggest():
    big_x, big_y, max_seen = 0, 0, 0
    for x in xrange(999,99,-1):
        for y in xrange(x, 99,-1): 
            if x*y < max_seen: continue
            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

我不明白那条线是如何工作的。第一次通过max_seen = 0，第一次x*y大于999*9990。因此不满足该条件并运行下一行。说得通。然而，最终max_seen会比它更大x*y，为什么会在continue这里呢？

似乎甚至不需要这条线，因为如果条件满足或不满足，程序无论如何都会继续。我怀疑我不了解continuePython 的工作原理。

这是我的方法：

def find_biggest():
    big_x, big_y, new_pal, max_seen = 0, 0, 0, 0
    for x in range(999, 100, -1):
        for y in range(x, 100, -1):
            if is_palindrome(x*y) == True:
                new_pal = x*y
                if new_pal > max_seen:
                    big_x, big_y, max_seen = x, y, new_pal

从效率的角度来看，程序应该在所有 new x*yare时立即退出< max_seen，但999*100小于998*900（意味着它还不能停止，因为它仍然需要检查998*y,997*y等）那么你将如何编码呢？

4

3 回答 3

0

这两种方法几乎相同，尽管第一种方法在产品小于已经遇到的最大回文时避免检查回文，因此更有效。

if x*y < max_seen: continue
if is_palindrome(x*y):
   ...

要回答你的第一个问题，在第一种方法中，max_seen只有当它属于回文时才会变大，所以它最终不会 变大。

于 2013-05-09T14:44:28.997 回答
0

我怀疑代码x*y < max_seen首先检查的原因是它比is_palindrome. 如果您认为自己的许多潜力x和y价值观都不好，那么首先进行最简单的测试是有意义的，这样您只需要运行几次复杂的测试。

也就是说，如果x*y < max_seen为真，则不会对当前x值进行任何成功的测试。优化可以是用（结束内部循环并继续下一个值）替换continue（继续下一个值）。ybreakx

你甚至可以对外部循环做类似的事情，并测试 if x * 999 < max_seen。如果是这样，您将永远找不到更好的结果，您可以停止循环。这是代码中的样子：

def biggest():
    big_x, big_y, max_seen = 0, 0, 0
    for x in xrange(999,99,-1):
        if x*x < max_seen:
            break # breaks out of outer loop, as no later x value can be better
        for y in xrange(x, 99,-1): 
            if x*y < max_seen:
                break # breaks out of inner loop, no later y value can be better
            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y
    return big_x, big_y, max_seen
于 2013-05-09T14:47:11.467 回答
0

这是一个有效的通用解决方案（比其他解决方案快约 5 倍）： 

def pgen(factor):
    ''' Generates stream of palindromes smaller than factor**2 
    starting with largest possible palindrome '''
    pmax = str(factor**2)
    half_palindrome = int(pmax[0:len(pmax)/2]) - 1
    for x in xrange(half_palindrome, 0, -1):
        yield int(str(x) + str(x)[::-1])

def biggest(factor):
    ''' Returns largest palindrome and factors '''
    for palindrome in pgen(factor):
        for f1 in xrange(factor/11*11, factor/10, -11):
            f2 = palindrome/f1
            if f2 > factor:
                break
            if f2*f1 == palindrome:
                return palindrome, f1, f2

>>> biggest(99)
(9009, 99, 91)
>>> biggest(999)
(906609, 993, 913)
>>> biggest(9999)
(99000099, 9999, 9901)
>>> biggest(99999)
(9966006699L, 99979, 99681L)
>>> biggest(9999999)
(99956644665999L, 9998017, 9997647L)
>>> biggest(99999999)
(9999000000009999L, 99999999, 99990001L)
>>> biggest(999999999)
(999900665566009999L, 999920317, 999980347L)
于 2013-05-09T16:44:45.833 回答