elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Entrar al Canal Oficial Telegram de elhacker.net


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  Ayuda con Busqueda dicotomica
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Ayuda con Busqueda dicotomica  (Leído 4,052 veces)
maestro kirer

Desconectado Desconectado

Mensajes: 11


Ver Perfil
Ayuda con Busqueda dicotomica
« en: 7 Diciembre 2017, 16:30 pm »

Hola a todos , este post es para dudas entonces si hay que moverlo o asi agradeceria que lo hiciesen , bueno empiezo . Estoy en un ciclo de programacion y tengo un examen de programacion este miercoles hasta ahi todo bien pero tengo unas dudas con algun metodo los cuales no entendi muy bien puesto que nuestra profesora no es la mejor explicando , estoy hablando de los metodos de ordenacion y busqueda dicotomica os dejo ahora unas partes de los codigos .


package ejerciciocoches;

import java.util.Scanner;


public class Busqueda {

    public static int buscar(String[] modelos) {
        Scanner scan = new Scanner(System.in);
        int inicio = 0;
        int fin = modelos.length - 1;
        int mitad;
        System.out.println("Introduce el nombre a buscar: ");
        String busqueda = scan.nextLine();
        while (inicio <= fin) {
            mitad = (fin + inicio) >>> 1;
            if (busqueda.compareToIgnoreCase(modelos[mitad]) > 0) {
                inicio = mitad + 1;
            } else if (busqueda.compareToIgnoreCase(modelos[mitad]) < 0) {
                fin = mitad - 1;
            }else{
                return mitad;
            }
        }
        return -1;
    }
}



Vale mis cuestiones son como se usa bien la busqueda y por que se le ponen los -1 (el codigo lo hicimos todos juntos en clase )  por ejemplo en la variable fin ponemos modelo... -1 por que para que sirve eso

orden

package ejerciciocoches;


public class Ordenar {

    public static void ordenarMayorMenor(float[] sumaFilas, String[] modelos) {
        float aux;
        String auxS;
        for (int i = 0; i < sumaFilas.length - 1; i++) {
            for (int j = i + 1; j < sumaFilas.length; j++) {
                if (sumaFilas < sumaFilas[j]) {
                    aux = sumaFilas;
                    sumaFilas = sumaFilas[j];
                    sumaFilas[j] = aux;

                    auxS = modelos;
                    modelos = modelos[j];
                    modelos[j] = auxS;
                }
            }
        }
    }

    public static void ordenarAlf(float[][] pCoches, String[] modelos) {
        float[] aux;
        String auxS;
        for (int i = 0; i < modelos.length - 1; i++) {
            for (int j = i + 1; j < modelos.length; j++) {
                if (modelos.compareToIgnoreCase(modelos[j]) > 0) {
                    auxS = modelos;
                    modelos = modelos[j];
                    modelos[j] = auxS;

                    aux = pCoches;
                    pCoches = pCoches[j];
                    pCoches[j] = aux;
                }
            }
        }
    }
}



y lo otro es en la ordenacion los simbolos <> sirven para ordenar de mayor a menor cual para cual ¿?



Pues en resumen me gustaria una explicacion de la busqueda dicotomica y la duda del orden.
Muchas gracias de antemano


En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.350


Ver Perfil
Re: Ayuda con Busqueda dicotomica
« Respuesta #1 en: 8 Diciembre 2017, 18:34 pm »

Debes pensar las cosas, no 'solo escribir' ni 'solo oir', la "velocidad" de enseñanza en las univesidades suele ser contraproducente, porque al final solo aprenderías cosas de memoria, sin entenderlas, así que haces bien en preguntar... aunque si por tu propia cuenta lo pensaras despacio un poco, tú mismo descubrirías el proqué.

1 - Veamos al comienzo, la línea:
Código:
int fin = modelos.length - 1;
el -1 responde al hecho de que el tamaño de un array indica SIEMPRE la cantidad de elementos que contiene, por ejemplo si dice 10, tiene 10 elementos, pero contados a partir del 0, el último será el índice 9, si fueran 87 elemento, empezando en 0, el último sería el 86, ídem si tuviera 2514 elementos, el último sería el índice 2513, ergo el último índice siempre es: tamaño-1
Si en vez de empezar en 0, empezaras en 5, sería tamaño-1+5, porque para 10 elementos iría desde el 5,6,7,8,9-10,11,12,13,14.
Y si empezara en un índice de valor negativo, (por ejemplo -11 con tamaño 27) el último índice sería:  tamaño-1+(-11) = 27-1-11 = 15
(-11,-10,-9,-8,-7; -6,-5,-4,-3,-2; -1,0,1,2,3; 4,5,6,7,8; 9,10,11,12,13; 14,15)
Es decir la fórmula general para conocer el último índice en un array, siempre es: Tamaño-1+límiteInferior. Y dado que la casi absoluta comunidad de lenguajes arranca sus indíces en el 0, la suma del límite inferior es redundante.

