martes, octubre 12, 2010

Mejorando la generación de números vampiros

En la siguiente versión del método generarVampiros, se va a modificar la salida con tres parámetros booleanos que permitirán generar hasta 8 listas diferentes teniendo en cuenta si los factores que se multiplican para formar el número vampiro tienen el mismo número de dígitos (vMitad); si dichos factores son números primos o no (vPrimo); y si tanto los factores como el número generado no tienen dígitos repetidos (vUnico).

De esta manera, la ejecución del método generarVampiros(8, true, true, true) generará solamente números vampiros de 8 dígitos formados por la multiplicación de dos números de 4 dígitos que sean primos y que no contengan dígitos repetidos. En este caso, la respuesta del programa es la siguiente:

10.349.527 = 2.579 x 4.013
10.429.753 = 2.309 x 4.517
17.204.359 = 2.309 x 7.451
18.647.023 = 2.741 x 6.803
54.918.067 = 5.801 x 9.467
64.781.293 = 7.691 x 8.423



public static Vector<String> generarVampiros(int digitos, boolean vMitad, 
                                             boolean vPrimo, boolean vUnico) {
        // vMitad: true para factores del mismo tamaño
        // vPrimo: true para factores primos
        // vUnico: true para factores sin dígitos repetidos
        Vector<Integer> va, vb, vc;
        Vector<String>  respuesta = new Vector<String>();
        long numFinal = (long) Math.pow(10,digitos)-1;    // último vampiro posible
        long numBase  = (long) Math.pow(10,digitos-1);    // primer vampiro posible
        long numMin   = (long) Math.pow(10,digitos/2-1);  // menor factor tamaño n/2
        long numMax   = (long) Math.pow(10,digitos/2)-1;  // mayor factor tamaño n/2
        long factorInicialA=0;
        long factorFinalA=0;
        long factorInicialB=0;
        long factorFinalB=0;
        if(vMitad) {
            factorInicialA = numMin;
            factorFinalA   = numMax;
        }
        else {
            factorInicialA = 1;
            factorFinalA   = numFinal;
        }
        for(long a = factorInicialA; a<=factorFinalA; a++) {
            if(vPrimo && !Algoritmos.esPrimoV6(a)) continue;
            va = vectorDigitos(a);
            if(vMitad) {
                factorInicialB=Math.max(a+1,numBase/a);
                factorFinalB=numMax;
            }
            else {
                factorInicialB = Math.max(a+1,numBase/a);
                factorFinalB = numFinal;
            }
            for(long b = factorInicialB; b<=factorFinalB; b++) {
                if(vPrimo && !Algoritmos.esPrimoV6(b)) continue;
                long c = a*b;
                if(c>numFinal) { b=numFinal; continue; }
                if(c<numBase) continue;
                vb = vectorDigitos(b);
                vc = vectorDigitos(c);
                if(vUnico) {
                    Set<Integer> sa = new TreeSet<Integer>();
                    Set<Integer> sc = new TreeSet<Integer>();
                    sa.addAll(va);
                    sa.addAll(vb);
                    sc.addAll(vc);
                    if(sc.size()==digitos && sa.equals(sc)) {
                        respuesta.add(String.format("%,12d = %,6d x %,6d",c, a,b));
                    }
                }
                else {
                    for(int x: va) vb.add(x);
                    Collections.sort(vb);
                    Collections.sort(vc);
                    if(vb.equals(vc)) {
                        respuesta.add(String.format("%,12d = %,6d x %,6d",c, a,b));
                    }
                }
            }
        }
        Collections.sort(respuesta);
        return respuesta;
    }

No hay comentarios.:

Publicar un comentario

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...