PDA

Visualizza la versione completa : [C] ricerca minimo array con ricorsione


SSSS90
07-03-2014, 10:56
Salve gradirei un confronto su questo banale esercizio per il calcolo del minimo in un array con metodo ricorsivo,il mio problema è che mi perdo nel ragionamento,quando viene eseguita l'istruzione
ris = min_search_rec(vett,first+1,last);c

PS
Credo che un ragionamento "numerico "step-by-step mi aiuterebbe...spero qualcuno possa venirmi incontro con questo approccio..ciao grazie;)





//Ricerca minimo in array con ricorsione
/*UN PO DI TEORIA:CHE NON FA MAI MALE.Il vettore è costituito ad es. da 10 elementi ,vedremo di seguito applicato l'algoritmo ricorsivo
del divide et impera,a)divide perche' il vettore di ingresso viene diviso considerando l'elemento che occupa la prima posizione
v[first] e il vettore restante v[first+1...last]cb)caso base,nel caso si giungesse per divisioni induttive ad un vettore che contiene un solo
elemento il problema ammetterrebbe una soluzione banale,essendo il minimo l'unico elemento presente--c)impera:induttivamente si supponga di
saper risolvere il problema di ricerca del minimo nel vettore v[first+1...last] e si indichi con Min first+1,last la relativa soluzione.d)combina:
vengono combinati i vari risultati,cioè viene preso il primo elemento del vettore e viene confrontato con il minimo della parte restante del vettore,poi
il secondo elemento del vettore (first=1) e confrontato con il minimo del sottovettore((first+1)--->last )

*/
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
int min_search_rec(int vett[],int first,int last);/*first primo elemento---last ultimo elemento*/


int min_search_rec(int,int);
int main()
{
int vett[10]={1,5,7,158,56,24,15,11,6,89};



printf("Il minimo e' %d\n",min_search_rec(vett,0,9));
system("pause");

}

int min_search_rec(int vett[],int first,int last)
{
int ris;
int i;

/*caso base*/
if (first==last) /*ho raggiunto la fine del vettore*/
return first;

{ /*divide et impera*/
ris = min_search_rec(vett,first+1,last);

/*combina*/

if(vett[ris] < vett[first])

return ris;

else

return first;
}
}

SSSS90
07-03-2014, 15:04
Grazie lo stesso ragazzi,mi sa che per capire bene la ricorsione bisogna vedere bene gli stack,record di attivazione e quant'altro...buona giornata a tutti

Alex'87
07-03-2014, 15:48
Se posti del codice leggibile magari qualcuno una mano te la da anche...

SSSS90
07-03-2014, 16:16
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

int min_search_rec(int vett[],int first,int last);



int main()
{
int vett[10]={1,5,7,158,56,24,15,11,6,89};



printf("Il minimo e' %d\n",min_search_rec(vett,0,9));
system("pause");

}

int min_search_rec(int vett[],int first,int last)
{
int ris;
int i;


if (first==last)
return first;

{
ris = min_search_rec(vett,first+1,last);



if(vett[ris] < vett[first])

return ris;

else

return first;
}
}

SSSS90
07-03-2014, 21:09
Non riesco a capire con che ordine e in che modo le istruzioni vengono salvate nello stack nell'algoritmo ricorsivo,qualcuno può consigliarmi magari qualche testo che affronta il problema in maniera chiara e magari grafica con tanto disegno dello stack e dell'ordine con cui i numeri vengono salvati,va bene per qualsiasi esempio di algoritmo ricorsivo..grazie...buono studio e lavoro a tutti..:)

Loading