Salve a tutti!!! Avrei una domanda da fare,riguarda alla RICERCA DICOTOMICA !
Qui sotto vi riporto l'esercizio tra quelli svolti per la settimana scorsa, e il testo chiedeva di allocare un vettore di interi,e di effettuare la ricerca di un intero all'interno del vettore creato,prima con una funzione cerca,poi con una funzione cerca_vettore_ordinato !
La prof mi ha dato errore scrivendomi di "effettuare una ricerca dicotomica sul vettore ordinato"...
Allora, IN PRIMIS , il vettore è ordinato, perchè dopo la prima chiamata a funzione (cerca() ) ho usato la qsort per ordinare gli interi,e poi ho rieffettuato la ricerca su un vettore ordinato per l'appunto! Lei intende forse che devo fare la ricerca partendo dal mezzo,esempio metto 100 interi,partendi da 50 e poi scartare quelli inferiori o superiori al 50 in base all'intero che ricerco???
int cerca();
int Ordinamento ( const void *P, const void *S )/* Funzione qsort per ordinare in ordine crescente gli interi inseriti nel vettore*/
{
int *a, *b ;
a = (int*) P ;
b = (int*) S ;
if ( *a == *b )
{
return 0;
}
if ( *a < *b )
{
return -1;
}
if ( *a > *b )
{
return 1;
}
}
int main()
{
int *vettore, k = 0, dimensione = 0, i, cercato = 0, n = 0, m = 0 ;
srand((int) time(NULL));
system("color 0A");
printf("Inserire quanti numeri RANDOM si vogliono creare : ");
fflush(stdin);
k = scanf("%d", &dimensione);
while( k == 0 )
{
printf("Errore di Input");
fflush(stdin);
k = scanf("%d", &dimensione);
}
vettore = (int*) malloc ( dimensione * sizeof(int));
for(i = 0; i < dimensione ; i++)/*Generazione dei numeri interi nel vettore in maniera random da -100 a +100 */
{
vettore[i] = -100 + (rand()% 200);
}
printf("\nI numeri creati RANDOM sono : ");
for( i = 0 ; i < dimensione ; i++ )
{
printf("%d ",vettore[i]);
}
k = 0;
printf("\n\nInserire il numero che si vuol ricercare : ");
fflush(stdin);
k = scanf("%d", &cercato);
while( k == 0 )
{
printf("\nErrore di Input!");
fflush(stdin);
k = scanf("%d", &cercato);
}
i = cerca(vettore, dimensione, cercato);
if( i == -1 )/* Se la funzione restituisce -1 il valore non è presente nel vettore */
{
system("cls");
system("color C0");
printf("\n\t\t IL NUMERO NON E' PRESENTE NEL VETTORE!!!\n\n");
printf("\t\t FINE PRIMA PARTE CON VETTORE NON ORDINATO!\n\n");
system("pause");
}
if ( i >= 0 )/* Se la funzione restituisce 1 il valore è presente nel vettore */
{
system("cls");
system("color 0A");
printf("\n\t\t IL NUMERO %d SI TROVA ALL'INDICE %d\n\n", vettore[i], i );
printf("\t\t FINE PRIMA PARTE CON VETTORE NON ORDINATO!\n\n");
system("pause");
}
system("cls");
system("color 0A");
fflush(stdin);
printf("\t\t\tSECONDA PARTE DELL'ESERCIZIO\n\tNUMERI RANDOM ORDINATI IN ORDINE CRESCENTE TRAMITE FUNZIONE\n\n");
/* ** SECONDA PARTE DEL PROGRAMMA ** */
qsort(vettore, dimensione, sizeof(int), Ordinamento ); /* Con la funzione qsort,richiamando il vettore in questione e la funziona "Ordinamento" */
/* sistemo in ordine crescente i i numeri interi inseriti in maniera random nel vettore */
printf("I numeri in ORDINE CRESCENTE creati Random sono : ");
for( i = 0 ; i < dimensione ; i++ )
{
printf("%d ",vettore[i]);
}
k = 0;
printf("\n\nInserire il numero che si vuol ricercare : ");
fflush(stdin);
k = scanf("%d", &cercato);
while( k == 0 )
{
printf("\nErrore di Input!");
fflush(stdin);
k = scanf("%d", &cercato);
}
i = 0;
i = cerca(vettore, dimensione, cercato);
if( i == -1 )/* Se la funzione restituisce -1 il valore non è presente nel vettore */
{
system("cls");
system("color C0");
printf("\n\t\t IL NUMERO NON E' PRESENTE NEL VETTORE!!!\n\n");
printf("\t\t FINE SECONDA PARTE CON VETTORE ORDINATO!\n\n");
free(vettore);
system("pause");
return 0;
}
if ( i >= 0 )/* Se la funzione restituisce 1 il valore è presente nel vettore */
{
system("cls");
system("color 0A");
printf("\n\t\t IL NUMERO %d SI TROVA ALL'INDICE %d\n\n", vettore[i], i );
printf("\t\t FINE SECONDA PARTE CON VETTORE ORDINATO!\n\n");
free(vettore);
system("pause");
return 0;
}
}
int cerca(int vettore[], int dimensione, int cercato)/* Funzione per cercare un numero nel vettore creato */
{
int i, k , ctrl = 0 ;
fflush(stdin);
for ( i = 0 ; i < dimensione ; i++ )
{
if( vettore[i] == cercato )
{
ctrl = ctrl + 1;
break;
}
}
if( ctrl == 0 )
{
return -1;
}
if( ctrl == 1 )
{
return i;
}
}