Pourquoi est-ce simple script Python ne révèle la réponse incorrecte?

Question

Je travaille à nouveau sur le projet Euler, ce problème de temps # 4. Le point de ce script est de trouver le plus grand produit palindrome de deux nombres à trois chiffres. Je pensais qu'il était assez facile à résoudre, mais je reçois une réponse qui est trop faible. Plus précisément, je reçois 580085, et la réponse est 906609.

Quelqu'un pourrait-il me dire ce que ce sujet est incorrect?

#!/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

Votre code ne fait pas sûr qu'il imprime le plus grand produit, car il pourrait plus tard être un plus petit produit qui le remplace. Pour résoudre ce problème, t initialize à zéro, et remplacer votre état avec

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

ou de manière équivalente,

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

Modifier : Correction de problèmes int / chaîne ci-dessus. Il est un peu plus propre pour éviter la conversion en chaîne et revenir à int comme celui-ci si:

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 2

Voici une façon délicate mais correcte de le faire en une seule expression ...:

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])

La partie la plus délicate est la clause de for p unique élément qui joue le rôle d'une cession (juste pour arrêter recalcul ce produit à plusieurs reprises; -).

Notez que la réponse acceptée est erronée (comme plusieurs autres), car il cherche la string "max", qui est différent de int max - essayez de l'exécuter, et vous verrez -)

Answer 3

Le problème est de trouver le plus grand palindrome. Vous avez rien ici pour trouver le plus grand, tout simplement le dernier. Vous supposiez le dernier serait le plus grand, mais ce n'est pas parce que vous examiniez la place entière ZXZ des possibilités.

Par exemple, vous envisagez de 200 * 101 après que vous avez examiné 101 * 999.

Answer 4

En raison de la façon dont vous utilisez les deux pour les boucles que vous allez obtenir le numéro avec la plus grande valeur de x, pas le plus grand produit.

906609 = 993 * 913

Alors x garde incrémenter et la prochaine palindrome est:

580085 = 995 * 583

Vous avez besoin d'une variable pour garder la trace des plus importants que vous avez trouvé Palindrome.

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

Vous devez ajouter un chèque si celui que vous avez trouvé est plus grand que celui que vous avez déjà.

Answer 6

Je vais ajouter que vous pouvez vous faire gagner du temps dans ce test. Tous les 6 chiffres palindromes doit être divisible par 11. Par conséquent, au moins l'un des facteurs doit être divisible par 11.