View Full Version : [C]minimo in un vettore
domenico88
22-12-2009, 19:24
Ciao a tutti...
Allora ho un problemino con un esempio sulla ricorsione....
In pratica dovrei trovare il minimo nel vettore ricorsivamente, considerando l'elemento che occupa la prima posizione e i restanti elementi quindi first +1 - last.
Il funzionamento non lo riesco proprio a capire
Perdonatemi ma sono alle prime armi con la programmazione, soprattutto con la tecnica del divide et impera.....
Vi posto il codice della funzione
int min_search_rec( int v[], int first, int last)
{
int ris;
/*Caso base */
if ( first == last)
return (first);
/*Divide et impera*/
ris = min_search_rec( v, first +1, last);
/*Combina */
if ( v[ris] < v[first] )
return ris;
else
return first;
}
Grazie anticipatamente a tutti!:)
clockover
23-12-2009, 08:31
Guarda fai così...
--caso base --> se indice == ultimo indice ritorni il minimo
--passo 1--> se elemento corrente minore di minimo allora minimo elemento corrente
--passo 2 --> passo ricorsivo richiami la funzione incrmentando l'indice e passando come parametro il nuovo minimo
dopo un po che ci hai ragionato su ti posto la soluzione ma non ora ovviamente :D :D
Non ho capito cosa intendi per first e last. Mi immagino che sia l'intervallo di posizioni su cui andare a calcolare il minimo.
Condizione di arresto: va bene quella che hai scritto, però è errato il valore che ritorni. Non ha senso, anche nel resto della funzione, ritornare indietro indice e valori, o ritorni l'uno o ritorni l'altro. In questo caso deve sempre ritornare un valore del vettore.
Passo generico: se il valore corrente è minore di quello ritornato dal passo ricorsivo allora ritorni il valore corrente, altrimenti ritorni il valore del ritornato dal passo ricorsivo
Inoltre di pende anche da come ti hanno insegnato il divide et impera. In teoria va bene anche solo incrementare first, ma molti per divide et impera intendono la suddivisione in due sottoinsiemi di dimensione simile dell'intervallo di azione della funzione ricorsiva.
Quindi dovresti suddividere a metà l'intervallo di ricerca e richiamare due volte la funzione ricorsiva. In questo caso il passo generico sarebbe:
divido l'intervallo first - last a metà, ne passo metà ad una funzione ricorsiva e una metà ad un'altra. Confronto il valore ritornato delle funzioni e ritorno il valore minore.
domenico88
23-12-2009, 12:06
Grazie a tutti per le risp.....:D
Cmq raga quella funzione non l'ho scritta io, cioè l'ha scritta il mio prof sul mio libro di Asd.....
Ho capito poco e niente....scusate ma quando
ris = min_search(v, first +1, last); Cosa succede???:mbe:
Non ho capito proprio come lavora la funzione:rolleyes:
X clockover.....ci sto ragionando sarebbe una soluzione alternativa a quella del mio prof ma con una chiamata ricorsiva in coda giusto???
clockover
23-12-2009, 12:23
Allora quel codice che hai postato non funziona!
La chiamata ricorsiva che chiedi tu non fa altro che far avanzare l'indice first fino al caso base..
Comunque lascialo stare quello!
Fallo tu dal principio! Fattelo in due funzioni
1)
int minimo(int a[], int dimensione_vettore){
int index = 0;
int min = a[index];
return minimo2(a, min, index, dimensione_vettore);
}
2)int minimo2(.......){ fallo tu }
segui la traccia in linguaggio naturale che ti ho scritto nel primo post e cerca di capire che robaccia che fa
P.S.
ricorda che devi conoscere la dimensione del vettore
domenico88
23-12-2009, 12:38
Allora quel codice che hai postato non funziona!
La chiamata ricorsiva che chiedi tu non fa altro che far avanzare l'indice first fino al caso base..
Comunque lascialo stare quello!
Fallo tu dal principio! Fattelo in due funzioni
1)
int minimo(int a[], int dimensione_vettore){
int index = 0;
int min = a[index];
return minimo2(a, min, index, dimensione_vettore);
}
2)int minimo2(.......){ fallo tu }
segui la traccia in linguaggio naturale che ti ho scritto nel primo post e cerca di capire che robaccia che fa
P.S.
ricorda che devi conoscere la dimensione del vettore
Graze clock.......ci provo.....:D
Avevo letto male la funzione, quella funzione va perfettamente. Mi sembrava che ritornasse l'elemento del vettore, invece ritornava l'indice del valore minimo.
La chiamata di quella funzione dovrà essere:
min_index = min_search_rec(v, 0, size-1);
Ti permette di trovare il minimo inserendo qualsiasi intervallo, ad esempio:
min_index = min_search_rec(v, size-1, size-1);
Entrerai nella condizione di arresto e ti ritornerà l'indice dell'ultimo elemento del vettore. Questo è normale perché l'indice dell'elemento di minimo valore è sicuramente quello visto che è l'unico elemento valutato nell'intervallo.
Quindi pensa di chiamarlo così:
min_index = min_search_rec(v, size-2, size-1);
Verrà valutato il minimo fra gli ultimi due elementi del vettore:
- la condizione di arresto è falsa, quindi viene valutata la ricorsione che, come sopra, ritorna l'ultimo elemento del vettore
- a questo punto viene fatto il confronto fra l'ultimo elemento del vettore ed il penultimo, viene ritornato l'indice dell'elemento minore
Ora con:
min_index = min_search_rec(v, size-3, size-1);
Anche questa segue lo stesso ragionamento e ritorna l'indice dell'elemento minore fra gli ultime tre, andando a valutare l'elemento da ritornare fra gli indici dell'elemento size-3 e l'indice dell'elemento ritornato dalla chiamata ricorsiva.
int minimo(int a[], int dimensione_vettore){
int index = 0;
int min = a[index];
return minimo2(a, min, index, dimensione_vettore);
}
Non è necessario passare il minimo e nemmeno l'indice volendo, vedi questa:
int indice_valore_minimo(int v[], int dim)
{
int res;
if(dim == 1)
return 0;
res = indice_valore_minimo(v, dim - 1);
if(v[res] < v[dim - 1])
return res;
return dim -1;
}
domenico88
23-12-2009, 15:08
Sto confondendo un pò le idee :wtf:.....
Sto confondendo un pò le idee :wtf:.....
La funzione va, basta che tu la provi o che tu segua il mio ragionamento con dei valori.
La cosa che almeno a me ha confuso è che non ritorna il minimo, ma l'indice del vettore che contiene il valore minimo.
clockover
23-12-2009, 15:30
La cosa che almeno a me ha confuso è che non ritorna il minimo, ma l'indice del vettore che contiene il valore minimo.
Infatti.. comunque io l'ho fatto in questo modo
int min(int a[], int size){
int index = 0;
int minimo = a[index];
return min2(a, minimo, index+1, size);
}
int min2(int a[], int minimo, int i, int size){
if(i == size)return minimo;
if(a[i] < minimo)minimo = a[i];
return min2(a, minimo, i+1, size);
}
poi ovviamente... se hai bisogno della posizione nel vettore è meglio usare quell'altro che hai postato, altrimenti se hai bisogno semplicemente del valore va bene anche il mio! :D :D
aivoglia in quanti modi si può fare
domenico88
23-12-2009, 15:33
grazie ragazzi siete stati davvero gentilissimi....:D
grazie ragazzi siete stati davvero gentilissimi....:D
Ma hai almeno capito come funziona quello del professore ?
domenico88
23-12-2009, 17:21
Ma hai almeno capito come funziona quello del professore ?
Hai colpito in pieno..... non ho capito ancora come funziona!:rolleyes:
non riesco a capire i passi che compie la funzione sull'array!:muro:
Hai colpito in pieno..... non ho capito ancora come funziona!:rolleyes:
non riesco a capire i passi che compie la funzione sull'array!:muro:
Hai letto il mio ragionamento ? Cosa non ti torna, commentalo passo per passo.
domenico88
24-12-2009, 12:46
Hai letto il mio ragionamento ? Cosa non ti torna, commentalo passo per passo.
allora
Il caso base:
if( first == ultimo)
return first;
ok qui il caso base controlla che il vettore abbia esaurito gli elementi da controllare....in caso positivo ritorna il primo indice
Correggimi se sbaglio....
ris = min_search_ris(v, first +1, last);
Qua è il problema.....allora viene invocata la funzione con first che avanza di un elemento...ma cosa assegna la funzione a "ris"????
E' spiegato nel mio messaggio sopra cosa ritrna ed in quale caso. Devi fare un ragionamento per induzione, altrimenti non ne esci.
Quota il mio messaggio, commenta ogni mio ragionamento e dimmi cosa non ti torna.
domenico88
24-12-2009, 14:22
:cry: :cry: non so veramente come fare per capire sta ricorsione
ma devo fare un ragionamento all'inverso?
ris = min_search(v, first +1, last);
dopo questa chiamata sul vettore cosa succede...sul libro c'è scritto che viene diviso considerando separatamente l'elemento che occupa la prima posizione (v[first] ) e il vettore v[first + 1....last] costituito dai rimanenti elementi....:confused:
l'ho riletto e strariletto il tuo ragionamento ma non riesco a capire!:muro:
clockover
24-12-2009, 14:27
Prova fare una cosa: prendi un foglio di carta e creati, sempre sulla carta un array con 3 o 4 elementi massimo! Ti separi anche il foglio in 3 o 4 parti! Segui il codice su carta! Il tuo algoritmo parte e cominci a scrivere in uno spazio! Quando arrivi alla chiamata ricorsiva semplicemente cambi spazio e ricominci! Così via fino alla fine!
dopo questa chiamata sul vettore cosa succede...sul libro c'è scritto che viene diviso considerando separatamente l'elemento che occupa la prima posizione (v[first] ) e il vettore v[first + 1....last] costituito dai rimanenti elementi....:confused:
Il libro vuole dire che ad ogni passo della ricorsione, tu stai confrontando l'elemento di indice corrente con l'indice che contiene il valore minimo di tutti gli elementi successivi al corrente nel vettore.
Quindi, ad esempio, con 3, 4, 2, 5, 3:
- min_index = min_search(v, 0, 4);
-- condizione di arresto falsa, res = min_search(v, 1, 4);
--- condizione di arresto falsa, res = min_search(v, 2, 4);
---- condizione di arresto falsa, res = min_search(v, 3, 4);
----- condizione di arresto falsa, res = min_search(v, 4, 4);
------ condizione di arresto vera ritorno 4
----- res = 4, v[4] < v[3], ritorno 4
---- res = 3, v[3] > v[2], ritorno 2
--- res = 2, v[2] < v[1], ritorno 2
-- red = 2, v[2] < v[0], ritorno 2
- min_index = 2
domenico88
24-12-2009, 15:27
Il libro vuole dire che ad ogni passo della ricorsione, tu stai confrontando l'elemento di indice corrente con l'indice che contiene il valore minimo di tutti gli elementi successivi al corrente nel vettore.
Quindi, ad esempio, con 3, 4, 2, 5, 3:
- min_index = min_search(v, 0, 4);
-- condizione di arresto falsa, res = min_search(v, 1, 4);
--- condizione di arresto falsa, res = min_search(v, 2, 4);
---- condizione di arresto falsa, res = min_search(v, 3, 4);
----- condizione di arresto falsa, res = min_search(v, 4, 4);
------ condizione di arresto vera ritorno 4
----- res = 4, v[4] < v[3], ritorno 4
---- res = 3, v[3] > v[2], ritorno 2
--- res = 2, v[2] < v[1], ritorno 2
-- red = 2, v[2] < v[0], ritorno 2
- min_index = 2
ok così ho chiarito un pò le idee....forse ci sono....
Solo una cosa...come fà first a decrementarsi?? alla prima selezione first non era 4?
Non si decrementa, resta il vlaore che era prima.
Se io ad un dato apsso delal ricorsione chiamo
min_search_rec(v, 2, 4)
int min_search_rec( int v[], int first, int last)
{
int ris;
/*Caso base */
//qui first vale 2
if ( first == last)
return (first);
/*Divide et impera*/
//qui first continua a valere 2, però passo 2 + 1 alla chiamata ricorsiva
ris = min_search_rec( v, first +1, last);
/*Combina */
//qui first continua a valere 2, mentre in ris c'è l'indice dell'elemento con valore minimo fra gli elementi 3 e 4
if ( v[ris] < v[first] )
return ris;
else
return first;
}
domenico88
24-12-2009, 17:13
Non si decrementa, resta il vlaore che era prima.
Se io ad un dato apsso delal ricorsione chiamo
min_search_rec(v, 2, 4)
int min_search_rec( int v[], int first, int last)
{
int ris;
/*Caso base */
//qui first vale 2
if ( first == last)
return (first);
/*Divide et impera*/
//qui first continua a valere 2, però passo 2 + 1 alla chiamata ricorsiva
ris = min_search_rec( v, first +1, last);
/*Combina */
//qui first continua a valere 2, mentre in ris c'è l'indice dell'elemento con valore minimo fra gli elementi 3 e 4
if ( v[ris] < v[first] )
return ris;
else
return first;
}
Grazie per la pazienza moderatore ma qui non ne riesco a venire a capo....
Per gli algoritmi iterativi studiati, seguivo passo per passo le istruzioni e riuscivo a capire come si comportavano...qui non riesco a seguire un filo logico....cosa strana perchè la ricorsione dovrebbe essere più semplice e intuitiva....:rolleyes:
clockover
24-12-2009, 17:19
Hai provato come ti ho detto io... cioè con carta e penna...
L'esempio che ti ha fatto cionci, cioè
- min_index = min_search(v, 0, 4);
-- condizione di arresto falsa, res = min_search(v, 1, 4);
--- condizione di arresto falsa, res = min_search(v, 2, 4);
---- condizione di arresto falsa, res = min_search(v, 3, 4);
----- condizione di arresto falsa, res = min_search(v, 4, 4);
------ condizione di arresto vera ritorno 4
----- res = 4, v[4] < v[3], ritorno 4
---- res = 3, v[3] > v[2], ritorno 2
--- res = 2, v[2] < v[1], ritorno 2
-- red = 2, v[2] < v[0], ritorno 2
- min_index = 2
è una sintesi di quello che faresti tu con carta e penna... schiodati un po da davanti il pc e dal libro e fai come ti ho detto... una volta che lo hai capito farai :muro: :muro: :muro: porca miseria ma era un ca...ata
il motivo per cui capisci gli iterativi e non i ricorsivi sicuramente è perchè non ti accorgi che quando fai una chiamata ricorsiva, l'algoritmo chiamante rimane "appeso" e attende la terminazione dell'algoritmo chiamato, e così fino alla fine
Per gli algoritmi iterativi studiati, seguivo passo per passo le istruzioni e riuscivo a capire come si comportavano...qui non riesco a seguire un filo logico....cosa strana perchè la ricorsione dovrebbe essere più semplice e intuitiva....:rolleyes:
La ricorsione è tutt'altro che più semplice e intuitiva, è uno degli scogli più grossi che si hanno quando si comincia a programmare, perché il ragionamento non è lineare, ma solo per passi. In una funzione iterativa hai tutto lì davanti. In una funzione ricorsiva spesso davanti hai solo la condizione d'arresto e il passo i-esimo.
Hai mai fatto una dimostrazione per induzione a scuola ? Scrivere e leggere algoritmi algoritmi ricorsive è assolutamente la stessa cosa.
Quello che ti ho scritto qualche post fa è proprio una "dimostrazione" per induzione del fatto che quella funzione...funziona :D
Ti ho fatto vedere il passo 0 (condizione d'arresto), il passo 1 (prima ricorsione) ed il passo N (anche se te l'ho mascherato come passo 2).
Spesso ci ferma ad osservare cosa dovrebbe fare la funzione ricorsiva nella sua interezza, niente di più sbagliato, perché si perde invece quello che dovrebbe fare ad ogni passo. Invece devi osservare SOLO quello che fa al passo zero (condizione d'arresto), al passo 1 ed al passo generico N (considerando corretto ciò che viene ritornato dalla ricorsione). Se ognuna delle precedenti situazioni non ha problemi allora la funzione ricorsiva è automaticamente corretta.
Nel mio ultimo post ho seguito proprio passo passo cosa farebbe quella funzione, a mo' di funzione iterativa.
Ora non ti manca altro, DEVI capirla :D
L'ultimo commento di clockover forse ti può aiutare ;) Mi sa che ci ha preso...
la ricorsione è parte fondamentale di un modello di linguaggio dichiarativo dove dici COSA deve fare e non COME deve farla.
E' un bordello assurdo.
Io ho imparato con carta e penna e disegnini delle strutture dati.
Secondo me non c'è altro modo.
domenico88
25-12-2009, 12:03
ciao raga buon natale a tutti.....:D
Ieri ho fatto un esercizio in cui dovevo invertire gli elementi di un vettore con una funzione, l'ho fatta prima iterativa e poi ricorsiva....e funzionava!
Certo non era difficilissima...però qualche passo in avanti l'ho fatto!
Da poco mi sono svegliato, ieri sera ho fatto un pò di cagnara :ubriachi:, quindi è meglio non postare il codice altrimenti uscirebbero diversi orrori!:D
Dopo continuo con gli esercizi e soprattutto co sto minimo e vi faccio sapere!
Io ho imparato con carta e penna e disegnini delle strutture dati.
Secondo me non c'è altro modo.
Secondo me è il modo più complesso. Il ragionamento per induzione è molto, ma molto più semplice.
Vuoi fare una funzione ricorsiva ? Basta chiedersi poche cose:
- come deve essere la condizione d'arresto e scriverla per prima
- come deve essere il passo generico. In particolare come deve essere la visita (anticipata, posticipata o simmetrica). A questo punto bisogna scrivere il codice del passo generico supponendo già corretto e completo il funzionamento della ricorsione.
- considerare eventuali condizioni di arresto o di errore secondarie, solamente alla fine
Automaticamente dopo tutto funziona.
Secondo me è il modo più complesso. Il ragionamento per induzione è molto, ma molto più semplice.
Vuoi fare una funzione ricorsiva ? Basta chiedersi poche cose:
- come deve essere la condizione d'arresto e scriverla per prima
- come deve essere il passo generico. In particolare come deve essere la visita (anticipata, posticipata o simmetrica). A questo punto bisogna scrivere il codice del passo generico supponendo già corretto e completo il funzionamento della ricorsione.
- considerare eventuali condizioni di arresto o di errore secondarie, solamente alla fine
Automaticamente dopo tutto funziona.
Sì ma questo se sei tu a progettare la funzione. Se devi leggere una funzione ricorsiva fatta da un altro (che non sia un putt***ta ovviamente) a me aiuta molto vedere visivamente cosa succede alla struttura dati.
Sì ma questo se sei tu a progettare la funzione. Se devi leggere una funzione ricorsiva fatta da un altro (che non sia un putt***ta ovviamente) a me aiuta molto vedere visivamente cosa succede alla struttura dati.
Quando leggi puoi ragionare nello stesso modo in cui scrivi il programma risparmiandoti molte "seghe mentali". Le definisco così perché ragionare linearmente su una questione ricorsiva mi ricordo che era veramente fastidioso.
Agli inizi quando le leggevo anche io mi facevo tabelle su tabelle, poi alla fine mi sono imposto di resettare tutto quello che pensavo e ricominciare da capo se il ragionamento mi portava a considerare quello che avveniva oltre il passo successivo della ricorsione. Ne ho ottenuto notevoli vantaggi. I tempi necessari alla comprensione o alla scrittura di una funzione ricorsiva si sono ridotti notevolmente.
Vincenzo1968
26-12-2009, 12:45
Per capire la ricorsione c'è il bel libro di Eric S. Roberts - THINKING RECURSIVELY(Wiley):
http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471816523.html
http://media.wiley.com/product_data/coverImage/23/04718165/0471816523.jpg
http://www.amazon.com/Thinking-Recursively-Java-Eric-Roberts/dp/0471701467
http://ecx.images-amazon.com/images/I/41NAQD398XL._BO2,204,203,200_PIsitb-sticker-arrow-click,TopRight,35,-76_AA240_SH20_OU01_.jpg
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.