2 - Búsqueda dicotómica, (como no), es nombre muy apropiado para libros y universidades, pero es más universal y entendible para todo el mundo (y no solo el mundillo informático), "Búsqueda binaria".
La búsqueda binaria requiere que el array (o el tipo de colección que se utilice) esté ordenada. Luego si se desea buscar un valor concreto, pongamos el 22 y pongamos (que el array de partida tiene 100 elementos, (sí del 0 al 100-1), y que en cada índice contiene casualmente el valor cuyo índice señala: Arr(0) = 0, Arr(1)=1, Arr(2)=2 ... Arr(99)=99, por simplicidad en las comprobaciones)...

3 - Entonces tendremos que (eliminado la morralla que oscurece la sencillez del algoritmo, esto es expresándolo en pseudocódigo):
Código:
entero = Funcion BusquedaBinaria(array de enteros Valores(), entero Valor) //el que se busca
    entero ini, medio, fin
    
    fin = Tamaño(Valores)-1: ini = 0
    
    Hacer mientras (ini <= fin) //menor o igual que
        medio = (ini + fin) \ 2
                
        Si Valores(medio) > Valor luego
            fin = medio - 1
        Osi Valores(medio) < Valor luego
            ini = medio + 1
        Sino
            devolver medio //valor encontrado
        fin si
    repetir
      
    // Si no se encuentra el valor puede devolverse el índice evaluado (medio) en negativo,
    //    queriendo indicar con ello que de existir se alojaría en ese índice
    //    (es ideal si se quisiera insertar ordenado)
    //    y eso es mucho mejor que -1, pero si te reclaman devolver -1, pues hale...
    Devolver -medio
Fin Funcion
4 - AQUÍ: la devolución de un índice negativo, expresa 'no encontrado', y a la devolución mejor que considerar:
 
Código:
Si Buscarbin(x,y) =-1 luego no hallado
mucho mejor expresarlo así:
 
Código:
Si BuscarBin(x,y)<0 luego no hallado

Y ahora pasando ese array preestablecdio de 100 elementos con valores numerados del 0 al 99 y buscando el valor 22, hagamos paso a paso lo que sucede (que es lo que tu deberías haber hecho, dibujar una tabla y en cada línea anotar los valores que tienen cada variable, así como el resultado de las comparaciones evaluadas (True/False) ):
Previo:
ini=0
fin = 100-1

Primer ciclo
Medio= (0+99)\2 = 49 // hacmeos una división entera, los ínidces siempre son enteros, no decimales, luego 49'5 se trunca en 49.
Ahora la primera comprobación (dentro del bucle):
 Si Valores(49) >22 luego //que es la condición que se cumple
      fin= (medio-1), = 49-1 = 48, es decir el valor en el medio es mayor que el buscado, nos queda que mirar or debajo del medio, el índice inmediatamente por debajo del medio es justamente: medio -1, ese pasa a ser ahora el fin, el último hasta el que buscaríamos...

Siguiente ciclo:
Medio = (0 + 48)\2= 24
  Si Valores(24) > 22 luego //nuevamente se cumple esta condición...
     Fin = (24-1) =23 // ahora el límite superior será 1 menos que el valor que ya hemos visto que era superior al buscado.

Siguiente ciclo:
Medio = (0 + 23)\2 = 11
  Si Valores(12) > 22 luego // esta vez no se cumple, pasamos a ala sigueinte condición
  Osi Valores(11) < 22 luego //si se cumple esta, luego inicio podrá ser ahora mayor que 0, toda vez que ehmos visto que el valor está más arriba que la posición 11.
     Ini = (medio +1) = 11+1 = 12 // es decir de existir, estará entre los índices 12 y 23

Siguiente ciclo:
Medio = (12+23)\2 = 17
  Si Valores(17) > 22 luego // no se cumple,
  Osi Valores(17) < 22 luego
     Ini = (medio+1) = 17+1=18

Siguiente ciclo:
Medio = (17+23)\2= 20
   Si Valores(20) > 22 luego // no se cumple,
   Osi Valores(20) < 22 luego
     Ini = (medio+1) = 20+1=21

Siguiente ciclo:
Medio= (21+23)\2= 22
   Si Valores(20) > 22 luego // no se cumple,
   Osi Valores(20) < 22 luego //Tampoco se cumple, se pasa el caso siguiente que es expresada como ninguno d elos previos:
     Devolver Medio // hallado, se devuelve el índice 22, porque contiene el valor 22
Recuerda que por comodidad pusimos en el array como valor el mismo valor numérico que es el índice, luego Valores(22) = 22, que es el valor buscado y está en el índice 22.

