Ejercicios de búsqueda en tablas

EJERCICIO 1

Realizar una aplicación que contenga la función "Buscar", a la que se le pasará un array de números enteros y el elemento a buscar. Debe devolver un Boolean indicando si lo ha encontrado (true) o no (false).

Module Module1

    Sub Main()
        Dim numeros() As Integer = {32, 5, 3, 2, 66, 2, 7, 45, 90}
        Dim num As Integer = 91
        Dim encontrado As Boolean = Buscar(numeros, num)

        Console.WriteLine(encontrado)

        Console.ReadKey()

    End Sub

    Function Buscar(ByVal numeros() As Integer, ByVal num As Integer) As Boolean
        Dim encontrado As Boolean = False

        For Each n As Integer In numeros
            If (n = num) Then
                encontrado = True
            End If
            'Si lo encuentra, sale del "for"
            If encontrado Then Exit For
        Next

        Return encontrado
    End Function

End Module

EJERCICIO 2

Modificar la función anterior para que implemente el algoritmo de búsqueda dicotómica. En este caso se le pasará un array ordenado de menor a mayor.

Module Module1

    Sub Main()
        Dim numeros() As Integer = {2, 2, 3, 5, 7, 32, 45, 66, 90}
        Dim num As Integer = 4
        Dim encontrado As Boolean = Buscar(numeros, num)

        Console.WriteLine(encontrado)

        Console.ReadKey()

    End Sub

    Function Buscar(ByVal numeros() As Integer, ByVal num As Integer) As Boolean
        Dim izquierda As Integer = 0
        Dim derecha As Integer = numeros.Length - 1
        Dim centro As Integer

        While (izquierda <= derecha)
            centro = (izquierda + derecha) / 2
            If (numeros(centro) = num) Then
                Return True
            End If
            If (numeros(centro) > num) Then
                derecha = centro - 1
            ElseIf (numeros(centro) < num) Then
                izquierda = centro + 1
            End If
        End While

        Return False

    End Function

End Module

EJERCICIO 3

Modificar de nuevo la función para que en lugar de un Boolean indicando si ha encontrado o no el elemento buscado, devuelva un entero indicando la posición donde se encuentra dicho elemento. Si el array no contiene ese elemento, devolverá -1.

Module Module1

    Sub Main()
        Dim numeros() As Integer = {2, 2, 3, 5, 7, 32, 45, 66, 90}
        Dim num As Integer = 90
        Dim posicion As Integer = Buscar(numeros, num)

        If (posicion = -1) Then
            Console.WriteLine("No encontrado")
        Else
            Console.WriteLine("Encontrado en la posicion: " & posicion)
        End If

        Console.ReadKey()

    End Sub

    Function Buscar(ByVal numeros() As Integer, ByVal num As Integer) As Integer
        Dim izquierda As Integer = 0
        Dim derecha As Integer = numeros.Length - 1
        Dim centro As Integer

        While (izquierda <= derecha)
            centro = (izquierda + derecha) / 2
            If (numeros(centro) = num) Then
                Return centro
            End If
            If (numeros(centro) > num) Then
                derecha = centro - 1
            ElseIf (numeros(centro) < num) Then
                izquierda = centro + 1
            End If
        End While

        Return -1

    End Function

End Module

Ejercicio de búsqueda en tablas

Partiremos de dos tablas de datos de igual tamaño.

• Una con datos de tipo float (con alturas).
• Otra con datos de tipo String (con nombres).

Supondremos que cada posición indica en dichas tabla la altura y el nombre de una misma persona.

Hacer un programa que inicialice dichas tablas con valores supuestos.

El programa pedirá por la entrada estandar una altura, buscando a continuación el nombre de la persona más alta que no sobrepase la altura introducida.

• Si no encuentra ninguna... lo indicará.
• Si encuentra varias... solo debe mostrar la primera.

public class BuscarAltura {
    public static void main(String[] args) {
        Scanner entrada = new Scanner(System.in);
        float[] alturas = {1.55F, 1.48F, 1.76F, 1.59F, 1.70F, 1.63F, 1.82F};
        String[] nombres = {"Macarena", "Pablo", "María", "Noel", "Eduardo", "Manuel", "Julia"};
        int i, ini, fin;
        float alturaBuscada, auxAlt;
        String auxNom;
        boolean buscadaMayor = false, intercambio = true;
        System.out.print("Introduzca la altura a buscar: ");
        alturaBuscada = entrada.nextFloat();
        //Primero ordenamos la tabla:
        ini = 0;
        fin = alturas.length-1;
        while (ini<fin & intercambio){
            intercambio = false;
            for (i=ini; i<fin; i++){
                if (alturas[i] > alturas[i+1]){
                    auxAlt = alturas[i];
                    alturas[i] = alturas[i+1];
                    alturas[i+1] = auxAlt;
                    auxNom = nombres[i];
                    nombres[i] = nombres[i+1];
                    nombres[i+1] = auxNom;
                    intercambio = true;
                }
            }
            fin--;
            if (intercambio){
                intercambio = false;
                for (i=fin-1; i>=ini; i--){
                    if (alturas[i] > alturas[i+1]){
                        auxAlt = alturas[i];
                        alturas[i] = alturas[i+1];
                        alturas[i+1] = auxAlt;
                        auxNom = nombres[i];
                        nombres[i] = nombres[i+1];
                        nombres[i+1] = auxNom;
                        intercambio = true;
                    }
                }
            }
            ini++;
        }
        //Ahora buscamos AlturaBuscada:
        i=alturas.length-1;
        while (i>=0 & !buscadaMayor){
            if (alturaBuscada >= alturas[i])
                buscadaMayor = true;
            i--;
        }
        if (!buscadaMayor)
            System.out.println("No hay ninguna altura menor que la introducida.");
        else
            System.out.println("La persona más alta que no supera la altura introducida es: "+nombres[i+1]);
    }
}

Ejercicio ordenar y buscar

Dada una tabla de nombres introducidos por el usuario, ordenarlos mediante el método de la sacudida (variante de la burbuja). Después el usuario pedirá buscar un nombre que se buscará en la tabla mediante el método de búsqueda dicotómica o binaria.

NOTA: enlace a una página de algoritmos de ordenación http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html

public class OrdenarBuscar {
    public static void main(String[] args) {
        Scanner entrada = new Scanner(System.in);
        int pos, cuantos;
        int ini, fin, i;
        int izq, der, med;
        String[] nombres;
        String aux, buscado;
        boolean intercambio = true;
        System.out.print("Cuántos nombres quiere introducir: ");
        cuantos = entrada.nextInt();
        nombres = new String[cuantos];
        entrada.nextLine(); //Para limpiar el buffer.
        System.out.println("Introduzca "+cuantos+" nombres.");
        for (pos=0; pos<nombres.length; pos++)
            nombres[pos] = entrada.nextLine();
        ini = 0;
        fin = nombres.length-1;
        while (ini<fin & intercambio){
            intercambio = false;
            for (i=ini;i<fin;i++){
                if (nombres[i].compareTo(nombres[i+1])>0){
                    aux = nombres[i];
                    nombres[i] = nombres[i+1];
                    nombres[i+1] = aux;
                    intercambio = true;
                }
            }
            fin--;
            if (intercambio){
                intercambio = false;
                for (i=fin-1;i>=ini;i--){
                    if (nombres[i].compareTo(nombres[i+1])>0){
                        aux = nombres[i];
                        nombres[i] = nombres[i+1];
                        nombres[i+1] = aux;
                        intercambio = true;
                    }
                }
            }
            i++;
        }
        System.out.println("Nombres ordenados:");
        for (pos=0; pos<nombres.length; pos++)
            System.out.print(nombres[pos]+"  ");
        System.out.println("\nIntroduzca el nombre a buscar.");
        buscado = entrada.nextLine();
        izq = 0;
        der = nombres.length-1;
        med = (izq+der)/2;
        while (buscado.compareTo("")!=0){
            while (buscado.compareTo(nombres[med])!=0 & izq<der){
                if (buscado.compareTo(nombres[med])<0)
                    der = med-1;
                else
                    izq = med+1;
                med = (izq+der)/2;
            }
            if (buscado.compareTo(nombres[med])==0)
                System.out.println("El nombre buscado está en la posición: "+med);
            else
                System.out.println("No encontrado.");
            System.out.println("Introduzca otro nombre.");
            buscado = entrada.nextLine();
        }
        System.out.println("FIN.");
    }
}

Ejercicios búsquedas

Realizar un programa que pida el nombre de una isla y una vez introducido, compruebe si dicha isla pertenece a las Islas Canarias.

public class BuscarIslas {
    public static void main(String[] args) {
        Scanner entrada = new Scanner(System.in);
        int pos=0;
        String islaBuscada;
        String[] islasCanarias = {"El Hierro", "La Palma", "La Gomera", "Tenerife", "Gran Canaria", "Lanzarote", "Fuerteventura"};
        System.out.println("Introduzca el nombre de una isla.");
        System.out.println("Este programa le dirá si pertenece al archipiélago canario.");
        islaBuscada = entrada.nextLine();
        while (pos<(islasCanarias.length-1) & !islaBuscada.equals(islasCanarias[pos]))
            pos++;
        if (islaBuscada.equals(islasCanarias[pos]))
            System.out.println("Sí se trata de una de las Islas Canarias.");
        else
            System.out.println("No es una de las Islas Canarias o el nombre no se ha escrito bien.");
    }
}

Realizar un programa que contenga una tabla de alturas y pida al usuario una altura concreta. Buscará si la altura dada está en la tabla y mostrará la posición.

public class BuscarAlt {
    public static void main(String[] args) {
        Scanner entrada = new Scanner(System.in);
        int pos=0;
        double[] alturas = {1.75, 1.58, 1.50, 2.07, 1.67, 2.11, 1.98, 1.83, 1.49, 1.67};
        double alturaUsuario;
        System.out.println("Introduzca la altura que desee.");
        System.out.println("Este programa le mostrará la posición en que se encuentra.");
        alturaUsuario = entrada.nextDouble();
        while (pos<(alturas.length-1) & alturas[pos]!=alturaUsuario)
            pos++;
        if (alturas[pos]==alturaUsuario)
            System.out.println("La altura "+alturaUsuario+" se encuentra en la posición: "+pos);
        else
            System.out.println("La altura "+alturaUsuario+" no se ha encontrado.");
    }
}