Problema programma col linguaggio C
Questo è il codice evidentemente sbagliato, ma non riesco a capire dov'è che sbaglio!!
In sintesi l'utente digiterà prima la dimensione dell'array, poi digita i numeri e infine il numero che deve essere cercato (key). Ho dovuto svolgere questo esercizio con la ricorsione, ma il programma si blocca e non capisco il perchè!
PS: uso il "dev C++ " per programmare col linguaggio C.
#include
#include
//protos
int linear_search(const int a[], int key, int low, int high);
void implemention_sort(int a[], int size);
//il programma inizia col main
int main(int argc, char *argv[]){
int size, count, key;
printf("quanti numeri devi inserire? : \t");
scanf("%d\n", &size);
int array[size];
printf("inserisci i numeri:\n");
for (count = 0; count < size; count++){
scanf("%d\n\n", &array[count]);//non gli sto mettendo il & e mi ha detto che ho sbagliato
}//fine for
implemention_sort(array, size);
printf("ecco l'array ordinato: \n");
for(count = 0; count < size; count++){
printf("\n %d \n", array[count]);
}//fine for
printf("inserisci il numero da cercare: \t");
scanf("%d\n", &key);
printf("\n\n[%d]", linear_search(array, key, 0, size - 1));
system("PAUSE");
}//fine main
//funzioni
int linear_search(const int array[], int key, int low, int high){
int middle = (low + high)/2;
if (key < array[middle]){
linear_search(array, key, 0, middle - 1);
}//fine if esterno
else if(key > array[middle]){
linear_search(array, key, middle + 1, high);
}//fine else if esterno
else if(key == array[middle]){
return middle;
}//fine secondo else if
else{
printf("-1 significa che non è stato trovato.");
return -1;
}//fine else
}//fine funzione
//alra funzione
void implemention_sort(int a[], int size){
int j; //contatore
int temp;
if (size == 0){
}//fine if
else{
for (j = 0; j < size; j++){
if (a[j + 1] < a[j]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}//fine for
}//fine for
implemention_sort(a, size - 1);
}//fine else
}//fine funzione
Grazie mille dell'aiuto
In sintesi l'utente digiterà prima la dimensione dell'array, poi digita i numeri e infine il numero che deve essere cercato (key). Ho dovuto svolgere questo esercizio con la ricorsione, ma il programma si blocca e non capisco il perchè!
PS: uso il "dev C++ " per programmare col linguaggio C.
#include
#include
//protos
int linear_search(const int a[], int key, int low, int high);
void implemention_sort(int a[], int size);
//il programma inizia col main
int main(int argc, char *argv[]){
int size, count, key;
printf("quanti numeri devi inserire? : \t");
scanf("%d\n", &size);
int array[size];
printf("inserisci i numeri:\n");
for (count = 0; count < size; count++){
scanf("%d\n\n", &array[count]);//non gli sto mettendo il & e mi ha detto che ho sbagliato
}//fine for
implemention_sort(array, size);
printf("ecco l'array ordinato: \n");
for(count = 0; count < size; count++){
printf("\n %d \n", array[count]);
}//fine for
printf("inserisci il numero da cercare: \t");
scanf("%d\n", &key);
printf("\n\n[%d]", linear_search(array, key, 0, size - 1));
system("PAUSE");
}//fine main
//funzioni
int linear_search(const int array[], int key, int low, int high){
int middle = (low + high)/2;
if (key < array[middle]){
linear_search(array, key, 0, middle - 1);
}//fine if esterno
else if(key > array[middle]){
linear_search(array, key, middle + 1, high);
}//fine else if esterno
else if(key == array[middle]){
return middle;
}//fine secondo else if
else{
printf("-1 significa che non è stato trovato.");
return -1;
}//fine else
}//fine funzione
//alra funzione
void implemention_sort(int a[], int size){
int j; //contatore
int temp;
if (size == 0){
}//fine if
else{
for (j = 0; j < size; j++){
if (a[j + 1] < a[j]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}//fine for
}//fine for
implemention_sort(a, size - 1);
}//fine else
}//fine funzione
Grazie mille dell'aiuto
Risposte
ciao, ci sono un pochino di imperfezioni:
nella scanf come primo argomento devi mettere solo il tipo di dato che si aspetta, senza altri caratteri. Per andare a capo devi mettere un printf("\n") separato
l'algoritmo di sort dell'array è quello che incasina il tutto, infatti se per prova fai un print dell'array prima di fare il sort, avrai degli elementi diversi da quelli dopo il sort. Questo perchè durante il sort, l'algoritmo pesca degli elementi in locazioni di memoria esterne all'array. Questo avviene per il controllo a[j + 1] < a[j] in
cosi facendo, quando arrivi all'ultimo j del ciclo, vai fuori dall'array a prendere un altro valore in memoria, inserendolo nell'array come ultimo valore al posto di quello già presente se più piccolo. Cosi facendo introduci nell'array un nuovo valore e ne togli uno di quelli inseriti dall'utente.
Per risolvere il problema devi riscrivere il ciclo for con j < size-1 , ovvero:
cosi l'array viene ordinato correttamente.
altro scanf da correggere.
Ora funziona
p.s. aggiungi uno \n alla fine di
trasformandolo in
se no ti si attacca il risultato alla nuova dicitura del prompt dei comandi
int size, count, key;
printf("quanti numeri devi inserire? : \t");
scanf("%d", &size); // Scanf corretto
printf ("\nnumero inserito\n");
int array[size];
printf("inserisci i numeri:\n");
for (count = 0; count < size; count++){
scanf("%d\n\n", &array[count]);//non gli sto mettendo il & e mi ha detto che ho sbagliato
}//fine for
nella scanf come primo argomento devi mettere solo il tipo di dato che si aspetta, senza altri caratteri. Per andare a capo devi mettere un printf("\n") separato
implemention_sort(array, size);
l'algoritmo di sort dell'array è quello che incasina il tutto, infatti se per prova fai un print dell'array prima di fare il sort, avrai degli elementi diversi da quelli dopo il sort. Questo perchè durante il sort, l'algoritmo pesca degli elementi in locazioni di memoria esterne all'array. Questo avviene per il controllo a[j + 1] < a[j] in
for (j = 0; j < size; j++) {
if (a[j + 1] < a[j]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}//fine for
}//fine for
cosi facendo, quando arrivi all'ultimo j del ciclo, vai fuori dall'array a prendere un altro valore in memoria, inserendolo nell'array come ultimo valore al posto di quello già presente se più piccolo. Cosi facendo introduci nell'array un nuovo valore e ne togli uno di quelli inseriti dall'utente.
Per risolvere il problema devi riscrivere il ciclo for con j < size-1 , ovvero:
for (j = 0; j < size-1; j++) {
if (a[j + 1] < a[j]){
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}//fine for
}//fine for
cosi l'array viene ordinato correttamente.
printf("inserisci il numero da cercare: \t");
scanf("%d\n", &key);
altro scanf da correggere.
Ora funziona
p.s. aggiungi uno \n alla fine di
printf("\n\n[%d]", linear_search(array, key, 0, size - 1));
trasformandolo in
printf("\n\n[%d]\n", linear_search(array, key, 0, size - 1));
se no ti si attacca il risultato alla nuova dicitura del prompt dei comandi
Scusa ma l'esercizio consiste solo nell'immissione di numeri in un array e nella ricerca di un valore tra di essi?
Se così:
Se non ti risposto come volevi scusami.
Se così:
Se non ti risposto come volevi scusami.
in pratica i due programmi fanno la stessa cosa, ma mi pare di aver capito che venisse richiesta la ricorsione e l'uso dell'algoritmo di ricerca binario (ricorsivo).
[EDIT] La ricerca binaria è inoltre computazionalmente megllio di quella sequenziale, infatti:
La ricerca sequenziale (cicla tutto fino a che non trovi l'array), ha i seguenti comportamenti:
caso peggiore: $O(n)$ [elemento non presente]
caso medio $O(n/2)$ [elemento nell'array]
caso ottimo: $O(1)$ [elemento come prmo valore dell'array]
La ricerca binaria ha invece i seguenti comportamenti:
caso peggiore: $O(logn)$ [elemento non presente]
caso medio $O(logn)$ [elemento nell'array]
caso ottimo: $O(1)$ [elemento nel centro dell'array]
[EDIT] La ricerca binaria è inoltre computazionalmente megllio di quella sequenziale, infatti:
La ricerca sequenziale (cicla tutto fino a che non trovi l'array), ha i seguenti comportamenti:
caso peggiore: $O(n)$ [elemento non presente]
caso medio $O(n/2)$ [elemento nell'array]
caso ottimo: $O(1)$ [elemento come prmo valore dell'array]
La ricerca binaria ha invece i seguenti comportamenti:
caso peggiore: $O(logn)$ [elemento non presente]
caso medio $O(logn)$ [elemento nell'array]
caso ottimo: $O(1)$ [elemento nel centro dell'array]
Ok. Perchè se fosse stato solo così, quello sarebbe stato un metodo più veloce. Ciao.
più veloce da scrivere, ma meno veloce a livello computazionale 
Non lo so questo. Ma se lo dici tu mi fido 
"sapo93":
in pratica i due programmi fanno la stessa cosa, ma mi pare di aver capito che venisse richiesta la ricorsione e l'uso dell'algoritmo di ricerca binario (ricorsivo).
[EDIT] La ricerca binaria è inoltre computazionalmente megllio di quella sequenziale, infatti:
La ricerca sequenziale (cicla tutto fino a che non trovi l'array), ha i seguenti comportamenti:
caso peggiore: $O(n)$ [elemento non presente]
caso medio $O(n/2)$ [elemento nell'array]
caso ottimo: $O(1)$ [elemento come prmo valore dell'array]
La ricerca binaria ha invece i seguenti comportamenti:
caso peggiore: $O(logn)$ [elemento non presente]
caso medio $O(logn)$ [elemento nell'array]
caso ottimo: $O(1)$ [elemento nel centro dell'array]
In realtà, nel secondo caso, devi fare l'ordinamento. Quindi devi aggiungere la complessità dell'ordinamento che rende il secondo algoritmo sempre peggio dell'algoritmo base. Inoltre, e questo purtroppo è poco puntualizzato nei corsi, la ricerca binaria produce tantissimi cache missing. Siccome i cache missing sovrastano i tempi delle altre operazioni, questo rende la ricerca binaria molto meno appetibile di quanto possa sembrare. Incomincia sempre dagli algoritmi più semplici.
In realtà invece che poco puntualizzato penso proprio che sia inesistente.
Non so in altri corsi, ma ad informatica in Bicocca tutti i corsi di algoritmi non si interessano dei problemi tecnici, resta tutto a livello teorico. E' prevista una parte applicativa, ma si riduce all'implementazione di quello imparato a lezione, senza ragionamenti sull'effettiva differenza tra prestazioni in teoria e prestazioni in pratica.
Ho sentito parlare di cache missing solo trattando di architettura degli elaboratori
Non so in altri corsi, ma ad informatica in Bicocca tutti i corsi di algoritmi non si interessano dei problemi tecnici, resta tutto a livello teorico. E' prevista una parte applicativa, ma si riduce all'implementazione di quello imparato a lezione, senza ragionamenti sull'effettiva differenza tra prestazioni in teoria e prestazioni in pratica.
Ho sentito parlare di cache missing solo trattando di architettura degli elaboratori
Non saprei comunque in che condizioni convenga usare l'uno rispetto all'altro. In questo caso era il passo di ordinamento a rendere la ricerca binaria poco appetibile. D'altra parte se devi fare molte ricerche allora il peso del sort si riduce.
P.S.: Ho notato che nel tuo progetto numC hai definito le matrici come puntatori di puntatori a double. Spesso, in realtà, si preferisce usare un puntatore a double semplice e accedere all'elemento m[j] come m[i * row_size + j] oppure m[j * col_size + i]. Tra l'altro il primo è il modo in cui sono memorizzate in memoria gli array multidimensionali in C (il secondo è quello del Fortran). La gestione della memoria è più semplice ed è più facile scrivere buoni codici.
P.S.: Ho notato che nel tuo progetto numC hai definito le matrici come puntatori di puntatori a double. Spesso, in realtà, si preferisce usare un puntatore a double semplice e accedere all'elemento m[j] come m[i * row_size + j] oppure m[j * col_size + i]. Tra l'altro il primo è il modo in cui sono memorizzate in memoria gli array multidimensionali in C (il secondo è quello del Fortran). La gestione della memoria è più semplice ed è più facile scrivere buoni codici.
"sapo93":
ciao, ci sono un pochino di imperfezioni:
int size, count, key; printf("quanti numeri devi inserire? : \t"); scanf("%d", &size); // Scanf corretto printf ("\nnumero inserito\n"); int array[size]; printf("inserisci i numeri:\n"); for (count = 0; count < size; count++){ scanf("%d\n\n", &array[count]);//non gli sto mettendo il & e mi ha detto che ho sbagliato }//fine for
nella scanf come primo argomento devi mettere solo il tipo di dato che si aspetta, senza altri caratteri. Per andare a capo devi mettere un printf("\n") separato
implemention_sort(array, size);
l'algoritmo di sort dell'array è quello che incasina il tutto, infatti se per prova fai un print dell'array prima di fare il sort, avrai degli elementi diversi da quelli dopo il sort. Questo perchè durante il sort, l'algoritmo pesca degli elementi in locazioni di memoria esterne all'array. Questo avviene per il controllo a[j + 1] < a[j] in
for (j = 0; j < size; j++) { if (a[j + 1] < a[j]){ temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; }//fine for }//fine for
cosi facendo, quando arrivi all'ultimo j del ciclo, vai fuori dall'array a prendere un altro valore in memoria, inserendolo nell'array come ultimo valore al posto di quello già presente se più piccolo. Cosi facendo introduci nell'array un nuovo valore e ne togli uno di quelli inseriti dall'utente.
Per risolvere il problema devi riscrivere il ciclo for con j < size-1 , ovvero:
for (j = 0; j < size-1; j++) { if (a[j + 1] < a[j]){ temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; }//fine for }//fine for
cosi l'array viene ordinato correttamente.
printf("inserisci il numero da cercare: \t"); scanf("%d\n", &key);
altro scanf da correggere.
Ora funziona
p.s. aggiungi uno \n alla fine di
printf("\n\n[%d]", linear_search(array, key, 0, size - 1));
trasformandolo in
printf("\n\n[%d]\n", linear_search(array, key, 0, size - 1));
se no ti si attacca il risultato alla nuova dicitura del prompt dei comandi
Sei stato davvero molto gentile!!! grazie mille!!!
D purtroppo mi è sfuggita questa parte dello scanf che non stampa a video la newline (ci potevo arrivare con la logica, la scanf prende in input, mica output xD)."kobeilprofeta":
Scusa ma l'esercizio consiste solo nell'immissione di numeri in un array e nella ricerca di un valore tra di essi?
Se così:
Se non ti risposto come volevi scusami.
Scusate ma a cosa serve la funzione "getch()" ?? fa parte dello standard? io non credo di averlo mai incontrato...grazie!
"sapo93":
in pratica i due programmi fanno la stessa cosa, ma mi pare di aver capito che venisse richiesta la ricorsione e l'uso dell'algoritmo di ricerca binario (ricorsivo).
[EDIT] La ricerca binaria è inoltre computazionalmente megllio di quella sequenziale, infatti:
La ricerca sequenziale (cicla tutto fino a che non trovi l'array), ha i seguenti comportamenti:
caso peggiore: $ O(n) $ [elemento non presente]
caso medio $ O(n/2) $ [elemento nell'array]
caso ottimo: $ O(1) $ [elemento come prmo valore dell'array]
La ricerca binaria ha invece i seguenti comportamenti:
caso peggiore: $ O(logn) $ [elemento non presente]
caso medio $ O(logn) $ [elemento nell'array]
caso ottimo: $ O(1) $ [elemento nel centro dell'array]
Si si, hai capito perfettamente :3
PS Grazie a tutti dell'aiuto!!!! davvero gentili e veloci nel rispondere !!
la funzione getch() appartiene all'header conio.h, e aspetta che l'utente dia in input un qualunque carattere (numeri, lettere e simboli). Una volta che riceve il carattere, il programma va avanti con la normale esecuzione. Di solito si mette alla fine del programma per far decidere all'utente quando terminarlo.
Si usa ad esempio per bloccare il programma in modo che l'utente possa leggere l'output senza che esso vada avanti o si chiuda (ad esempio ci sono alcune console linux che si chiudono quando il programma che viene eseguito dentro di esse si chiude)
EDIT L'esempio non è proprio corretto perché in molti compilatori linux non esiste l'header conio.h. Non fa parte della libreria standard del C ma alla famiglia posix
p.s. @vict85 quel codice l'ho fatto tempo fa, volevo metterci un po mano ma gli esami hanno un livello di priorità maggiore (dovrei passare ad un round robin
).Quando ho un po di tempo provo
Grazie per il suggerimento
Si usa ad esempio per bloccare il programma in modo che l'utente possa leggere l'output senza che esso vada avanti o si chiuda (ad esempio ci sono alcune console linux che si chiudono quando il programma che viene eseguito dentro di esse si chiude)
EDIT L'esempio non è proprio corretto perché in molti compilatori linux non esiste l'header conio.h. Non fa parte della libreria standard del C ma alla famiglia posix
p.s. @vict85 quel codice l'ho fatto tempo fa, volevo metterci un po mano ma gli esami hanno un livello di priorità maggiore (dovrei passare ad un round robin
).Quando ho un po di tempo provo Grazie per il suggerimento
"sapo93":
EDIT L'esempio non è proprio corretto perché in molti compilatori linux non esiste l'header conio.h. Non fa parte della libreria standard del C ma alla famiglia posix
Non fa parte delle librerie posix (altrimenti ci sarebbe su tutti i linux[nota]Su posix c'è una libreria con scopi simili e si chiama ncurses.h (che è un clone di curses.h su unix)[/nota]). Conio è un libreria MS-DOS e non sono sicuro sia molto amata neanche alla Microsoft
.
"vict85":
[quote="sapo93"]EDIT L'esempio non è proprio corretto perché in molti compilatori linux non esiste l'header conio.h. Non fa parte della libreria standard del C ma alla famiglia posix
Non fa parte delle librerie posix (altrimenti ci sarebbe su tutti i linux). Conio è un libreria MS-DOS e non sono sicuro sia molto amata neanche alla Microsoft
.[/quote]si si, hai ragione.
Scusate ma ero un po sbarellato dopo 3 ore di sistemi distribuiti. La fonte che ho letto dice espressamente
Non appartiene nemmeno allo standard POSIX
che io ho letto come appartiene allo standard POSIX.
Mi pareva strano che se appartenesse a POSIX non ci fosse su sistemi linux, ma non ci ho'dato troppo peso
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo