Foros aprenderaprogramar.com
Aprender a programar => C, C++, C#, Java, Visual Basic, HTML, PHP, CSS, Javascript, Ajax, Joomla, MySql y más => Mensaje iniciado por: rackdon en 13 de Junio 2014, 13:45
-
Buenas tardes.
Como me viene pasando ultimamente cuando hago algo de recursividad, los resultados no son los esperados.
El código es el siguiente:
// Ejercicio 6.35: Búsqueda binaria (recursivo) //
#include <stdio.h>
#define TAMANIO 15
/* prototipos de las funciones */
int busquedaBinaria( const int b[], int claveDeBusqueda, int bajo, int alto );
void despliegaEncabezado( void );
void despliegaLinea( const int b[], int bajo, int medio, int alto );
/* la función main comienza la ejecución del programa */
int main()
{
int a[ TAMANIO ]; /* crea el arreglo a */
int i; /* contador para inicializar los elementos de 0 a 14 del arreglo a */
int llave; /* valor a localizar en el arreglo a */
int resultado; /* variable para almacenar la ubicación de la llave o -1 */
/* crea los datos */
for ( i = 0; i < TAMANIO; i++ ) {
a[ i ] = 2 * i;
} /* fin de for */
printf( "Introduzca un numero entre 0 y 28: " );
scanf( "%d", &llave );
despliegaEncabezado();
/* busca la llave en el arreglo a */
resultado = busquedaBinaria( a, llave, 0, TAMANIO - 1 );
/* despliega los resultados */
if ( resultado != -1 ) {
printf( "\n%d se encuentra en el elemento %d del arreglo\n", llave, resultado );
} /* fin de if */
else {
printf( "\n%d no se encuentra\n", llave );
} /* fin de else */
system("pause");
return 0; /* indica terminación exitosa */
} /* fin de main */
/* función para realizar la búsqueda binaria en un arreglo */
int busquedaBinaria( const int b[], int claveDeBusqueda, int bajo, int alto )
{
int central = ( bajo + alto ) / 2;
despliegaLinea( b, bajo, central, alto );
if ( bajo > alto )
{
printf("\ncentral = %d", central);
return -1;
}
if ( claveDeBusqueda == b[ central ] )
{
printf("\ncentral = %d", central);
return -1;
}
if ( claveDeBusqueda < b[ central ] )
{
busquedaBinaria( b, claveDeBusqueda, bajo, central - 1 );
}
if(claveDeBusqueda > b[central] )
{
busquedaBinaria (b, claveDeBusqueda, central + 1, alto);
}
} /* fin de la funcipon busquedaBinaria */
/* Imprime un encabezado para la salida */
void despliegaEncabezado( void )
{
int i; /* contador */
printf( "\nSubindices:\n" );
/* muestra el encabezado de la columna */
for ( i = 0; i < TAMANIO; i++ ) {
printf( "%3d ", i );
} /* fin de for */
printf( "\n" ); /* comienza la nueva línea de salida */
/* muestra una línea de caracteres - */
for ( i = 1; i <= 4 * TAMANIO; i++ ) {
printf( "-" );
} /* fin de for */
printf( "\n" ); /* inicia una nueva línea de salida */
} /* fin de la función despliegaEncabezado */
/* Imprime una línea de salida que muestra la parte actual
del arreglo que se esta procesando. */
void despliegaLinea( const int b[], int baj, int cen, int alt )
{
int i; /* contador para la iteración a través del arreglo b */
/* ciclo a través del arreglo completo */
for ( i = 0; i < TAMANIO; i++ ) {
/* despliega espacios si se encuentra fuera del rango actual del subarreglo */
if ( i < baj || i > alt ) {
printf( " " );
} /* fin de if */
else if ( i == cen ) { /* despliega el elemento central */
printf( "%3d*", b[ i ] ); /* marca el valor central */
} /* fin de else if */
else { /* despliega otros elementos en el subarreglo */
printf( "%3d ", b[ i ] );
} /* fin de else */
} /* fin de for */
printf( "\n" ); /* inicia la nueva línea de salida */
} /* fin de la función despliegaLinea */
He probado introduciendo el número 25, y en vez de mostrar que no se encuentra el número, muestra que se ha encontrado, lo cual no me cuadra, porque si que devuelve -1 a la funcion main.
Otro caso es, si introduzco el número 8, devuelve a la función main el 8, pero al mostrar el resultado, aparece como si fuera 14. Y con el 6 ocurre lo mismo.
A ver si alguien me pudiera ayudar.
Muchisimas gracias
-
La recursividad es difícil de entender y depurar, de ahí que muchos programadores opten por no utilizarla.
En este caso con dos pequeñas modificaciones parece que el programa funciona bien. La primera:
if ( claveDeBusqueda == b[ central ] ) {
printf("\ncentral = %d", central);
return central;
}
Es decir, cuando encuentras la solución tienes que devolver el índice donde lo has encontrado, no devolver -1 (eso sería que no se ha encontrado)
Si declaras la función recursiva de tipo int, significa que la función va a devolver un entero, sin embargo hay ramas de ejecución sin sentencia return ¿entonces qué devuelve la función? La solución está en que devuelva una llamada recursiva, simplemente añadir un return antes de la llamada recursiva
Con estos pequeños cambios:
// Ejercicio 6.35: Búsqueda binaria (recursivo) //
#include <stdio.h>
#define TAMANIO 15
/* prototipos de las funciones */
int busquedaBinaria( const int b[], int claveDeBusqueda, int bajo, int alto );
void despliegaEncabezado( void );
void despliegaLinea( const int b[], int bajo, int medio, int alto );
/* la función main comienza la ejecución del programa */
int main() {
int a[ TAMANIO ]; /* crea el arreglo a */
int i; /* contador para inicializar los elementos de 0 a 14 del arreglo a */
int llave; /* valor a localizar en el arreglo a */
int resultado; /* variable para almacenar la ubicación de la llave o -1 */
/* crea los datos */
for ( i = 0; i < TAMANIO; i++ ) {
a[ i ] = 2 * i;
} /* fin de for */
printf( "Introduzca un numero entre 0 y 28: " );
scanf( "%d", &llave );
despliegaEncabezado();
/* busca la llave en el arreglo a */
resultado = busquedaBinaria( a, llave, 0, TAMANIO - 1 );
/* despliega los resultados */
if ( resultado != -1 ) {
printf( "\n%d se encuentra en el elemento %d del arreglo\n", llave, resultado );
} /* fin de if */
else {
printf( "\n%d no se encuentra\n", llave );
} /* fin de else */
system("pause");
return 0; /* indica terminación exitosa */
} /* fin de main */
/* función para realizar la búsqueda binaria en un arreglo */
int busquedaBinaria( const int b[], int claveDeBusqueda, int bajo, int alto ) {
int central = ( bajo + alto ) / 2;
despliegaLinea( b, bajo, central, alto );
if ( bajo > alto ) {
printf("\ncentral = %d", central);
return -1;
}
if ( claveDeBusqueda == b[ central ] ) {
printf("\ncentral = %d", central);
return central;
}
if ( claveDeBusqueda < b[ central ] ) {
return busquedaBinaria( b, claveDeBusqueda, bajo, central - 1 );
}
if(claveDeBusqueda > b[central] ) {
return busquedaBinaria (b, claveDeBusqueda, central + 1, alto);
}
} /* fin de la funcipon busquedaBinaria */
/* Imprime un encabezado para la salida */
void despliegaEncabezado( void ) {
int i; /* contador */
printf( "\nSubindices:\n" );
/* muestra el encabezado de la columna */
for ( i = 0; i < TAMANIO; i++ ) {
printf( "%3d ", i );
} /* fin de for */
printf( "\n" ); /* comienza la nueva línea de salida */
/* muestra una línea de caracteres - */
for ( i = 1; i <= 4 * TAMANIO; i++ ) {
printf( "-" );
} /* fin de for */
printf( "\n" ); /* inicia una nueva línea de salida */
} /* fin de la función despliegaEncabezado */
/* Imprime una línea de salida que muestra la parte actual
del arreglo que se esta procesando. */
void despliegaLinea( const int b[], int baj, int cen, int alt ) {
int i; /* contador para la iteración a través del arreglo b */
/* ciclo a través del arreglo completo */
for ( i = 0; i < TAMANIO; i++ ) {
/* despliega espacios si se encuentra fuera del rango actual del subarreglo */
if ( i < baj || i > alt ) {
printf( " " );
} /* fin de if */
else if ( i == cen ) { /* despliega el elemento central */
printf( "%3d*", b[ i ] ); /* marca el valor central */
} /* fin de else if */
else { /* despliega otros elementos en el subarreglo */
printf( "%3d ", b[ i ] );
} /* fin de else */
} /* fin de for */
printf( "\n" ); /* inicia la nueva línea de salida */
} /* fin de la función despliegaLinea */
-
Muchas gracias.
Lo de return -1, antes lo tenía bien, pero al andar probando para ver donde podía estar el error lo cambie y luego se me olvido volver a dejarlo como debía ser.
En cuanto a lo de return (funcion), muchas gracias, era ese el fallo. Soy tonto y se me olvido poner return, por eso se quedaba guardado el ultimo central en vez de devolver el valor real.