0

回文数はどちらの方法でも同じように読めます。2 つの 2 桁の数の積から作られる最大の回文は 9009 = 91 × 99
です。2 つの 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

私が得られないのは、その行がどのように機能するかです。1 回max_seen = 0目x*yは999*9990 より大きいため、条件が満たされず、次の行が実行されます。理にかなっています。しかし、最終的には、なぜここにあるのでしょうかmax_seen。x*ycontinue

条件が満たされているかどうかに関係なく、プログラムは続行されるため、この行は必要ないようです。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

効率の観点から、プログラムはすべての newx*yが< max_seenになるとすぐに終了する必要がありますが、999*100未満です(つまり、 、 など998*900をまだチェックする必要があるため、まだ停止できませんでした)。それをどのようにコーディングしますか?998*y997*y

4

3 に答える 3

0

コードが最初にチェックする理由x*y < max_seenは、より簡単なテストであると思われis_palindromeます。x自分の可能性と価値の多くが良くないと予想yされる場合は、複雑なテストを数回実行するだけで済むように、最初に最も簡単なテストを実行するのが理にかなっています。

そうは言っても、 true の場合、現在の値x*y < max_seenに対して成功するテストはありません。最適化は、(次の値に進む) を(内側のループを終了し、次の値に進む)xに置き換えることです。continueybreakx

外側のループに対しても同様のことを行い、 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

2 つのアプローチはほぼ同じですが、最初のアプローチでは、既に検出された最大の回文よりも積が小さい場合に回文をチェックしないため、より効率的です。

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

最初の質問に答えるには、最初のアプローチでmax_seenは、回文に属している場合にのみ大きくなるため、最終的に大きくなることはありません 。

于 2013-05-09T14:44:28.997 に答える
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 に答える