récursive - palindrome python 3



Numéro de problème Euler#4 (10)

Essayez de calculer x à partir du produit de z et y plutôt que de vérifier chaque nombre de 1 à un million. Pensez-y: si on vous demandait de calculer 500 * 240, ce qui est plus efficace - en les multipliant, ou en comptant à partir de 1 jusqu'à ce que vous trouviez la bonne réponse?

En utilisant Python, j'essaie de résoudre le problème # 4 des problèmes de Project Euler . Quelqu'un peut-il me dire ce que je fais de façon incorrecte? Le problème est de trouver le plus grand palindrome fabriqué à partir du produit de deux nombres à trois chiffres . Voici ce que j'ai jusqu'ici.

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

C'est ce que j'ai fait en Java:

public class Euler0004
{
    //assumes positive int
    static boolean palindrome(int p)
    {
        //if there's only one char, then it's
        //  automagically a palindrome
        if(p < 10)
            return true;

        char[] c = String.valueOf(p).toCharArray();

        //loop over the char array to check that
        //  the chars are an in a palindromic manner
        for(int i = 0; i < c.length / 2; i++)
            if(c[i] != c[c.length-1 - i])
                return false;

        return true;
    }


    public static void main(String args[]) throws Exception
    {
        int num;
        int max = 0;

        //testing all multiples of two 3 digit numbers.
        // we want the biggest palindrome, so we
        // iterate backwards
        for(int i = 999; i > 99; i--)
        {
            // start at j == i, so that we
            //  don't calc 999 * 998 as well as
            //  998 * 999...
            for(int j = i; j > 99; j--)
            {
                num = i*j;

                //if the number we calculate is smaller
                //  than the current max, then it can't
                //  be a solution, so we start again
                if(num < max)
                    break;

                //if the number is a palindrome, and it's
                //  bigger than our previous max, it
                //  could be the answer
                if(palindrome(num) && num > max)
                    max = num;
            }
        }

        //once we've gone over all of the numbers
        //  the number remaining is our answer
        System.out.println(max);

    }
}

Answer #2

Quelques problèmes d'efficacité

  1. commencer en haut (puisque nous pouvons l'utiliser en sautant beaucoup de calculs)
  2. ne double pas
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 #3

Si votre programme est lent, et que vous avez des boucles imbriquées comme ceci:

for z in range(100, 1000):
    for y in range(100, 1000):
        for x in range(1, 1000000):

Ensuite, une question que vous devriez vous poser est: "Combien de fois le corps de la boucle la plus profonde sera-t-il exécuté?" (le corps de votre boucle la plus interne est le code qui commence par: x = str(x) )

Dans ce cas, c'est facile à comprendre. La boucle externe sera exécutée 900 fois. Pour chaque itération, la boucle du milieu sera également exécutée 900 fois, soit 900 × 900, soit 810 000 fois. Ensuite, pour chacune de ces 810 000 itérations, la boucle interne exécutera elle-même 999 999 fois. Je pense que j'ai besoin de beaucoup de temps pour calculer ça:

>>> 900*900*999999
809999190000L

En d'autres termes, vous faites votre chèque palindrome presque 810 milliards de fois. Si vous voulez faire la limite recommandée par Project Euler d'une minute par problème, vous pourriez vouloir optimiser un peu :-) (voir le commentaire de David)


Answer #4

chaîne de comparaison avec un entier dans

x == z*y

il y a aussi des erreurs logiques

commencer dans la range(999, 99, -1) ordre inverse range(999, 99, -1) . ce sera plus efficace. enlever la troisième boucle et la deuxième comparaison complètement.


Answer #5

plutôt que d'énumérer tous les produits de nombres à trois chiffres (~ 900 ^ 2 itérations), énumérer tous les palyndromes de 6 et 5 chiffres (cela prend ~ 1000 itérations); ensuite, pour chaque palyndrome, décidez s'il peut être représenté par un produit de deux nombres à trois chiffres (s'il ne le peut pas, il devrait avoir un facteur premier à quatre chiffres, ce qui est donc facile à tester).

De plus, vous posez des questions sur le problème n ° 4, pas sur le n ° 3.


Answer #6

Voici ma solution:

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

Answer #7

Cela ajoute quelques optimisations à la bonne solution de @ GreggLind, réduisant de moitié le temps d'exécution:

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)

La ligne

if x*x < max_seen: break

signifie qu'une fois que nous arrivons au point où x est inférieur à sqrt du plus grand palindrome encore vu, non seulement n'avons-nous pas besoin d'enquêter sur d'autres facteurs sur cette rangée; nous n'avons même plus besoin d'enquêter sur d'autres lignes, car toutes les lignes restantes commencent à partir d'un nombre inférieur à la valeur actuelle de x.

Cela ne réduit pas le nombre de fois que nous appelons is_palindrome() , mais cela signifie beaucoup moins d'itérations de la boucle externe. La valeur de x qu'il casse est 952, donc nous avons éliminé la vérification de 853 lignes (bien que les plus petites, grâce à l'autre break ).

J'ai aussi remarqué que

if x*y < max_seen: continue

devrait être

if x*y < max_seen: break

Nous essayons de court-circuiter toute la ligne, pas seulement l'itération actuelle de la boucle interne.

Quand j'ai exécuté ce script en utilisant cProfile , le temps cumulé pour le biggest() était d'environ 56 msec en moyenne, avant les optimisations. Les optimisations l'ont réduit à environ 23 msec. Soit l'optimisation seule fournisse la plus grande partie de cette amélioration, mais la première est légèrement plus utile que la seconde.


Answer #8

Voici une solution générale efficace (~ 5x plus rapide que les autres que j'ai vu):

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 #9

Waouh, cette approche améliore un peu plus les autres implémentations sur cette page, y compris la mienne .

Au lieu de

  • descendre les facteurs à trois chiffres ligne par ligne (tout d'abord y pour x = 999, puis tout y pour x = 998, etc.),

nous

  • descendez les diagonales: faites d'abord tous les x, y tels que x + y = 999 + 999; alors faites tout x, y tel que x + y = 999 + 998; etc.

Il n'est pas difficile de prouver que sur chaque diagonale, plus x et y sont proches l'un de l'autre, plus le produit est élevé. On peut donc partir du milieu, x = y (ou x = y + 1 pour les diagonales impaires) et faire encore les mêmes optimisations de court-circuit qu'avant. Et parce que nous pouvons partir des diagonales les plus hautes, qui sont les plus courtes, nous sommes susceptibles de trouver le palindrome de qualification le plus élevé beaucoup plus tôt.

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)

Un facteur de presque-3 amélioration

Au lieu d'appeler is_palindrome () 6124 fois, nous l'appelons maintenant seulement 2228 fois. Et le temps total accumulé est passé d'environ 23 msec à environ 9!

Je me demande toujours s'il existe une manière parfaitement linéaire (O (n)) de générer une liste de produits de deux séries de nombres dans l'ordre décroissant. Mais je suis assez content de l'algorithme ci-dessus.





palindrome