Ricerca ternaria in C
Ragazzi che ne dite di questa ricerca ternaria?Funzionale?
Grazie!
#include <stdio.h>
#include <stdlib.h>
int main(void) {
// Dichiarazione di un array di 100 interi
const int maxDim = 100;
int v[maxDim], dimensione, element, counter;
int isFound = 0;
int a, b,c, m;
// Inserimento della dimensione
printf("Inserisci la dimensione dell'array (max %d): ",maxDim);
scanf("%d",&dimensione);
// controllo di allocazione statica
if ((dimensione <= maxDim) && (dimensione > 0)) {
// lettura dell'array
for (counter = 0; counter < dimensione; counter++) {
printf("Inserisci il valore %d-esimo: ",counter);
scanf("%d",&v[counter]);
}
// inserimento elemento da ricercare
printf("Inserisci il valore da cercare: ");
scanf("%d",&element);
// inizio ricerca
a = 0;
b = dimensione - 1;
c= dimensione /2;
if ((v[a] <= element) && (v[b] >= element)) {
isFound = (v[a] == element) || (v[b] == element) || (v[c]==element);
if(element<= v[c]){
while ((c-a != 1)&& (! isFound)){
m=(a+b)/2;
isFound=v[m]==element;
if (element < v[m]){
c=m;
}else{
a=m;
}
}
}
if (element > v[c]){
while ((b-c != 1) && (!isFound)) {
m = (a + b) / 2;
isFound = v[m] == element;
if (v[m] < element)
c = m;
else
b = m;
}
}
}
if (isFound) {
printf("Elemento trovato");
} else {
printf("Elemento non trovato");
}
} else {
printf("Errore: la dimensione inserita è maggiore di %d",maxDim);
}
system ("PAUSE");
return 0;
}Grazie!
Risposte
Si , credo che sia funzionale !
Menale pensa che potrei migliorarlo in qualche verso?
Voglio pensarci un pò su e Le farò sapere ! 
Attendo risposte!
Ciao,
ti prego usa il tag [/code/] mi si girano gli occhi se no
definiscimi: "funzionale"
non mi piace proprio questo pezzo, sarà compilabile ma proprio è da strutturare diversamente
a me non sembra molto una ricerca ternaria come la definisco io, ma correggi i tag e ne riparliamo
ti prego usa il tag [/code/] mi si girano gli occhi se no
definiscimi: "funzionale"
isFound = v[m] == element;
non mi piace proprio questo pezzo, sarà compilabile ma proprio è da strutturare diversamente
a me non sembra molto una ricerca ternaria come la definisco io, ma correggi i tag e ne riparliamo
Intanto utilizza il tag code per inserire il codice (trovi il pulsante nell'editor avanzato e puoi scrivere [ code ] e [ /code ] senza spazi per inserirlo direttamente via codice). Questo vale anche per l'altro programma.
Per prima cosa, perché il tuo programma possa funzionare, gli elementi dovrebbero essere inseriti in ordine dell'array. Suppongo che l'utente sia bravo e che abbia fornito l'input in modo corretto per commentare il seguito, che riporto formattato per comodità.
E' secondo me inutilmente lungo e complicato e non sono neanche certo funzioni correttamente. Non si capisce perché il livello più esterno sia trattato separatamente dagli altri. Inoltre i due cicli più interni sembrano prediligere una singola direzione, mentre è in generale possibile che la direzione cambi tra un livello ed il seguente. Hai provato il codice con diversi array di input? Funziona? Se inserisci per esempio 1 2 3 4 5 6 7 8 9, riesce a trovare 3? riesce a trovare 6?
Per prima cosa, perché il tuo programma possa funzionare, gli elementi dovrebbero essere inseriti in ordine dell'array. Suppongo che l'utente sia bravo e che abbia fornito l'input in modo corretto per commentare il seguito, che riporto formattato per comodità.
// inizio ricerca
a = 0;
b = dimensione - 1;
c= dimensione /2;
if ((v[a] <= element) && (v[b] >= element)) {
isFound = (v[a] == element) || (v[b] == element) || (v[c]==element);
if(element<= v[c]){
while ((c-a != 1)&& (! isFound)){
m=(a+b)/2;
isFound=v[m]==element;
if (element < v[m]){
c=m;
}else{
a=m;
}
}
}
if (element > v[c]){
while ((b-c != 1) && (!isFound)) {
m = (a + b) / 2;
isFound = v[m] == element;
if (v[m] < element)
c = m;
else
b = m;
}
}
}
E' secondo me inutilmente lungo e complicato e non sono neanche certo funzioni correttamente. Non si capisce perché il livello più esterno sia trattato separatamente dagli altri. Inoltre i due cicli più interni sembrano prediligere una singola direzione, mentre è in generale possibile che la direzione cambi tra un livello ed il seguente. Hai provato il codice con diversi array di input? Funziona? Se inserisci per esempio 1 2 3 4 5 6 7 8 9, riesce a trovare 3? riesce a trovare 6?
Ho provato e non ci crederai,ho fatto proprio un caso simile al tuo,ma mi si blocca il pc! Il problema dove risiede?
IN che senso " ti si blocca " ??? IN compilazione o in esecuzione ?
Non mi va avanti! Mi esce una schermata e mi dice che c'è un errore!
Ho finalmente avuto l'occasione di testarlo e in effetti non funziona. Sai cosa sono le funzioni? Sarebbe meglio riscrivere il programma facendone uso ma siccome non mi sembra che tu abbia mai presentato un codice che ne facesse uso, immagino che tu non le abbia mai fatto. Per cui mi limito a correggere il codice.
Per ridurre i livelli di if annidati è a volte utile sfruttare il fatto che inserendo un return all'interno di un if le istruzioni successive non vengono eseguite. È più facile mostrarlo con un esempio. Il tuo codice è strutturato nel modo seguente:
Inserendo il return all'interno del ramo else dell'if e negando la condizione si ottiene la seguente struttura del codice che è probabilmente più semplice da seguire:
La stessa cosa la puoi fare anche per la verifica se l'elemento cercato è all'interno dei valori dell'array. Ma credo ci siano pochi vantaggi a farlo in quel caso.
La parte della lettura dell'array e del numero da cercare è corretta. Quello che è da correggere è invece l'algoritmo di ricerca (che da quello che ne so si chiama ricerca binaria e non ternaria ma forse esiste con qualche modifica anche quello ternario..). Dove hai letto l'algoritmo o la sua descrizione? Quello che deve fare è, ad ogni iterazione verificare in quale metà dell'intervallo (a, b) si trova l'elemento e continuare la ricerca nel nuovo intervallo (a, c) o (c, b). In altre parole l'algoritmo dovrebbe assomigliare a qualcosa come il seguente:
Per ridurre i livelli di if annidati è a volte utile sfruttare il fatto che inserendo un return all'interno di un if le istruzioni successive non vengono eseguite. È più facile mostrarlo con un esempio. Il tuo codice è strutturato nel modo seguente:
/* ... */
if ((dimensione <= maxDim) && (dimensione > 0)) {
/* ... gran parte del codice ... */
} else {
printf("Errore: la dimensione inserita è maggiore di %d",maxDim);
}
system ("PAUSE");
return 0;
Inserendo il return all'interno del ramo else dell'if e negando la condizione si ottiene la seguente struttura del codice che è probabilmente più semplice da seguire:
/* ... */
if (dimensione > maxDim || dimensione <= 0) {
printf("Errore: la dimensione inserita è maggiore di %d\n", maxDim);
/* system("PAUSE"); è inutile e ci sono buone ragioni per non usarlo... */
return 1; /* lo 0 è normalmente usato per indicare che l'esecuzione è andata a buon fine.. */
}
/* ... gran parte del codice ... */
return 0;
La stessa cosa la puoi fare anche per la verifica se l'elemento cercato è all'interno dei valori dell'array. Ma credo ci siano pochi vantaggi a farlo in quel caso.
La parte della lettura dell'array e del numero da cercare è corretta. Quello che è da correggere è invece l'algoritmo di ricerca (che da quello che ne so si chiama ricerca binaria e non ternaria ma forse esiste con qualche modifica anche quello ternario..). Dove hai letto l'algoritmo o la sua descrizione? Quello che deve fare è, ad ogni iterazione verificare in quale metà dell'intervallo (a, b) si trova l'elemento e continuare la ricerca nel nuovo intervallo (a, c) o (c, b). In altre parole l'algoritmo dovrebbe assomigliare a qualcosa come il seguente:
while (a < b) {
int c = (a + b)/2;
if (element == c) {
/* trovato ... */
break;
} else if (element < c) {
/* cerca in intervallo più basso... */
b = c;
} else {
/* cerca in intervallo più alto... */
a = c;
}
}
OK ! Ma durante la compilazione oppure in esecuzione ????????????????
Non ho capito.. a cosa ti riferisci esattamente?
Questo era un esercizio dato da un professore durante la seduta d'esame. Conosco le funzioni,le uso spesso,ma sul pc non riesco a capire come e dove scriverle! Poi invece di tutti quei if non sarebbe meglio uno switch o mi complico la vita?
Il programma non funziona in fase di esecuzione, ma viene compilato correttamente (a patto di usare un compilatore che supporti almeno parzialmente il C99). Uno switch non aiuta perché gli if non sono del tipo corretto. Siccome non si tratta di un compito ti mostro come avrei scritto il programma (l'ho scritto pensando al C99 per cui esiste il tipo _Bool rinominato in bool all'interno di stdbool.h e posso definire le variabili dove voglio*).
L'utilizzo della ricorsione è in questo caso utile. È anche possibile scriverlo in versione ricorsiva:
Puoi vedere come nel codice gli if vengano spesso usati per uscire prima dalla funzione o dal programma.
* Se stai usando un compilatore basato su gcc credo sia necessario inserire l'opzione -std=c99. Per passare ad un programma compilabile con il vecchi standard è necessario definire manualmente il tipo bool (o usare un int) e definire tutte le variabili all'inizio del blocco di esistenza.
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool search(int *, unsigned, int);
int main()
{
unsigned dim = 0;
fputs("Inserisci la dimensione dell'array: ", stdout);
scanf("%u", &dim);
if (dim == 0) {
fputs("Dimensione dell'array non valida.\n\n", stderr);
return 1;
}
int *array = malloc(dim * sizeof(int));
if (array == NULL) {
fputs("Impossibile allocare l'array.\n\n", stderr);
return 2;
}
puts("Inserisci i valori dell'array.");
scanf("%d", &array[0]);
for (int i = 1; i < dim; ++i) {
scanf("%d", &array[i]);
if (array[i-1] > array[i]) {
fputs("Gli elementi dell'array devono essere in ordine crescente.\n\n", stderr);
return 3;
}
}
int value = 0;
fputs("Inserisci il valore da cercare nell'array: ", stdout);
scanf("%d", &value);
bool result = search(array, dim, value);
if (result) {
puts("Elemento trovato.\n");
} else {
puts("Elemento non trovato.\n");
}
return 0;
}
bool search(int *array, unsigned dim, int value)
{
if (dim <= 0 || array == NULL || value < array[0] || value > array[dim - 1]) {
return false;
}
if (value == array[0] || value == array[dim-1]) {
return true;
}
unsigned c = dim / 2;
if (value <= array[c]) {
return search(array, c+1, value);
} else {
return search(array+c+1, dim-c-1, value);
}
}
L'utilizzo della ricorsione è in questo caso utile. È anche possibile scriverlo in versione ricorsiva:
bool search(int *array, unsigned dim, int value)
{
if (dim <= 0 || array == NULL || value < array[0] || value > array[dim - 1]) {
return false;
}
if (value == array[0] || value == array[dim - 1]) {
return true;
}
unsigned a = 0;
unsigned b = dim - 1;
while (a <= b) {
unsigned c = a + (b - a)/2;
if (array[c] == value) {
return true;
} else if (array[c] < value) {
b = c;
} else {
a = c+1;
}
}
return false;
}
Puoi vedere come nel codice gli if vengano spesso usati per uscire prima dalla funzione o dal programma.
* Se stai usando un compilatore basato su gcc credo sia necessario inserire l'opzione -std=c99. Per passare ad un programma compilabile con il vecchi standard è necessario definire manualmente il tipo bool (o usare un int) e definire tutte le variabili all'inizio del blocco di esistenza.
Cavolo non era per niente banale! o.o
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo