ragazzi il problema che vi propongo e' abbastanza semplice, ma non riesco a trovare un'algoritmo abbastanza efficente.
dati N numeri interi positivi (per ora restringo il problema a questo) calcolare il mediano (cioe' quello che, ordinando i numeri, sarebbe alla meta' dell'ordinamento)
io ho pensato cosi' (senza usare array o bla bla)
1. se N/2 = P , con P intero, allora aggiungi N_{0}= 0, ottieni cosi (N+1 numeri) = N
2. fai N/2 ed arrotonda all'intero superiore e poni questo valore pari a Q
3. Poni M=N_{0} come il mediano
4. Poni K=1
5. Leggi i valori da N_{0} a N_{n}, e per ogni valore di N_{i}>M sostituisci N_{i}==>M
6. ogni volta che sostituisci il valore N_{i}==>M fai K=K+1
7. quando arrivi a K=Q, allora M sara' il mediano.
pero'
1) non mi sembra correttissimo
2) mi sembra moolto lento.
Problema semplice
-
germania2002
- Messaggi: 821
- Iscritto il: 01 gen 1970, 01:00
- Località: Cosenza
- Contatta:
Problema meno semplice di quanto si pensi
Ciao ^_^, il problema a cui ti riferisci è il problema della selezione (dato un insieme di elementi non ordinati, determinare la posizione (o l'elemento), dell'elemento che occuperebbe la posizione k, se gli elementi fossero ordinati)...allora
per gli interi effettivamente come complessità si può arrivare ad un O(n), prendi un algoritmo come il radix-sort (ordinamento digitale), ordini metà dell'array, e poi estrai l'elemento cercato, o ne restituisci la posizione nell'array non ordinato..., oppure ci sarebbero anche altri algoritmi per la selezione con chiamate ricorsive stile Quicksort con alcune accortezze sulla scelta dell'elemento rispetto a cui partizionare.
rispondendo alla domanda "però"
1) l'algoritmo non mi sebra corretto. Guarda il caso seguente, come scelta iniziale preliminare del mediano abbiano 0, sappiamo che tutti gli interi positivi sono maggiori di 0, ora però, cosa fa l'algoritmo: aggiorna la scelta del mediano non appena trova un elemento più grande, ma se per esempio N_{1}= max{N} (se l'elemento in posizione 1, è il più grande tra gli elementi che consideri, supponiamo infatti che secondo l'algoritmo N_{0}=0),
quindi N_{1}>M=0,
=> quindi secondo la condizione aggiorniamo M:= N_{1}, K:=K+1
ma ora al prossimo confronto con N_{2} abbiamo il problema del massimo elemento incastrato nella nostra scelta del mediano, e quindi K rimane non aggiornato.
Ahimè per il problema del mediano servirebbe a poco persino contare gli elementi più grandi del minimo dell'insieme considerato (0 per gli interi positivi, simile al tuo algoritmo).
Mi sono occupato di questo problema proprio quest'estate, se vuoi ti posso postare il codice C++ per un algoritmo in genere considerato buono, così poi vedi come funziona ...
per il punto (2)
non puoi sperare di fare meno di O(n) (ossia complessità a*n, con a >1 strettamente ) per poter dire qualcosa sul mediano, devi almeno sapere ciò che hai nell'insieme da cui vuoi estrarlo.
Però vorrei proporti un PROBLEMA, abbastanza interessante sullo stesso tema il MEDIANO .
"Dato un array (per semplicità) di 5 elementi, come si fa a stabilirne il mediano eseguendo 6 confronti tra gli elementi di tale array ??? "
per gli interi effettivamente come complessità si può arrivare ad un O(n), prendi un algoritmo come il radix-sort (ordinamento digitale), ordini metà dell'array, e poi estrai l'elemento cercato, o ne restituisci la posizione nell'array non ordinato..., oppure ci sarebbero anche altri algoritmi per la selezione con chiamate ricorsive stile Quicksort con alcune accortezze sulla scelta dell'elemento rispetto a cui partizionare.
rispondendo alla domanda "però"
1) l'algoritmo non mi sebra corretto. Guarda il caso seguente, come scelta iniziale preliminare del mediano abbiano 0, sappiamo che tutti gli interi positivi sono maggiori di 0, ora però, cosa fa l'algoritmo: aggiorna la scelta del mediano non appena trova un elemento più grande, ma se per esempio N_{1}= max{N} (se l'elemento in posizione 1, è il più grande tra gli elementi che consideri, supponiamo infatti che secondo l'algoritmo N_{0}=0),
quindi N_{1}>M=0,
=> quindi secondo la condizione aggiorniamo M:= N_{1}, K:=K+1
ma ora al prossimo confronto con N_{2} abbiamo il problema del massimo elemento incastrato nella nostra scelta del mediano, e quindi K rimane non aggiornato.
Ahimè per il problema del mediano servirebbe a poco persino contare gli elementi più grandi del minimo dell'insieme considerato (0 per gli interi positivi, simile al tuo algoritmo).
Mi sono occupato di questo problema proprio quest'estate, se vuoi ti posso postare il codice C++ per un algoritmo in genere considerato buono, così poi vedi come funziona ...
per il punto (2)
non puoi sperare di fare meno di O(n) (ossia complessità a*n, con a >1 strettamente ) per poter dire qualcosa sul mediano, devi almeno sapere ciò che hai nell'insieme da cui vuoi estrarlo.
Però vorrei proporti un PROBLEMA, abbastanza interessante sullo stesso tema il MEDIANO .
"Dato un array (per semplicità) di 5 elementi, come si fa a stabilirne il mediano eseguendo 6 confronti tra gli elementi di tale array ??? "
-
germania2002
- Messaggi: 821
- Iscritto il: 01 gen 1970, 01:00
- Località: Cosenza
- Contatta:
