Autor Tema: Búsqueda Binaria Recursiva en C [lenguajeC] arreglo menor central intercambiar  (Leído 3955 veces)

Telematico

  • Sin experiencia
  • *
  • Mensajes: 2
  • Principiante!
    • Ver Perfil
Buenas Noches, actualmente estoy intentando "autoaprender" lógica de programación y con ella lenguaje C, en este momento desarrollo una tarea de búsqueda binaria recursiva, pero por mas vueltas que le doy al algoritmo no doy con la respuesta que requiero....Alguien puede auxiliarme...

Saludos

Acá el código:..

Algoritmo recursivo de busqueda  binaria

Código: [Seleccionar]
#include <stdio.h>
#include <stdlib.h>
#define dimension 3
main( )
{
int indice,j,valor;
int pos_menor,alto,central,bajo;
float arreglo[dimension];
float menor,AUX;

/*Leer Vector*/
for(indice=0;indice<dimension;indice++)
{
printf("arreglo[%i]= ",indice);//Ingresa los valores para el arreglo//
scanf("%f",&arreglo[indice]);
}

//Orden por Selección//
for(indice=0;indice<dimension;indice++)
{
menor=arreglo[indice];//Asignamos el contenido del arreglo a la variable menor//
pos_menor=indice;//Asignamos el valor del indice del arreglo a la variable pos_menor/
for(j=indice+1;j<dimension;j++)//Ciclo iterativo para ordenar por selección//
 {
 if(menor>arreglo[j])// Sentencia if para evaluar que la variable menor sea mayor ha arreglo//
  {
   menor=arreglo[j];//Se asigna el contenido del arreglo en la posición j, a la variable menor//
   pos_menor=j;//Asignamos el contenido o valor de j a la variable pos_menor//
  }
}
//Intecambiar//
AUX=arreglo[indice];//Se usa para almacenar el contenido del arreglo, en la posicion indicada por el indice//
arreglo[indice]=arreglo[pos_menor];//Igualamos el contenido de los indices del arreglo con los de arreglo pos_menor//
arreglo[pos_menor]=AUX;//Se asignan a la variable auxiliar los valores anteriores//
}
//Imprimir o mostrar el Vector en orden ascendente//
for(indice=0;indice<dimension;indice++)
{
printf("arreglo[%i]=%f\n",indice,arreglo[indice]); //Muestra el vector ordenado, en orden ascendente, %i indica numeros enteros//
}
printf("\n Que valor desea buscar? ");//indicamos al usuario que diga cual valor desea buscar//
scanf("%f",&valor);//capturamos el valor anterior anterior en la variable valor//
bajo=0;//asignamos el valor 0  a la variable bajo//
alto=dimension-1;//restamos 1 a la variable dimension, el resultado lo asignamos a la variable alto//
central=(bajo+alto)/2;//sumanos los contenidos de alto y bajo lo dividimos entre 2, el resultado lo asignamos a la variable central//
//Busqueda Binaria//
while ((bajo<=alto)&&(arreglo[bajo]!=valor))//Evaluamos que el valor de la variable bajo sea menor o igual al de alto y que el valor del arreglo en central sea diferente al valor que le usuario esta buscando//
{
if(valor<arreglo[central])//Verificamos si el valor introducido por el usuario, es menor al de la variable en central//
{
}
else
{
bajo=central+1;
central=(bajo+alto)/2;
}
if(valor = arreglo[central])
{
printf("El valor se encuentra en la posicion:%i",arreglo[central],valor);
}
else
{
printf("El valor no se encuentra");
}
getch();
system("PAUSE");
return 0;
}
}
« Última modificación: 09 de Agosto 2018, 22:17 por Ogramar »

Kabuto

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 983
    • Ver Perfil
Re:Búsqueda Binaria Recursiva
« Respuesta #1 en: 15 de Julio 2018, 20:51 »
Y ¿ha de ser recursiva?
En dicho caso tendrías que escribir una función y supongo que como parámetros tendría que recibir el vector, el número a buscar, y valores para el bajo y el alto. Estos valores "bajo" y "alto" irían cambiando con cada llamada recursiva para ir acotando la búsqueda.

Es decir, supongamos un vector de 10 elementos.
Entonces tendríamos que bajo = 0 y alto = 9

Comparamos el numero a buscar con la posicion intermedia, que sería el indice 5 del vector.

Si el número a buscar es menor que el que tenemos en el índice 5 del vector, ya sabemos que el numero que buscamos no está entre el 5 y el 9.
Entonces volvemos a llamar a la funcion, con bajo = 0 pero ahora alto = 4.

Si el numero fuera mayor, encontes bajo = 6 y alto = 9.

Así hasta encontrar el numero.

He escrito algoritmos (en Java) para busquedas dicotómicas pero nunca recursivas. Simplemente un bucle que se repite actualizando los valores de bajo y alto hasta encontrar el numero o bien hasta que no queden posiciones por consultar.

Quizás deberías intentar hacer esto primero, para que te quede clara la mecánica de la búsqueda dicotómica. Y luego intentar lo mismo pero por recursividad, que por otra parte, no se si es algo adecuado para este tipo de ejercicio. Tal vez sí, no lo sé, nunca lo he intentado.
NO respondo dudas por mensaje privado
Publicando vuestras dudas en el foro público conseguimos:
- Que más gente aporte respuestas mejores o complementarias.
- Que otras personas puedan aprender de vuestras dudas.

Mejor en PÚBLICO que en privado. Gracias

Telematico

  • Sin experiencia
  • *
  • Mensajes: 2
  • Principiante!
    • Ver Perfil
Re:Búsqueda Binaria Recursiva
« Respuesta #2 en: 17 de Julio 2018, 05:47 »
Buenas Noches

Gracias por tu respuesta, pero si es recursiva, y los datos son solo tres!...
pero no logro dar con la linea de código que me falta o que debo corregir...

Saludos

Kabuto

  • Moderador Global
  • Experto
  • *******
  • Mensajes: 983
    • Ver Perfil
Re:Búsqueda Binaria Recursiva
« Respuesta #3 en: 17 de Julio 2018, 22:23 »
Vale, a ver. Recuperando un código mio de Java, lo he porteado a C y lo he integrado en tu código.
No estoy muy ducho en C, lo mio es Java. Pero lo he compilado y funciona.

He modificado la constante dimension a valor 10, para que la busqueda sea un poco más larga e interesante.

El resto de código apenas lo he modificado, solo la parte donde hacemos la busqueda.
He cambiado el bucle while, por un do ..while.
Viene a ser lo mismo en realidad, pero para este ejercicio queda mejor en mi opinion.

Tambien añado un booleano para controlar si hemos encontrado el valor a buscar o no.
Es mejor informar de si lo hemos encontrado o no cuando el bucle haya terminado de buscar.
El bucle puede terminar por haberlo encontrado o porque ya no quedan números para seguir comparando. Esta variable booleana nos servirá para saber cuál de las dos posibilidades ha ocurrido.
He puesto una linea que empieza por "Debug Info:" para que informe por pantalla que posicion del vector está consultando en cada momento.
No es necesaria para resolver el problema, pero es interesante ver como se va recalculando el valor de central. Sobre todo si aumentamos aún más la dimension del vector.

En fin, lo realmente interesante y algo difícil, es la parte en como recalculamos los valores de alto, bajo y central según si el numero es mayor o menor.

Código: [Seleccionar]
if (valor < arreglo[central])//Verificamos si el valor introducido por el usuario, es menor al de la variable en central//
{
//Valor es menor, hay que recalcular primero la variable alto y luego central
alto = central - 1;
central = (alto - bajo) / 2 + bajo;
}
else
{
//Valor es mayor, hay que recalcular primero la variable bajo y luego central
bajo = central + 1;
central = (alto - bajo) / 2 + bajo;
}

Las dos líneas que pusiste tú, se acercaban bastante a la solución, pero esta es en realidad un poquito más complicada.
No parece evidente al principio, sobre todo al trabajar con un vector de solo dimension 3, pero el resultado de dividir por 2 la resta de alto - bajo, hay que sumarsela despues a bajo
Supón un vector de dimension 10. REsulta que
bajo = 0
alto  = 9
central = 4 --> (9/2 = 4.5 --> Al pasar a int la posicion es 4 )

El numero no coincide y es mayor, así que tenemos que recalcular la variable bajo y central
bajo = central + 1 -- > 5
alto = 9 (este no cambia)
central = (alto - bajo) / 2 --> (9 - 5) / 2 --> 2
¿Como que un 2 ? Esto no es correcto, debemos preguntar por una posicion mayor que 4 , y 2 es menor ....

Claro, por eso digo que el resultado de este cálculo, hay que sumárselo siempre a bajo.
Atentos:
central = (alto - bajo) / 2  + bajo--> (9 - 5) / 2 + 5 --> 7

Ahora sí!!! Hemos conseguido el 7, que si es mayor que la posicion 4 por la cuál habiamos preguntado anteriormente.

No se si con esta explicación ha quedado claro, si haces tu mismo a lapiz y papel una simulación de estos cálculos cada vez que el bucle se repite buscando el número, quizás lo entiendas mejor.

En fin, te pongo abajo el código completo. Si lo compilas debería funcionar.

Importante, esto que yo he hecho es una búsqueda dicotómica, pero no es recursiva

