Почему этот простой скрипт Python показывает неправильный ответ?

Question

Я снова работаю над Project Euler, на этот раз проблема № 4. Смысл этого сценария - найти самое большое палиндромное произведение из двух трехзначных чисел. Я думал, что это было довольно просто решить, но я получаю ответ, который слишком низок. Более конкретно, я получаю 580085, а ответ - 906609.

Может кто-нибудь сказать мне, что это неправильно?

#!/usr/bin/env python
# encoding: utf-8
"""
P4.py

Created by Andrew Levenson on 2010-06-29.
Copyright (c) 2010 __MyCompanyName__. All rights reserved.
"""

import sys
import os


def main():
    for x in range(100, 1000):
        for y in range(100, 1000):
            z = str( x * y )
            s = str( z[::-1] ) # Reverse z
            if z == s:
                t = z
    print t


if __name__ == '__main__':
    main()

Answer 1

Вот хитрый, но правильный способ сделать это в одном выражении ...:

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

Сложная часть - это пункт for p, состоящий из одного элемента, который играет роль присваивания (просто чтобы прекратить повторный расчет этого продукта несколько раз; -).

Обратите внимание, что принятый ответ неверен (как и некоторые другие), потому что он ищет строку"max", которая отличается от int max - попробуйте запустить это, и вы увидите! -)

Answer 2

Ваш код не гарантирует, что он печатает самый большой продукт, так как позже может быть продукт меньшего размера, который заменит его.Чтобы исправить это, инициализируйте t равным нулю и замените ваше условие на

if z==s and int(z)>t:
    t = int(z)

или, что эквивалентно,

if z==s:
    t = max(t,int(z))

Редактировать : исправлены проблемы типа int / stringвыше.Это немного чище, чтобы избежать преобразования в строку и обратно в int следующим образом:

def isPalindrome(x):
    s = str(x)
    return s == s[::-1]

t = 0
for x in range(100, 1000):
    for y in range(100, 1000):
        z = x * y
        if isPalindrome(z) and z > t:
            t = z
print t

Answer 3

Проблема в том, чтобы найти самый большой палиндром. У вас нет ничего, чтобы найти самое большое, просто последнее. Вы предполагали, что последний будет самым большим, но это не так, потому что вы изучаете весь квадрат возможностей ZxZ.

Например, вы рассматриваете 200 * 101 после того, как вы рассмотрели 101 * 999.

Answer 4

Из-за того, как вы используете петли 2 для числа, вы получите число с наибольшим значением x, а не с самым большим продуктом.

906609 = 993 * 913

Затем x продолжает увеличиваться, и следующий палиндром будет:

580085 = 995 * 583

Вам нужна переменная для отслеживания самого большого из найденных палиндромов.

def main():
    largest = 0
    for x in range(100, 1000):
        for y in range(100, 1000):
            z = str( x * y )
            s = str( z[::-1] ) # Reverse z
            if z == s:
                t = int(z)
                if t > largest:
                    largest = t
    print largest

Answer 5

Вам нужно добавить проверку, если найденная вами больше той, что у вас уже есть.

Answer 6

Я добавлю, что вы можете сэкономить немного времени в этом тесте. Все 6-значные палиндромы должны делиться на 11. Поэтому хотя бы один из факторов должен делиться на 11.