¿Cómo puedo optimizar mi horrible código para encontrar el palíndromo más alto de un número de 3 dígitos?

Question

Esto es lo que he escrito hasta ahora.Se compila y, hasta donde yo sé, debería "funcionar", ¡si le dieras a tu computadora una cantidad infinita de tiempo para calcular la respuesta!

Me preguntaba si alguien podría darme una manera de optimizar esto para que mi programa me diga el número palindrómico más alto (el mismo tanto hacia adelante como hacia atrás, por ejemplo, 91 * 99 = 9009;) formado al multiplicar dos cualesquiera. números de tres dígitos.

 public class HighestPalindrome {
     public static void main(String[] args) {
    int number=0;
    int answer=0;

    search:
    for(int LoopOfFirstNumber=999;LoopOfFirstNumber<=100;LoopOfFirstNumber -= 3){
      for(int LoopOfSecondNumber=LoopOfFirstNumber;LoopOfSecondNumber<=100;LoopOfSecondNumber-=3)
      {
        number = LoopOfFirstNumber * LoopOfSecondNumber;
        if (number == reverse(number))
         {
          answer=number;
          System.out.println(answer);
          break search;
         }
      }
    }
  }

     //The code after this works fine, I believe. It will reverse any number given very quickly, I think the problem
     //is above....with the two for loops!

    private static int reverse(int n, int r) {
      if (n == 0) return r;
      System.out.println("This iteration returns " + n/10 + " and  " + 10*r+n%10);
      return reverse(n/10, 10*r+n%10);
    }

    public static int reverse(int n) {
     return reverse(n, 0);
    }

Answer 1

Como ya adivinado, el problema está en el bucle anidado. Trate de averiguar algunas propiedades de los números. La multiplicación de dos números de tres dígitos siempre dará un número que tiene cinco o seis dígitos. Desde que busca el número más alto, entonces se espera que sea de seis dígitos número comenzando con el número 9 y puesto que es capicúa, es probable que termina con el número 9 también. En pocas palabras, los números que está esperando en la forma 9xyyx9.

A continuación, no todos los pares de números se puede multiplicar y terminan con el número 9. xx3 y xx3 dará xxxxx9, también lo hace xx1 y XX9; pero XX1 y xx8 nunca se multiplican a xxxxx9.

Encuentre inmuebles como estos, y tratar de filtro que las probabilidades se pueden implementar fácilmente en su búsqueda.

Answer 2

Su for las condiciones del bucle son incorrectas:

LoopOfFirstNumber<=0

debería ser:

LoopOfFirstNumber>=100

Deberías continuar haciendo el bucle hasta que tus contadores de bucle estén >= 100 cuál es el número más pequeño de 3 dígitos.

Además, una vez que encuentres un palíndromo, debes romper ambos bucles.Actualmente estás rompiendo solo el bucle interno.Para solucionar este problema es necesario utilizar descanso etiquetado.

Answer 3

El interior de bucle no tiene que comenzar con 999, se puede comenzar con LoopOfSecondNumber = LoopOfFirstNumber:

Vayamos asumen que hay una solución para los que LoopOfSecondNumber = x > LoopOfFirstNumber = y. Entonces habría una solución en la que se conectan los dos números:. LoopOfFirstNumber = x, LoopOfSecondNumber = y => Esta solución así habría sido presentada anteriormente en el bucle exterior ya

Esto no le traerá mucha optimización, sin embargo, en el mejor de los casos que le lleva la mitad de las veces el código original tomó.

Answer 4

¿Por qué no hacer frente desde el otro lado?

Crear un conjunto de todos los números palíndromo a partir de 1000000 (1000 * 1000) y trabajando hacia abajo, debería ser bastante fácil.

Y luego factorizar ellos - aunque supongo que vas a necesitar un algoritmo para esto: - (