Intrigué par le problème palindromique du produit

Question

J'ai appris Ruby, alors j'ai pensé m'essayer à certains des puzzles du projet Euler.Malheureusement, je n'ai réussi qu'au problème 4...

Le problème 4 est le suivant :

Un numéro palindromique lit la même chose dans les deux sens.Le plus grand palindrome fabriqué à partir du produit de deux nombres à 2 chiffres est de 9009 = 91 × 99.

Trouvez le plus grand palindrome fabriqué à partir du produit de deux numéros à 3 chiffres.

J'ai donc pensé que je passerais de 999 à 100 dans une boucle for imbriquée et que je ferais un test pour le palindrome, puis que je sortirais des boucles lorsque j'aurais trouvé la première (qui devrait être la plus grande) :

final=nil
range = 100...1000
for a in range.to_a.reverse do
  for b in range.to_a.reverse do
    c=a*b
    final=c if c.to_s == c.to_s.reverse
    break if !final.nil?
  end
  break if !final.nil?
end
puts final

Cela génère un palindrome 580085, mais apparemment, ce n'est pas le produit le plus élevé de deux nombres à trois chiffres dans la plage.Étrangement, le même code réussit à renvoyer 9009, comme dans l'exemple, si je change la plage en 10...100.

• Quelqu'un peut-il me dire où je vais mal?
• En outre, y a-t-il une meilleure façon de sortir de la boucle interne?

Merci

Answer 1

Vous testez 999 * (999 ... 100), puis 998 * (999 ... 100)

Par conséquent, vous testera 999 * 500 avant de tester 997 * 996.

Alors, comment vous nous constatons que bon nombre?

Notons d'abord la multiplication est réfléchissante, a * b == b * a, donc b n'a pas besoin d'aller de 999 ... 0 à chaque fois, à ... 0.

Lorsque vous trouvez un Palindrone, ajoutez les deux facteurs ensemble et sauver la somme (les deux facteurs sauver aussi)

Dans la boucle, si (a + b) est toujours inférieure à la somme enregistrée, abandonner la boucle intérieure et se déplacer à l'autre a. Quand tombe en dessous de la somme / 2, aucune valeur future que vous pourriez trouver serait plus élevé que celui que vous avez déjà trouvé, vous avez terminé.

Answer 2

Le problème est que vous pourriez trouver un palindrome pour un a de 999 et un b de 200, mais vous casser trop vite, de sorte que vous ne verrez jamais qu'il y en a un pour 998 * 997 (numéros seulement, par exemple).

Vous devez soit regarder pour tous les palindromes ou une fois que vous trouverez le premier, ensemble qui b comme minimum lié et continuer à regarder à travers la boucle a.

Answer 3

En ce qui concerne la deuxième question, mon conseil est d'aborder le problème de manière plus fonctionnelle, de manière procédurale. Ainsi, plutôt que de boucle, vous pouvez essayer de « décrire » votre problème fonctionnel, et que Ruby fait le travail:

• De toutes les paires de nombres à 3 chiffres,
  • select que celles dont le produit est un palindrome,
    • et trouver celui avec le plus grand produit

Bien que cette approche peut ne pas donner la plus efficace des solutions, il peut vous apprendre quelques expressions idiomatiques Ruby.

Answer 4

Considérez les chiffres de P - qu'ils soient x, y et z. P doit être d'au moins 6 chiffres depuis le palindrome 111111 = 143 × 777 - le produit de deux nombres entiers à 3 chiffres. Puisque P est palindrome:

P=100000x + 10000y + 1000z + 100z + 10y + x
P=100001x + 10010y + 1100z
P=11(9091x + 910y + 100z)

Depuis le 11 est premier, au moins l'un des nombres entiers a ou b doit avoir un facteur de 11. Donc, si un est divisible par 11 alors nous savons b doit être. Grâce à ces informations, nous pouvons déterminer quelles sont les valeurs de b, nous vérifions en fonction d'un.

Answer 5

C # Mise en œuvre:

using System;

namespace HighestPalindrome
{
    class Program
    {
        static void Main(string[] args)
        {
            int i, j;
            int m = 1;
            bool flag = false;

            while (true)
            {
                if (flag) j = m + 1;
                else j = m;

                for (i = m; i > 0; i--)
                {
                    Console.WriteLine("{0} * {1} = {2}", 1000 - i, 1000 - j, (1000 - i) * (1000 - j));
                    j++;

                    //--- Palindrome Check ------------------------------

                    int number, temp, remainder, sum = 0;
                    number = temp = (1000 - i) * (1000 - j);

                    while (number > 0)
                    {
                        remainder = number % 10;
                        number /= 10;
                        sum = sum * 10 + remainder;
                    }

                    if (sum == temp)
                    {
                        Console.WriteLine("Highest Palindrome Number is - {0} * {1} = {2}", 1000 - i, 1000 - j, temp);
                        Console.ReadKey();
                        return;
                    }

                    //---------------------------------------------------
                }

                if (flag)
                    m++;
                flag = !flag;
            }

        }
    }
}

Answer 6

L'erreur est que vous assumez que si vous trouvez palindrome avec la plus grande valeur a il donnera le meilleur produit, il est pas vrai. La solution est de maintenir la valeur de max_product et mettre à jour contre la solution que vous trouvez.

Answer 7

Je peux répondre à votre première question: Vous devez trouver le produit le plus élevé, et non le produit contenant le plus grand facteur. En d'autres termes a * b pourrait être supérieure à c * d même si c > a > b.

Answer 8

Vous enfreignez le premier palindrome vous venez, pas nécessairement le plus grand.

Dites que vous avez A, B, C, D, E. Vous testez E * A avant de tester D * C.

Answer 9

ar=[]
limit = 100..999
for a in limit.to_a.reverse do
  for b in (100..a).to_a.reverse do
    c=a*b
    if c.to_s == c.to_s.reverse
      palndrm=c 
      ar << palndrm
    end  
  end
end
print ar
print"\n"
puts ar.max
puts ar.min 

Answer 10

une mise en œuvre:

max = 100.upto(999).inject([-1,0,0]) do |m, a|
  a.upto(999) do |b|
    prod = a * b
    m = [prod, a, b] if prod.to_s == prod.to_s.reverse and prod > m[0]
  end
  m
end
puts "%d = %d * %d" % max

imprime 906609 = 913 * 993

Answer 11

La chose principale est de passer par toutes les valeurs possibles. Ne pas essayer de casser quand vous trouvez la première réponse juste commencer par une meilleure réponse de zéro puis essayer toutes les combinaisons et garder à jour le mieux. La chose secondaire est d'essayer de réduire l'ensemble des « toutes les combinaisons ».

Une chose que vous pouvez faire est de limiter votre boucle interne à des valeurs inférieures ou égales à un (depuis b == b a). Cela met la plus grande valeur de votre équation toujours dans un et réduit considérablement le nombre de valeurs que vous avez à tester.

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

La prochaine chose que vous pouvez faire est de sortir de la boucle interne chaque fois que le produit est inférieur à la meilleure valeur actuelle.

c = a*b
next if c < best

Ensuite, si vous allez passer par tous de toute façon il n'y a aucun avantage à passer par eux dans le sens inverse. En commençant par le haut de gamme, il faut un certain temps avant de trouver un nombre palindrome et par conséquent, il faut un certain temps pour réduire votre jeu de recherche. Si vous commencez en bas, vous commencez à augmenter la minorant rapidement.

for a in range.to_a do
    for b in (100..a).to_a do

Mes tests montrent que de toute façon que vous essayez quelques 405K paires cependant. Alors que diriez-vous de penser à ce problème d'une manière différente. Quel est le plus grand produit possible de deux nombres à 3 chiffres? 999 * 999 = 998001 et le plus petit est 100 * 100 = 10000. Que diriez-vous que nous prenons l'idée que vous aviez de briser sur la première réponse, mais l'appliquer à une autre plage, qu'être 998001 à 10000 (ou 999 * 999 à 100 * 100).

for c in (10000...998001).to_a.reverse do

