D4rkAng3l
23-01-2006, 11:26
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
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