Cómo averiguar todos los números palindrómicos

Solución:

Revierte tu razonamiento. No intente encontrar estos números, sino créelos. Simplemente puede tomar cualquier número y reflejarlo (que siempre tiene una longitud par) y para ese mismo número simplemente agregue 0..9 en el medio (para los números con longitud impar).

Generando todos los palíndromos hasta un límite específico.

public static Set<Integer> allPalindromic(int limit) {

    Set<Integer> result = new HashSet<Integer>();

    for (int i = 0; i <= 9 && i <= limit; i++)
        result.add(i);

    boolean cont = true;
    for (int i = 1; cont; i++) {
        StringBuffer rev = new StringBuffer("" + i).reverse();
        cont = false;
        for (String d : ",0,1,2,3,4,5,6,7,8,9".split(",")) {
            int n = Integer.parseInt("" + i + d + rev);
            if (n <= limit) {
                cont = true;
                result.add(n);
            }
        }
    }

    return result;
}

Prueba de palindromicidad

Usando cadenas

public static boolean isPalindromic(String s, int i, int j) {
    return j - i < 1 || s.charAt(i) == s.charAt(j) && isPalindromic(s,i+1,j-1);
}

public static boolean isPalindromic(int i) {
    String s = "" + i;
    return isPalindromic(s, 0, s.length() - 1);
}

Usando enteros

public static boolean isPalindromic(int i) {
    int len = (int) Math.ceil(Math.log10(i+1));
    for (int n = 0; n < len / 2; n++)
        if ((i / (int) Math.pow(10, n)) % 10 !=
            (i / (int) Math.pow(10, len - n - 1)) % 10)
            return false;
    return true;
}

Hay un enfoque de fuerza bruta, que recorre todos los números y verifica si son palíndromos o no. Para verificar, invierta el número y compare. La complejidad debe ser O (n log10 (n)). [ Not that log10() matters, but for sake of completeness. ]

Otro es generar palíndromos según el número de dígitos. Digamos que tienes que generar palíndromos de 5 dígitos, son de la forma ABCBA, así que simplemente recorre 0-9 y llena todas las posiciones. Ahora, si ha generado palíndromos por debajo de 10 ^ 4, genere palíndromos de 1, 2, 3 y 4 dígitos.

Escribí códigos C ++ rápidos (y sucios) para probar la velocidad de ambos algoritmos (palíndromo de 8 dígitos). Fuerza bruta: Ideone. (3.4s) Mejor algoritmo: Ideone. (0s)

He eliminado las declaraciones impresas, porque Ideone no permite esta gran cantidad de datos en la salida.

En mi computadora los tiempos son:

Brute force:
real    0m7.150s
user    0m7.052s
Better algorithm:
real    0m0.024s
user    0m0.012s

Sé que ha mencionado el lenguaje como Java, pero no sé Java y estos códigos simplemente le muestran la diferencia entre los algoritmos, y puede escribir su propio código Java.

PD: He probado mi código para palíndromos de 8 dígitos con fuerza bruta, no puedo estar seguro de si produce un error por encima de los 8 dígitos, aunque el enfoque utilizado es general. Además, me hubiera gustado dar los enlaces al código en los comentarios, ya que el enfoque correcto ya se menciona, pero no tengo los privilegios necesarios.

---

---

Utiliza Nuestro Buscador