Задача Эйлера № 4

Question

Используя Python, я пытаюсь решить проблему # 4 проблемы Project Euler . Может кто-нибудь сказать, пожалуйста, что я делаю неправильно? Проблема состоит в том, чтобы найти самый большой палиндром из двух трехзначных чисел . Вот что я имею до сих пор.

import math

def main(): 
    for z in range(100, 1000):
        for y in range(100, 1000):
            for x in range(1, 1000000):
                x = str(x)
                if x == x[::-1] and x == z*y:
                    print x 

if __name__ == '__main__':
    main()

Answer 1

Некоторые проблемы эффективности:

1. начало сверху (поскольку мы можем использовать это при пропуске большого количества вычислений)
2. не рассчитывать дважды

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

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):  # so we don't double count   
            if x*y < max_seen: continue  # since we're decreasing, 
                                # nothing else in the row can be bigger
            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

    return big_x,big_y,max_seen

biggest()
# (993, 913, 906609)

Answer 2

Попробуйте вычислить x по произведению z и y, а не проверять каждое число от 1 до миллиона. Подумайте об этом: если вас попросили вычислить 500 * 240, что более эффективно - умножить их или считать от 1 до тех пор, пока вы не найдете правильный ответ?

Answer 3

Вот некоторые общие оптимизации, о которых следует помнить. Размещенный код обрабатывает все это, но вот общие правила, которые могут помочь при будущих проблемах:

1) если вы уже проверили z = 995, y = 990, вам не нужно проверять z = 990, y = 995. Грег Линд справляется с этим правильно

2) Вы вычисляете произведение z * y, а затем запускаете x в огромном диапазоне и сравниваете это значение с y * z. Например, вы только что вычислили 900 * 950, а затем запустили x от 1000 до 1M и посмотрите, если x = 900 * 950. Вы видите проблему с этим?

3) Кроме того, что происходит со следующим кодом? (вот почему ваш код ничего не возвращает, но вы все равно не должны этого делать)

x = str(100)
y = 100
print x == y

4) Если вы выясните (3), вы будете печатать там много информации. Вам нужно найти способ сохранить максимальное значение и вернуть его только в конце.

5) Вот хороший способ решить ваши проблемы Эйлера:

if __name__ == "__main__":
    import time
    tStart = time.time()
    print "Answer = " + main()
    print "Run time = " + str(time.time() - tStart)

Answer 4

Ух ты, этот подход немного улучшен по сравнению с другими реализациями на этой странице, включая mine .

Вместо

• переходя по трехзначным коэффициентам строка за строкой (сначала делайте все y для x = 999, затем все y для x = 998 и т. Д.),

мы

• пройти по диагонали: сначала сделайте все x, y так, чтобы x + y = 999 + 999; затем сделайте все x, y такими, что x + y = 999 + 998; и т.д.

Нетрудно доказать, что на каждой диагонали, чем ближе x и y друг к другу, тем выше произведение. Таким образом, мы можем начать с середины, x = y (или x = y + 1 для нечетных диагоналей) и по-прежнему выполнять те же оптимизации короткого замыкания, что и раньше. И поскольку мы можем начать с самых высоких диагоналей, которые являются самыми короткими, мы, вероятно, найдем самый высокий квалификационный палиндром гораздо раньше.

maxFactor = 999
minFactor = 100

def biggest():
    big_x, big_y, max_seen, prod = 0, 0, 0, 0

    for r in xrange(maxFactor, minFactor-1, -1):
        if r * r < max_seen: break

        # Iterate along diagonals ("ribs"):

        # Do rib x + y = r + r
        for i in xrange(0, maxFactor - r + 1):
            prod = (r + i) * (r - i)

            if prod < max_seen: break

            if is_palindrome(prod):
                big_x, big_y, max_seen = r+i, r-i, prod

        # Do rib x + y = r + r - 1
        for i in xrange(0, maxFactor - r + 1):
            prod = (r + i) * (r - i - 1)

            if prod < max_seen: break

            if is_palindrome(prod):
                big_x, big_y, max_seen = r+i,r-i-1, prod

    return big_x, big_y, max_seen

# biggest()
# (993, 913, 906609)

Улучшение фактора почти 3

Вместо того, чтобы вызывать is_palindrome () 6124 раза, теперь мы вызываем его только 2228 раз. И общее накопленное время возросло с 23 мс до 9!

Мне все еще интересно, существует ли совершенно линейный (O (n)) способ генерирования списка произведений из двух наборов чисел в порядке убывания. Но я очень доволен приведенным выше алгоритмом.

Answer 5

вместо того, чтобы перечислять все произведения трехзначных чисел (~ 900 ^ 2 итерации), перечислите все 6- и 5-значные палиндромы (это занимает ~ 1000 итераций); затем для каждого палиндрома решить, может ли он быть представлен продуктом двух трехзначных чисел (если это невозможно, он должен иметь четырехзначный простой множитель, так что это довольно легко проверить).

также вы спрашиваете о проблеме № 4, а не № 3.

Answer 6

сравнение строки с целым числом в

x == z*y

есть и логические ошибки

начать в обратном порядке range(999, 99, -1). это будет более эффективным. удалить третий цикл и второе сравнение в целом.

Answer 7

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

Answer 8

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

largest = 0
for a in range(100, 1000):
    for b in range(100, 1000):
        c = a * b
        if str(c) == ''.join(reversed(str(c))):
            largest = max(largest, c)
print(largest)

Answer 9

Это добавляет пару оптимизаций к хорошему решению @ GreggLind, сокращая время выполнения в два раза:

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

def biggest():
    big_x, big_y, max_seen = 0,0, 0
    for x in xrange(999,99,-1):
        # Optim. 1: Nothing in any row from here on can be bigger.
        if x*x < max_seen: break  

        for y in xrange(x, 99,-1):  # so we don't double count   
            # Optim. 2: break, not continue
            if x*y < max_seen: break  # since we're decreasing, 
                                # nothing else in the row can be bigger

            if is_palindrome(x*y):
                big_x, big_y, max_seen = x,y, x*y

    return big_x,big_y,max_seen

biggest()
# (993, 913, 906609)

Линия

if x*x < max_seen: break

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

Это не уменьшает количество раз, которое мы вызываем is_palindrome(), но означает гораздо меньшее количество итераций внешнего цикла. Значение x, на которое он разбивается, равно 952, поэтому мы исключили проверку 853 строк (хотя и «меньших», благодаря другим break).

Я также заметил, что

if x*y < max_seen: continue

должно быть

if x*y < max_seen: break

Мы пытаемся замкнуть всю строку, а не только текущую итерацию внутреннего цикла.

Когда я запускал этот скрипт с использованием cProfile , совокупное время для biggest() составляло в среднем около 56 мсек до оптимизации. Оптимизация сократилась до 23 мсек. Любая оптимизация принесла бы большую часть этого улучшения, но первая немного более полезна, чем вторая.

Answer 10

Вот мое решение:

polindroms = [(x, y, x * y) for x in range(100, 999) for y in range(100, 999) if str(x * y) == str(x * y)[::-1]]
print max(polindroms, key = lambda item : item[2])