Si consigues que te quede claro como funciona esta búsqueda, prueba a transformarlo tú en una búsqueda recursiva.

Suponiendo que entendemos lo mismo "por recursiva". Es decir, cuando hablamos "de recursividad", hablamos de una función que se llama a si misma internamente varias veces proporcionandose distintos valores para sus parametros.

Por eso dije al principio que en ese caso, tendrás que escribir una función que se encargue de hacer busquedas dicotómicas y que se llame a si misma hasta encontrar el número a buscar o hasta que no queden numeros por comprobar.

Aqui mi código completo:
Código: [Seleccionar]
#include <stdio.h>
#include <stdlib.h>
#define dimension 10

int main()
{
int indice, j;
int pos_menor, alto, central, bajo;
float arreglo[dimension];
float menor, AUX;
float valor;

/*Leer Vector*/
for (indice = 0; indice<dimension; indice++)
{
printf("arreglo[%i]= ", indice);//Ingresa los valores para el arreglo//
scanf("%f", &arreglo[indice]);
}

//Orden por Selección//
for (indice = 0; indice<dimension; indice++)
{
menor = arreglo[indice];//Asignamos el contenido del arreglo a la variable menor//
pos_menor = indice;//Asignamos el valor del indice del arreglo a la variable pos_menor/
for (j = indice + 1; j<dimension; j++)//Ciclo iterativo para ordenar por selección//
{
if (menor>arreglo[j])// Sentencia if para evaluar que la variable menor sea mayor ha arreglo//
{
menor = arreglo[j];//Se asigna el contenido del arreglo en la posición j, a la variable menor//
pos_menor = j;//Asignamos el contenido o valor de j a la variable pos_menor//
}
}
//Intecambiar//
AUX = arreglo[indice];//Se usa para almacenar el contenido del arreglo, en la posicion indicada por el indice//
arreglo[indice] = arreglo[pos_menor];//Igualamos el contenido de los indices del arreglo con los de arreglo pos_menor//
arreglo[pos_menor] = AUX;//Se asignan a la variable auxiliar los valores anteriores//
}
//Imprimir o mostrar el Vector en orden ascendente//
for (indice = 0; indice<dimension; indice++)
{
printf("arreglo[%i]=%f\n", indice, arreglo[indice]); //Muestra el vector ordenado, en orden ascendente, %i indica numeros enteros//
}
printf("\n Que valor desea buscar? ");//indicamos al usuario que diga cual valor desea buscar//
scanf("%f", &valor);//capturamos el valor anterior anterior en la variable valor//
bajo = 0;//asignamos el valor 0  a la variable bajo//
alto = dimension - 1;//restamos 1 a la variable dimension, el resultado lo asignamos a la variable alto//
central = alto / 2;//sumanos los contenidos de alto y bajo lo dividimos entre 2, el resultado lo asignamos a la variable central//
    //Busqueda Binaria
bool encontrado = false;
do
{
printf("--Debug info: Consultando Posicion --> %i\n", central);
if (valor == arreglo[central])
{
printf("Encontrado!!\n");
encontrado = true;
}
else
{
if (valor < arreglo[central])//Verificamos si el valor introducido por el usuario, es menor al de la variable en central//
{
//Valor es menor, hay que recalcular primero la variable alto y luego central
alto = central - 1;
central = (alto - bajo) / 2 + bajo;
}
else
{
//Valor es mayor, hay que recalcular primero la variable bajo y luego central
bajo = central + 1;
central = (alto - bajo) / 2 + bajo;
}
}
} while ((bajo <= alto) && !encontrado);
//Consultamos si lo hemos encontrado o no
if (encontrado)
printf("El valor se encuentra en la posicion:%i", central);
else
printf("Valor no encontrado");

printf("\n");
system("PAUSE");
return 0;
}

NO respondo dudas por mensaje privado
Publicando vuestras dudas en el foro público conseguimos:
- Que más gente aporte respuestas mejores o complementarias.
- Que otras personas puedan aprender de vuestras dudas.

Mejor en PÚBLICO que en privado. Gracias

 

Sobre la educación, sólo puedo decir que es el tema más importante en el que nosotros, como pueblo, debemos involucrarnos.

Abraham Lincoln (1808-1865) Presidente estadounidense.

aprenderaprogramar.com: Desde 2006 comprometidos con la didáctica y divulgación de la programación

Preguntas y respuestas

¿Cómo establecer o cambiar la imagen asociada (avatar) de usuario?
  1. Inicia sesión con tu nombre de usuario y contraseña.
  2. Pulsa en perfil --> perfil del foro
  3. Elige la imagen personalizada que quieras usar. Puedes escogerla de una galería de imágenes o subirla desde tu ordenador.
  4. En la parte final de la página pulsa el botón "cambiar perfil".