PDA

Visualizza la versione completa : [C] Ricerca binaria mediante funzione ricorsiva


D4rkAng3l
23-01-2006, 13:27
Ciao,
sono disperato, devo fare un esercizio che esegua la ricerca binaria di un valore in un array mediante una funzione ricorsiva...il mio programma si compila ma mi d strani valori....cos' che non v? La logica giusta?

Io l'ho pensato cos:

1) ho un array ordinato di n element

2)chiamo la mia funzione passandogli il puntatore al vettore, la chiave da ricercare, l'elemento pi basso da cui aprtire e quello pi alto dove arrivare)

3)La funzione essendo ricorsiva ha dei casi base che nel mio caso sono:
l'elemento stato trovato e restituisce la posizione nel vettore al chiamante
l'elemento non stato trovato e restituisce -1 al chiamante

4)Se la chiave maggiore dell'elemento di mezzo invoca nuovamente la funzione passandogli come elemento pi basso il vecchio elemento di mezzo + 1 e come elemento pi alto il vecchio elemento pi alto

Se la chiave minore dell'elemento di mezzo invoca nuovamente la funzione passandogli come elemento pi basso il vecchio elemento pi basso e come elemento di mezzo il vecchi elemento di emzzo-1

cmq il codice questo, forse s capisce meglio anche il concetto:



/* Ricerca binaria in un arrya mediante l'uso di una funzione ricorsiva */

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

/* La funzione riceve l'indirizzo al primo elemento del vettore, la chiave,
l'elemento da cui partire, e l'elemento a cui arrivare */
int binric(int *, int, int, int);

int main(){
int a[SIZE] = {1,2,3,4,5,6,7,8,9,10};
int key, risultato;

printf("Inserire un valore da ricercare nell'array: ");
scanf("d", &key);

risultato = binric(a, key, 0, SIZE-1);

if(risultato == -1)
printf("L'elemento inserito non presente nel vettore\n");
else
printf("L'elemento inserito si trova nella %d locazione\n", risultato);

system("PAUSE");
return 0;
}

int binric(int b[], int chiave, int low, int hight){

int midle; // Valore di mezzo
midle = (low+hight)/2;

/* Casi base: se ha trovato la chiave o se non ha trovato la chiav nel
vettore */
if(chiave == b[midle]) // elemento trovato
return midle;
else if(hight <= low) // elemento non trovato
return -1;

/* Se deve continuare la ricerca rinvoca la funzione binric ricorsivamente
fino al ragiungimento di uno dei due casi base */

else if(chiave >= b[midle])
binric(b, chiave, midle+1, hight);
else
binric(b, chiave, low, midle-1);
}


Grazie
Andrea

LeleFT
23-01-2006, 14:57
Il concetto giusto... il codice quasi:


/* Ricerca binaria in un arrya mediante l'uso di una funzione ricorsiva */

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10

/* La funzione riceve l'indirizzo al primo elemento del vettore, la chiave,
l'elemento da cui partire, e l'elemento a cui arrivare */
int binric(int *, int, int, int);

int main(){
int a[SIZE] = {1,2,3,4,5,6,7,8,9,10};
int key, risultato;

printf("Inserire un valore da ricercare nell'array: ");
scanf("%d", &key);

risultato = binric(a, key, 0, SIZE-1);

if(risultato == -1)
printf("L'elemento inserito non presente nel vettore\n");
else
printf("L'elemento inserito si trova nella %d locazione\n", risultato);

system("PAUSE");
return 0;
}

int binric(int b[], int chiave, int low, int hight){

int midle; // Valore di mezzo
midle = (low+hight)/2;

/* Casi base: se ha trovato la chiave o se non ha trovato la chiav nel
vettore */
if(chiave == b[midle]) // elemento trovato
return midle;
else if(hight <= low) // elemento non trovato
return -1;

/* Se deve continuare la ricerca rinvoca la funzione binric ricorsivamente
fino al ragiungimento di uno dei due casi base */

else if(chiave >= b[midle])
return binric(b, chiave, midle+1, hight);
else
return binric(b, chiave, low, midle-1);
}

Ciao. :ciauz:

Loading