Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Ricerca in array con funzione ricorsiva [C++]
Forum - C/C++ - Ricerca in array con funzione ricorsiva [C++]

Pagine: [ 1 2 3 4 ] Precedente | Prossimo
Avatar
cos.peluso (Normal User)
Newbie


Messaggi: 18
Iscritto: 03/01/2018

Segnala al moderatore
Postato alle 17:11
Domenica, 07/01/2018
Raga sono di nuovo qui e la cosa non è positiva :(
Oggi sono alle prese con queste tracce:

-Realizzare una funzione ricorsiva che ricerca un elemento x in un array ordinato di interi.

-Scrivere una funzione ricorsiva che controlla se una parola è palindroma, ovvero se “rigirandola” non cambia.

La seconda traccia non l'ho ancora neanche provata a svolgere e quindi per il momento non chiedo nulla, perchè spero di saperla fare dopo aver risolto i problemi con la prima.
Ora, io ho capito il funzionamento di una funzione ricorsiva, e ho capito che devo cercare prima di tutto un "passo base"; solo che nel mio caso non riesco a trovarlo. Posto il codice che ho scritto fino e ora, ma è incompleto per il motivo che vi ho detto :(

Codice sorgente - presumibilmente C++

  1. //Rierca valore in array tramite ricorsiva
  2. #include <iostream>
  3. using namespace std;
  4. #define N 8
  5. typedef int vettore[N];
  6. vettore vett;
  7. int posizione;
  8.  
  9. int ricerca(vettore,int a);
  10.  
  11. int main(){
  12.         int input,posizione;
  13.         for(int i=0;i<N;i++){
  14.                 cout<<"Inserire un valore nell'array : ";
  15.                 cin>> vett[i];
  16.         }
  17.        
  18.         cout<<"Inserire l'elemento da cercare : ";
  19.         cin>>input;
  20.         posizione = ricerca(vett,input);
  21.        
  22.         }
  23.        
  24.         int ricerca(vettore,int a){
  25.                 }



Non sto chiedendo di scrivermi il codice, ma qualche suggerimento su come impostare la funzione ricorsiva sarebbe possibile?

N.B :Per il momento non sto considerando l'array ordinato, ne ho semplicemente inserito uno generico.

Ultima modifica effettuata da cos.peluso il 07/01/2018 alle 17:23
PM Quote
Avatar
Mikelius (Member)
Expert


Messaggi: 274
Iscritto: 14/04/2017

Segnala al moderatore
Postato alle 17:50
Domenica, 07/01/2018
La funzione ricorsiva, è una funzione che richiama se stessa
Esempio di Array Ordinato:

0
1
2
3
4
5
6
7
8
9

Per cercare un numero, la soluzione più semplice sarebbe confrontare il numero cercato con tutti gli elementi dell array finchè non trovi quello che cerchi. Sapendo che l'array è ordinato (in modo crescente ad esempio) puo confrontarli finchè il numero cercato è minore del numero con cui effettui il confronto.
Se il numero cercato è 0, al primo confronto lo trovi, se è 9 , ci voranno 10 confronti.


Ad esempio cerchiamo il numero 8 (chiamiamolo X) , e vediamo (ragionando senza scrivere codice per ora).

Un metodo che potresti utilizzare è quello di dividere l'array in 2 parti, dal 0-4 e dal 5-9 .
Se X < di 4 (che è il limite del primo blocco) sarà sicuramente nel 1° blocco, se maggiore sicuramente nel 2° .
Esssendo magiore , sarà nel2° blocco (5-9).
Ora ripetiamo il ragionamento e dividiamo il blocco in altre 2 parti (5-7 e 8-9). Ragianando come prima vedrai che X sta nel "nuovo" 2° blocco (8-9).
Di nuovo ripetiamo il ragionamento. dividendo il blocco in 2 parti. (8 e 9). Con il confronto avrai trovato il tuo elemento.
Questo è un ragionamento possibile per sfongere la tua funzione. Ora se hai capito il meccanismo, prova ad implementarlo tu.


"Io ne ho viste cose che voi umani non potreste immaginarvi...."
PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 431
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 17:54
Domenica, 07/01/2018
Siccome l'array è ordinato puoi usare il binary search come dice Mikelius; una alternativa nel caso non lo fosse sarebbe quella di dividere l'array in due parti: una la testa (head) che sarebbe il primo elemento, e l'altra la coda (tail) che rappresenta tutti gli altri elementi.

Se l'elemento da cercare è la testa, allora ritorni la posizione, altrimenti richiami ricorsivamente la funzione sulla coda.

Siccome creare nuovi array da passare alla funzione ricorsiva di base diventa macchinoso, ti conviene aggiungere un parametro che indichi la posizione da cui parte l'array considerato nella funzione ricorsiva (al caso base, 0).

Se invece adotti la soluzione di mikelius ti serviranno due parametri in più, che indicano la posizione iniziale e finale del pezzo di array che consideri (caso base 0 e lunghezza, cioè estremo finale escluso).

Ultima modifica effettuata da lumo il 07/01/2018 alle 17:58
PM Quote
Avatar
cos.peluso (Normal User)
Newbie


Messaggi: 18
Iscritto: 03/01/2018

Segnala al moderatore
Postato alle 12:15
Lunedì, 08/01/2018
Allora, ho scritto questo codice :


Codice sorgente - presumibilmente C++

  1. //Rierca valore in array tramite ricorsiva
  2. #include <iostream>
  3. using namespace std;
  4. #define N 8
  5. int posizione;
  6.  
  7. int ricerca(int v[],int start,int end,int search);
  8.  
  9. int main(){
  10.         int input,posizione;
  11.         int vett[8]={1,2,3,4,5,6,7,8};
  12.        
  13.         cout<<"Inserire l'elemento da cercare : ";
  14.         cin>>input;
  15.         posizione = ricerca(vett,0,N-1,input);
  16.        
  17.         cout<<"La posizione e' : "<<posizione<<endl;
  18.         }
  19.        
  20.         int ricerca(int v[],int start,int end,int search){
  21.                 int med;
  22.                 med= (start + (end-start))/2;
  23.                
  24.                 if(v[med]==search)
  25.                 {
  26.                         return med;
  27.                 }
  28.                 else
  29.                 if (v[med]<search){
  30.                         return ricerca(v,med+1,end,search);
  31.                 }
  32.                 else
  33.                 if(v[med]>search){
  34.                         return ricerca(v,start,med-1,search);
  35.                 }
  36.        
  37.         }





Ho ancora ancora dei dubbi, il processo credo di averlo scritto più o meno bene, però , come faccio a inserire nella funzione ricorsiva anche il caso in cui il valore cercato non sia presente ?
Inoltre per alcuni valori che inserisco, mi dice che il nomefile.exe ha smesso di funzionare , è un problema del mio computer o fa sempre parte di un errore nel mio codice ?

Ultima modifica effettuata da cos.peluso il 08/01/2018 alle 12:31
PM Quote
Avatar
2018_GPCPP (Normal User)
Newbie


Messaggi: 8
Iscritto: 04/01/2018

Segnala al moderatore
Postato alle 20:13
Lunedì, 08/01/2018
Ciao,

ho provato il tuo codice, funziona per alcuni numeri, mentre inserendo un 6 pare che vada in loop generando l'errore.
Se la richiesta non specifica algoritmi più complessi fossi in te per semplicità di scrittura proseguirei con una ricerca sequenziale.
Cercando ovviamente di strutturare il codice in maniera più leggibile.

PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 431
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 20:42
Lunedì, 08/01/2018
Ci sono vari problemi

Codice sorgente - presumibilmente Plain Text

  1. med= (start + (end-start))/2;



qua verrà end/2, che non va bene. Ti serve (start+end)/2 (provare qualche esempio per credere)

Codice sorgente - presumibilmente C/C++

  1. return ricerca(v,start,med-1,search);


Togli il -1 perché l'estremo superiore è incluso (altrimenti bisogna rimaneggiare le formule).
Per coerenza
Codice sorgente - presumibilmente Plain Text

  1. posizione = ricerca(vett,0,N-1,input);


metti 0, N.

Il crash lo hai perché quando l'elemento non viene trovato, la ricerca va avanti fuori dagli indici consentiti, e questo causa un segmentation fault (il sistema operativo si accorge che accedi ad aree di memoria non allocate dal tuo programma).
Devi mettere un controllo all'inizio della funzione che controlla questo fatto e in tal caso termina la ricorsione ritornando la posizione.

Ultima modifica effettuata da lumo il 08/01/2018 alle 21:11
PM Quote
Avatar
Mikelius (Member)
Expert


Messaggi: 274
Iscritto: 14/04/2017

Segnala al moderatore
Postato alle 22:24
Lunedì, 08/01/2018
concordo con lumo,

Inoltre 2 piccoli appunti/consigli:

-) Togli la variabile goblale
Codice sorgente - presumibilmente C/C++

  1. int posizione;


è inutile.

-) Hai creato
Codice sorgente - presumibilmente C/C++

  1. #define N 8


Utilizzala pure in
Codice sorgente - presumibilmente C/C++

  1. int vett[N]={1,2,3,4,5,6,7,8};



e successivamente per controllare che la posizione non vada fuori dagli indici che saranno
Codice sorgente - presumibilmente Plain Text

  1. 0<= posizione <=N-1




"Io ne ho viste cose che voi umani non potreste immaginarvi...."
PM Quote
Avatar
cos.peluso (Normal User)
Newbie


Messaggi: 18
Iscritto: 03/01/2018

Segnala al moderatore
Postato alle 16:37
Martedì, 09/01/2018
Ok raga, grazie agli spunti presi da un po tutte le vostre risposte sono riuscito a scrivere un codice funzionante , appena vado a casa dove ho il Wi-Fi copio il codice e ve lo mostro, così vedo se ci sono cose inutili o errori che non riesco a vedere .

Ultima modifica effettuata da cos.peluso il 09/01/2018 alle 16:37
PM Quote
Avatar
cos.peluso (Normal User)
Newbie


Messaggi: 18
Iscritto: 03/01/2018

Segnala al moderatore
Postato alle 18:09
Martedì, 09/01/2018
Codice sorgente - presumibilmente C++

  1. //Rierca valore in array tramite ricorsiva
  2. #include <iostream>
  3. using namespace std;
  4. #define N 8
  5. int posizione;
  6.  
  7. int ricerca(int v[],int start,int end,int search);
  8.  
  9. int main(){
  10.         int input,posizione;
  11.         int vett[8]={1,2,3,4,5,6,7,8};
  12.        
  13.         cout<<"Inserire l'elemento da cercare : ";
  14.         cin>>input;
  15.         if(input<=0 || input>8){
  16.        
  17.         cout<<"Nessun valore corrispondente."<<endl;}
  18.         else{
  19.        
  20.         posizione = ricerca(vett,0,N,input);
  21.        
  22.         cout<<"La posizione e' : "<<posizione+1<<endl;}
  23.        
  24.         system("PAUSE");
  25.         return 0;
  26.         }
  27.        
  28.         int ricerca(int v[],int start,int end,int search){
  29.                 int med;
  30.                 med= (start + end)/2;
  31.                
  32.                 if(v[med]==search)
  33.                 {
  34.                         return med;
  35.                 }
  36.                 else
  37.                 if (v[med]<search){
  38.                         return ricerca(v,med,end,search);
  39.                 }
  40.                 else
  41.                 if(v[med]>search){
  42.                         return ricerca(v,start,med,search);
  43.                 }
  44.        
  45.         }



Questo è il codice scritto e funziona bene.L'unico dubbio che ho ancora è, come potevo includere il caso del non esistente all'interno della funzione ricorsiva? Includendo un passo base ancora?

PM Quote
Pagine: [ 1 2 3 4 ] Precedente | Prossimo