3

Buenas, he creado un código basado en binary search, que hace llamadas recursivas para encontrar un Integer que se pasa como parámetro(elemento). El problema es que a la hora de probarlo (Haciendo que busque todos los números contenidos en una matriz) solo me encuentra unos pocos y haciendo un triangulo.(Mirar imagen)

introducir la descripción de la imagen aquí
El código es el siguiente:

public boolean contiene(int[][] matriz, int elemento) {
    return encontrarNumero(matriz, 0, matriz.length-1, 0, matriz[0].length-1, elemento);
}

public boolean encontrarNumero(int[][] matriz, int f0, int fN, int c0, int cN, int elem){
    boolean enc= false;
    if(f0==fN && c0==cN){
        return (matriz[f0][cN]==elem);
    }
    if(f0 < fN || c0<cN){
        int fk = (f0+fN)/2;
        int ck = (c0+cN)/2;

        if(elem > matriz[fk][ck]) {
            //Busca en primer cuadrante
            enc = encontrarNumero(matriz, f0, fk, c0, ck, elem);
            //busca en el tercero
            enc = encontrarNumero(matriz, fk+1, fN, c0, ck, elem);
        }
        else if (elem < matriz[fk][ck]){
            //busca en el tercero
            enc = encontrarNumero(matriz, fk+1, fN, c0, ck, elem);
            //busca en el segundo
            enc = encontrarNumero(matriz, f0, fk,ck+1, cN, elem);
            //busca en el cuarto
            enc = encontrarNumero(matriz,fk+1, fN, ck+1, cN, elem);
        }
        else if(matriz[fk][ck]==elem){
            return true;
        }
    }
    return enc;
}


La idea sería que me encontrara todos los números dentro del cartón(como prueba), pero no lo hace y solo encuentra unos pocos.

La función que llama al contiene es esta:

for(int i=99; i>0; i--)
        if(cb.contiene(carton, i)){
            if(texto.length()>0) texto.append(", ");
            texto.append(i);
        }

Muchas gracias. Un saludo

1 respuesta 1

2

Tu código tiene un error que una vez sabido te va a parecer obvio: Cuando haces la llamada recursiva, guardas el resultado en la variable booleana enc. ¡Pero te olvidas de comprobarla! Qué pasa si encuentras el elemento en el primer cuadrante? Pues que no estará en el tercer cuadrante y enc pasará de true a false, "olvidando" que ya habías encontrado el elemento

//Busca en primer cuadrante
enc = encontrarNumero(matriz, f0, fk, c0, ck, elem); //enc==true
//busca en el tercero
enc = encontrarNumero(matriz, fk+1, fN, c0, ck, elem); //enc==false

Por tanto tu algoritmo sólo encuentra los números que están en el último lugar que se mira, porque si se encuentran antes, se sigue buscando.

Código que he usado para hacer la prueba, basado en tu código y en la imagen que has puesto (única pega que le veo a tu exposición del problema, es mejor poner texto que una imagen):

public class Test {

    public static boolean contiene(int[][] matriz, int elemento) {
        return encontrarNumero(matriz, 0, matriz.length - 1, 0, matriz[0].length - 1, elemento);
    }

    public static boolean encontrarNumero(int[][] matriz, int f0, int fN, int c0, int cN, int elem) {
        boolean enc = false;
        if (f0 == fN && c0 == cN) {
            return (matriz[f0][cN] == elem);
        }
        if (f0 < fN || c0 < cN) {
            int fk = (f0 + fN) / 2;
            int ck = (c0 + cN) / 2;

            if (elem > matriz[fk][ck]) {
                // Busca en primer cuadrante
                enc = encontrarNumero(matriz, f0, fk, c0, ck, elem);
                // busca en el tercero
                enc = encontrarNumero(matriz, fk + 1, fN, c0, ck, elem) || enc;
            } else if (elem < matriz[fk][ck]) {
                // busca en el tercero
                enc = encontrarNumero(matriz, fk + 1, fN, c0, ck, elem) || enc;
                // busca en el segundo
                enc = encontrarNumero(matriz, f0, fk, ck + 1, cN, elem) || enc;
                // busca en el cuarto
                enc = encontrarNumero(matriz, fk + 1, fN, ck + 1, cN, elem)|| enc;
            } else if (matriz[fk][ck] == elem) {
                return true;
            }
        }
        return enc;
    }

    public static void main(String[] args) {
        int[][] carton = { 
                { 69, 57, 43, 28, 14 },
                { 68, 56, 35, 25, 13 },
                { 66, 55, 34, 22, 8 },
                { 64, 52, 32, 21, 7 },
                { 62, 47, 31, 17, 5 } };
        int[] buscados = { 62, 52, 34, 21, 7 };

        for (int b : buscados) {
            System.out.println("El número "+b+" está?: "+ contiene(carton, b));
        }
    }

}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.