Si has seguido las explicaciones paso a paso, el -1, +1 debe quedarte claro, para que sirve en cada caso, para mover el límite al punto deseado (no revisar dos veces valores ya verificados). Seguirá funcionando si pones:
   Fin = medio -1
   Ini = medio +1
pero en general requerirá más ciclos y podría darse el caso de entrar en un bucle infinito si al hallar en el siguiente ciclo el punto medio, resultare ser nuevamente el mismo punto medio del ciclo previo, precisamente por no acotar los límites convenientemente.
  
4 - La última duda, son los símbolos matemáticos (que esto ya tiene tela, en la Universidad y aún no conocer los símbolos matemáticos "Mayor que y Menor que).
Menor que: <
Mayor que: >
Distinto de: <> //desigualdad,  no universalmente usado en todos los lenguajes pero matemáticamente es aceptado, gracias a que misteriosamente en el ASCII (cuando el American Standard..., creó la tabla), no se incluyó el símbolo "= tachado" para expresar desigualdad, distinto de...
La forma de no equivocarte es ver que en un extremo hay 2 'puntos'(de los 2 trazos) y en el otro solo 1 (donde comfluyen), luego puesto, escrito el símbolo considera que exige que adónde apuntan los 2 'puntos' se espera que sea mayor que adonde apuntan solo un 'punto'  A > B; C < D.


« Última modificación: 8 Diciembre 2017, 18:47 pm por NEBIRE » En línea

maestro kirer

Desconectado Desconectado

Mensajes: 11


Ver Perfil
Re: Ayuda con Busqueda dicotomica
« Respuesta #2 en: 9 Diciembre 2017, 18:32 pm »

MUUUCHISIMAS GRACIAS con la busqueda binaria enserio te lo agradezco un monton , luego no estoy en la universidad estoy en un ciclo superior el cual mi profesora es experta de c ... lleva 2-3 años con java y aveces se lia ella sola ...
Y el problema de los simbolos no me referia a eso me debi de explicar mal eso si que ya lo sabia pero mi duda era que cual uso cuando hago un metodo para ordenar de mayor a menor y de menor a mayor eso es lo que quiero saber que simbolo uso para ordenar de ambas maneras no el significado de ellos .

Un saludo y gracias
En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.350


Ver Perfil
Re: Ayuda con Busqueda dicotomica
« Respuesta #3 en: 10 Diciembre 2017, 15:37 pm »

mi duda era que cual uso cuando hago un metodo para ordenar de mayor a menor y de menor a mayor eso es lo que quiero saber que simbolo uso para ordenar de ambas maneras...
No importa.
¿(5>3)? da la misma respuesta que preguntar ¿(3<5)?

Da lo mismo decir "no es lunes, ni martes, ni miércoles ni jueves, ni viernes, ni sábado", que decir "es domingo", lo uno si es lo inverso de lo otro, no importa entonces como se describa, si como afirmando lo uno o negando el resto. en general se usa lo que resulte más breve, legible o entendible... en el ejemplo: es domingo es más conciso y claro.
Igualmente puede valorarse:
Código:
Si (x < y) luego
que
Código:
Si (y => x) luego
Eso si, nota que no siempre al hacer algoritmos la inclusión del símbolo igual genera el mismo resultado, es decir hay veces en que:
Código:
Si (x <= y) luego
en un algoritmo puede llegar a ser igual que
Código:
Si (y >= x) luego
por lo que antes de expresar algo de una forma opuesta, se debe estar plenamente seguro de si la exclusión es totalmente correcta.

Cuando un caso tenga numerosas variables en juego, lo mejor es hacer una tabla de verdad, con ella se elige luego la forma que mejor resume y lleve a cabo (la que requiera menos comparaciones en general, además de más rápida es más clara) y si algo no resulta evidente, siempre dejar un comentario en el código... pasado el tiempo, puede ser que no recuerdes lo que tiempo atrás era muy evidente y hacer cambios que luego fallan.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Ayuda con mi busqueda
PHP
Rijhording 2 2,045 Último mensaje 29 Junio 2010, 16:10 pm
por Rijhording
ayuda con busqueda C#
.NET (C#, VB.NET, ASP)
RepsaGlez 0 3,196 Último mensaje 15 Agosto 2010, 00:17 am
por RepsaGlez
Ayuda con la búsqueda de un libro
Foro Libre
fuenteRea 2 1,966 Último mensaje 27 Febrero 2011, 14:43 pm
por Constance
Ayuda con búsqueda de palabra en txt
Programación C/C++
ZedGe 4 2,861 Último mensaje 2 Septiembre 2013, 11:58 am
por eferion
Algoritmo A* , Busqueda en Profundidad y Busqueda en Anchura
Java
HackingLikor 0 2,588 Último mensaje 4 Mayo 2016, 01:08 am
por HackingLikor
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines