問題描述
Python 中的歐拉 #4 (Euler #4 in Python)
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2‑digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3‑digit numbers.
http://projecteuler.net/problem=4
Below is my solution to this problem. It works, but I noticed another solution that used
if x*y < max_seen: continue
like this:
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
What I don't get is how that line works. The first time through max_seen = 0 and the first x*y is 999*999 which is greater than 0. So that condition isn't met and the next line is run. Makes sense. Eventually, however, max_seen will be larger than x*y so why does it continue here?
It seems this line isn't even needed because if the condition is or isn't met the program will continue anyway. I suspect I'm not understanding how continue works in Python.
This is my approach:
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
From an efficiency standpoint the program should exit as soon as all new x*y are < max_seen, but 999*100 is less than 998*900 (meaning it couldn't stop yet as it still needs to check 998*y, 997*y, etc.) so how would you code that?
參考解法
方法 1:
The two approaches are almost the same although the first approach avoids checking the palindrom if the product is smaller than the biggest palindrom already encountered, therefore more efficient.
if x*y < max_seen: continue
if is_palindrome(x*y):
...
To answer your first question, in the first approach, max_seen will get large only if it belongs to a palindrom, so it will not eventually get large.
方法 2:
I suspect the reason that the code checks for x*y < max_seen first is that it is an easier test than is_palindrome. If you expect many of your potential x and y values to be no good, it makes sense to do the easiest tests first so that you only need to run the complicated tests a few times.
That said, if x*y < max_seen is true, there won't be any successful tests for the current x value. An optimization could be to replace continue (which goes on to the next y value) with break (which ends the inner loop and so goes on to the next x value).
You could even do something similar for the outer loop, and test if x * 999 < max_seen. If so, you'll never find a better result and you can stop looping. Here's how that would look in code:
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
方法 3:
Here is an efficient general solution (~5x faster than others):
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)
(by caadrider、muratgu、Blckknght、dansalmo)