Euler # 4 in Python

Question

Палиндромное число читается одинаково в обоих направлениях. Самый большой палиндром, полученный из продукта двух двузначных чисел, составляет 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*999, который больше 0. Таким образом, условие не выполняется и выполняется следующая строка. Имеет смысл. В конце концов, однако, max_seen будет больше x*y, так почему же он continue здесь?

Кажется, эта строка даже не нужна, потому что если условие выполнено или не выполнено, программа будет продолжена в любом случае. Я подозреваю, что не понимаю, как работает continue в Python.

Это мой подход:

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 

С точки зрения эффективности, программа должна выйти, как только все новые x*y являются < max_seen, но 999*100 меньше 998*900 (то есть он еще не мог остановить как это до сих пор необходимо проверить 998*y, 997*y и т. д.), так как бы вы это закодировали?

Answer 1

Я подозреваю, что код, проверенный кодом x*y < max_seen, заключается в том, что это более легкий тест, чем is_palindrome. Если вы ожидаете, что многие из ваших потенциальных значений x и y не будут хорошими, сначала нужно сделать самые легкие тесты, чтобы несколько раз запускать сложные тесты.

При этом, если x*y < max_seen верен, успешных испытаний на текущее значение x не будет. Оптимизация может заключаться в замене continue (который переходит к следующему значению y) с break (который заканчивает внутренний цикл и поэтому переходит к следующему значению x).

Вы можете даже сделать что-то подобное для внешнего контура и проверить, если 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 

Answer 2

Два подхода почти одинаковы, хотя первый подход позволяет избежать проверки палиндрома, если продукт меньше самого большого палиндрома, который уже встречается, поэтому более эффективен.

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

Чтобы ответить на первый вопрос, в первом приближении, max_seen получит большой, только если она принадлежит к Palindrom, поэтому он будет нев конце концов получить большой.

Answer 3

Вот эффективное общее решение (~ 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)