Interrogado sobre problema del producto palindrómica

Question

He estado aprendiendo Ruby, así que pensé que me gustaría probar mi mano en algunos de los proyectos de Euler rompecabezas. Vergonzosamente, sólo se lo hice a un problema 4 ...

Problema 4 es como sigue:

  

A capicúa lee el mismo   ambos sentidos. El mayor palíndromo hecho   a partir del producto de dos 2 dígitos   números es 9009 = 91 × 99.

     

Para la mayor palíndromo hecho de   el producto de dos números de 3 dígitos.

Así que pensé que le bucle por debajo de 999 a 100 en un anidado de bucle y hacer una prueba para el palíndromo y luego salir de los bucles cuando me encontré con el primero (que debe ser el más 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

Esto hace un palíndromo salida de 580.085, pero al parecer esto no es el más alto producto de dos números de tres dígitos dentro de la gama. Curiosamente, el mismo código tiene éxito para volver 9009, al igual que en el ejemplo, si cambio el rango de 10 ... 100.

• ¿Puede alguien decirme dónde voy mal?
• También, hay una manera más agradable de romper el bucle interno?

Gracias

Answer 1

Se están probando 999 * (999 ... 100), entonces 998 * (999 ... 100)

Por lo tanto usted estará probando 999 * 500 antes de probar 997 * 996.

Así que, cómo nos encontramos con que el número correcto?

En primer nota de la multiplicación es reflexivo, a * b == b * a, por lo que b no tiene por qué ir de 999 ... 0 cada vez, sólo un ... 0.

Cuando encuentre un palindrone, añadir los dos factores juntos y salvar a la suma (excepto los dos factores también)

Dentro del bucle, si (a + b) es siempre menor que la suma salvado, abandonar el bucle interno y pase a la siguiente a. Cuando cae por debajo de una suma / 2, sin valor futuro se podría encontrar sería mayor que la que ya hemos encontrado, por lo que ya está.

Answer 2

El problema es que es posible encontrar un palíndromo para una a de 999 y una b de 200, pero romper demasiado pronto, por lo que nunca se ve que hay una para 998 * 997 (números solo ejemplo).

Es necesario que sea mirada de todos los palíndromos o una vez que encuentre la primera, conjunto que b como su límite mínimo y continuar mirando a través del bucle a.

Answer 3

En cuanto a la segunda pregunta, mi consejo es abordar el problema en más funcional, de manera procedimental. Así, en lugar de bucle, es posible que trate de "describir" su problema funcionalmente, y dejar Rubí hace el trabajo:

• Desde todos los pares de números de 3 dígitos,
  • select sólo aquellos cuyo producto es un palíndromo,
    • y encontrar el uno con el producto más grande

A pesar de que este enfoque no puede rendir el más eficiente de las soluciones, puede enseñarle par de frases hechas Ruby.

Answer 4

Tenga en cuenta las cifras de P - es mejor que sean x, y, z. P debe ser al menos 6 dígitos de longitud desde el palíndromo 111.111 = 143 × 777 - el producto de dos números enteros de 3 dígitos. Puesto que P es palindrómico:

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

Desde el 11 es primo, al menos uno de los enteros A o B debe tener un factor de 11. Así que si a no es divisible por 11 entonces sabemos B debe ser. Con esta información podemos determinar qué valores de b, comprobamos dependiendo de a.

Answer 5

C # Aplicación:

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

El error es de asumir que si encuentra palindrom con mayor valor a se le dará al producto mayor que no es cierto. Solución es mantener el valor max_product y actualizarlo frente a una solución que encuentre.

Answer 7

puedo responder a su primera pregunta: ¿Es necesario encontrar el producto más alto, no el producto que contiene el factor más alto. En otras palabras a * b podría ser mayor que c * d incluso si c > a > b.

Answer 8

que está rompiendo en el primer palíndromo se llega a, no necesariamente el más grande.

Digamos que tienes A, B, C, D, E. Usted prueba E * A antes de probar 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

una aplicación:

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

impresiones 906609 = 913 * 993

Answer 11

Lo más importante es ir a través de todos los valores posibles. No trate de romper cuando se encuentra la primera respuesta acaba de empezar con una mejor respuesta de cero, entonces probar todas las combinaciones y mantener la actualización mejor. Lo secundario es tratar de reducir el conjunto de "todas las combinaciones".

Una cosa que puede hacer es limitar su bucle interno a valores menores o iguales a un (ya que un b == b a). Esto pone el valor más grande de su ecuación siempre en una y reduce sustancialmente el número de valores que tiene que prueba.

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

La siguiente cosa que puede hacer es romper el bucle interno cada vez que el producto es menos que el mejor valor actual.

c = a*b
next if c < best

A continuación, si vas a ir a través de todos modos no hay beneficio para ir a través de ellos a la inversa. Comenzando en la parte superior de la gama que toma un tiempo antes de encontrar un capicúa y como resultado se toma un tiempo para reducir el conjunto de búsqueda. Si se inicia en la parte inferior de comenzar a aumentar el límite inferior de forma rápida.

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

Mis pruebas muestran que de cualquier manera se intenta algunos pares 405K sin embargo. Entonces, ¿cómo pensar acerca del problema de una manera diferente. ¿Cuál es el producto más grande posible de números de dos dígitos 3? 999 * 999 = 998.001 y el más pequeño es 100 * 100 = 10000. ¿Qué tal si tomamos la idea que tenía de romper en la primera respuesta, pero lo aplicamos a un rango diferente, que siendo 998 001 a 10000 (o 999 * 999 a 100 * 100).

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

Llegamos a un palíndromo después de sólo 202 pruebas ... el problema es que no es un producto de dos números de 3 dígitos. Así que ahora tenemos que comprobar si el palíndromo que hemos encontrado es un producto de 2 números de 3 dígitos. Tan pronto como nos encontramos con un valor en el rango que es un palíndromo y un producto de dos números de 3 dígitos que hemos terminado. Mis pruebas muestran que encontramos el palíndromo más alto que cumpla con el requisito después de menos de 93k pruebas. Pero ya que tenemos la sobrecarga de comprobar que todos los palíndromos a ese punto fueron producto de dos números de 3 dígitos que puede no ser más eficiente que la solución anterior.

Así que permite realizar copias de ir a la mejora inicial.

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

Estamos bucle filas a continuación, columnas y tratando de ser eficiente mediante la detección de un punto en el que podemos pasar a la siguiente fila porque ningún trys adicionales en la fila actual no podría ser mejor que nuestro mejor esfuerzo actual. ¿Qué pasaría si, en vez de bajar las filas, vamos a través de las diagonales?

Dado que los productos se hacen más pequeños en diagonal por diagonal puede dejar tan pronto como se encuentre un número palindome. Esta es una solución muy eficiente, pero con una implementación más compleja. Resulta que este método encuentra el mayor palíndromo después de poco más de 2.200 trys.

Answer 12

Esto es lo que me ocurrió en 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

Y aquí está la función para comprobar si el número es un palíndromo:

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

Creo que es probable que haya una solución más eficiente por ahí, sin embargo.

Answer 13

Para este problema, ya que estamos buscando la más alta palindrom, supuse que sería empezar con un 9. Así que termina con un 9 (palindrom).

si se presta atención, para obtener un número acabado en un 9, sólo se puede conseguir con los números terminados en 9 y 1, 3 y 3, 7 y 7.

A continuación, es inútil para comprobar los otros valores (por ejemplo, 999 * 998, ya que no terminará con un 9).

A partir de 999 y 991, a continuación, puede restar 10 a 991, 999 y 981 tratando etc ... Usted hace lo mismo con 993 y 993 ... 993 * 983 misma con 997 * 997 * 997 y luego 987, etc. No es necesario ir más allá de 900 o 10 ^ 4 -. 10 ^ 3 como se puede estar seguro de la más alta tendrá ante sí

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();
}

Por supuesto, esto funciona para 4 dígitos de tamaño factores etc.