Nous arrivons à un palindrome après seulement 202 essais ... le problème est qu'il est pas un produit de deux nombres à 3 chiffres. Alors maintenant, nous devons vérifier si le palindrome que nous avons trouvé est un produit de 2 nombres à 3 chiffres. Dès que nous trouvons une valeur dans la plage qui est un palindrome et un produit de deux nombres à 3 chiffres nous fait. Mes tests montrent que nous trouvons le plus haut palindrome qui répond à l'exigence après moins de 93k tests. Mais puisque nous avons les frais généraux de vérifier que tous les palindromes à ce moment-là étaient des produits de deux nombres à 3 chiffres, il ne peut être plus efficace que la solution précédente.

permet de revenir à l'amélioration aller originale.

for a in range.to_a.reverse do
    for b in (100..a).to_a.reverse do

Nous sommes des lignes en boucle puis colonnes et essayer d'être efficace en détectant un point où l'on peut aller à la ligne suivante, car les trys supplémentaires sur la ligne actuelle ne pouvait pas être mieux que notre meilleur courant. Et si, au lieu d'aller vers le bas les lignes, nous allons à travers les diagonales?

Étant donné que les produits deviennent plus petits en diagonale par diagonale vous pouvez vous arrêter dès que vous trouvez un numéro de palindome. Ceci est une solution vraiment efficace, mais avec une mise en œuvre plus complexe. Il se trouve cette méthode trouve le plus palindrome après un peu plus de 2200 trys.

Answer 12

Voici ce que je suis venu avec Ruby:

def largest_palindrome_product(digits)
  largest, upper, lower = 0, 10**digits - 1, 10**(digits - 1)

  for i in upper.downto(lower) do
    for j in i.downto(lower) do
      product = i * j
      largest = product if product > largest && palindrome?(product)
    end
  end
  largest
end

Et voici la fonction de vérifier si le nombre est un palindrome:

def palindrome?(input)
  chars = input.to_s.chars
  for i in 0..(chars.size - 1) do
    return false if chars[i] != chars[chars.size - i - 1]
  end
  true
end

Je pense qu'il ya probablement une solution plus efficace là-bas, cependant.

Answer 13

Pour ce problème, comme nous recherchons le palindrome le plus élevé, j'ai supposé qu'il commencerait par un 9.Finissant ainsi par un 9 (palindrome).

si vous faites attention, pour obtenir un nombre finissant par 9, vous ne pouvez l'obtenir qu'avec des nombres finissant par 9 et 1, 3 et 3, 7 et 7.

Il est alors inutile de vérifier les autres valeurs (par exemple 999*998 car cela ne se terminera pas par un 9).

En partant de 999 et 991, vous pouvez ensuite soustraire 10 à 991, en essayant 999 et 981 etc...Vous faites la même chose avec 993 et ​​993...993 * 983 Idem avec 997 * 997 puis 997 * 987, etc. Vous n'avez pas besoin d'aller plus loin que 900 ou 10 ^ 4 - 10 ^ 3 car vous pouvez être sûr que le plus élevé sera avant.

int PB4_firstTry(int size)
{
    int nb1 = (int)pow(10.0,size+1.0) - 1, nb2 = (int)pow(10.0,size+1.0) - 1;
    int pal91 = getFirstPalindrome(size,9,1);
    int pal33 = getFirstPalindrome(size,3,3);
    int pal77 = getFirstPalindrome(size,7,7);

    int bigger1 = (pal91 > pal33) ? pal91 : pal33;
    return (bigger1 > pal77) ? bigger1 : pal77;
}

int getFirstPalindrome(int size,int ending1,int ending2)
{
    int st1 =  (int)pow(10.0,size+1.0) - 10 + ending1;
    int comp = st1 - pow(10.0,size);
    int st2 =  (int)pow(10.0,size+1.0) - 10 + ending2;
    int answer = -1;
    while (st1 > comp)
    {
        for (int i = st2; i > comp && st1*i > answer; i-=10)
        {
            if (PB4_isPalindrome(st1*i))
                answer = st1*i;
        }
        st1 -= 10;
    }
    return answer;
}

bool PB4_isPalindrome(int number)
{
    std::string str = intToString(number);
    for (int i = 0; i < (int)(str.length() / 2); i++)
    {
        if (str[i] != str[str.length() - 1 - i])
            return false;
    }
    return true;
}

std::string intToString(int number)
{
    std::ostringstream convert;
    convert << number;
    return convert.str();
}

Bien sûr, cela fonctionne pour des facteurs à 4 chiffres, etc.