| V I S U A L I Z Z A D I S C U S S I O N E |
| Albatro |
Inserito il - 14/05/2006 : 11:22:31
Ragazzi.. devo fare un programmino che inserito il "numero"(inteso come dimensione totale..) dei partecipanti in Input li estragga in modo casuale..
ho un piccolo problema, anzi 2....
prima di tutto se inserisco x es. "5" mi estrae sempre la stessa combinazione... 2 - 3 - 5 - 1 - 5 ...
ok.. ho letto che sta cosa si risolve con "srand".. ma.. ehm... nn riesco a farlo funzionare....
l'altro mio problema è che NATURALMENTE una volta estratto un numero NON deve riestrarlo più! (pseudo-random x l'appunto...)
chi mi sa dire qualcosa di utile??? |
| 9 U L T I M E R I S P O S T E (in alto le più recenti) |
| genius |
Inserito il - 14/05/2006 : 23:58:44
Citazione:
Messaggio inserito da feeb
Citazione:
Messaggio inserito da genius
per evitare le ripetizioni mi vengono in mente 2 modi (per ora):
- memorizzi in un vettore i numeri ke estrai di volta in volta e controlli ke il nuovo numero estratto nn sia presente nel vettore. Questo algoritmo nn ha una grande efficenza perkè se devi estrarre n numeri devi fare un numero di confronti pari a (n-1)! se nn ho fatto male i conti.
- crei un vettore di n elementi ed inizializzi il vettore per esempio a 0. man mano ke estrai i numeri poni per esempio ad 1 il j-esimo elemento del vettore. In questo modo fai un solo confronto ad ogni estrazione (controlli se il valore j-esimo è 0, in tal caso il numero non è stato estratto precedentemente).
poi a seconda di quello ke ti serve puoi o memorizzare in un altro vettore la sequenza dei numeri estratti, oppure stampare a video tale sequenza ;)
mittico 
terzo modo:
http://www.neuralnoise.com/randperm.c (non fare caso ai nomi delle variabili..)
praticamente inizializza un vettore con gli n elementi da permutare (1..n in questo caso) e poi scambia gli elementi da 1 a n con un altro a caso, cosi' non ti serve verificare se un elemento e' gia' uscito o meno
magia! O(n)!
wow! cmq la seconda proposta mia è ank'essa O(n) ;) |
| Albatro |
Inserito il - 14/05/2006 : 23:17:13
grazie feeb e genius... proverò le varie proposte...
PS: feeb...... stè propr' sott' eh? |
| feeb |
Inserito il - 14/05/2006 : 19:57:12
Citazione:
Messaggio inserito da genius
per evitare le ripetizioni mi vengono in mente 2 modi (per ora):
- memorizzi in un vettore i numeri ke estrai di volta in volta e controlli ke il nuovo numero estratto nn sia presente nel vettore. Questo algoritmo nn ha una grande efficenza perkè se devi estrarre n numeri devi fare un numero di confronti pari a (n-1)! se nn ho fatto male i conti.
- crei un vettore di n elementi ed inizializzi il vettore per esempio a 0. man mano ke estrai i numeri poni per esempio ad 1 il j-esimo elemento del vettore. In questo modo fai un solo confronto ad ogni estrazione (controlli se il valore j-esimo è 0, in tal caso il numero non è stato estratto precedentemente).
poi a seconda di quello ke ti serve puoi o memorizzare in un altro vettore la sequenza dei numeri estratti, oppure stampare a video tale sequenza ;)
mittico
terzo modo:
http://www.neuralnoise.com/randperm.c (non fare caso ai nomi delle variabili..)
praticamente inizializza un vettore con gli n elementi da permutare (1..n in questo caso) e poi scambia gli elementi da 1 a n con un altro a caso, cosi' non ti serve verificare se un elemento e' gia' uscito o meno
magia! O(n)! |
| feeb |
Inserito il - 14/05/2006 : 13:27:40
Citazione:
Messaggio inserito da Albatro
si verifica che un numero già estratto viene ri-estratto... suggerimenti??? 
a voler fare una cosa figa, puoi generare una permutazione casuale degli interi 1..n
http://camino.rutgers.edu/ut/utsa/cs3343/lecture25.html
se no ti basta controllare che un numero non sia gia' uscito (magari li salvi in un vettore) |
| genius |
Inserito il - 14/05/2006 : 13:27:07
per evitare le ripetizioni mi vengono in mente 2 modi (per ora):
- memorizzi in un vettore i numeri ke estrai di volta in volta e controlli ke il nuovo numero estratto nn sia presente nel vettore. Questo algoritmo nn ha una grande efficenza perkè se devi estrarre n numeri devi fare un numero di confronti pari a (n-1)! se nn ho fatto male i conti.
- crei un vettore di n elementi ed inizializzi il vettore per esempio a 0. man mano ke estrai i numeri poni per esempio ad 1 il j-esimo elemento del vettore. In questo modo fai un solo confronto ad ogni estrazione (controlli se il valore j-esimo è 0, in tal caso il numero non è stato estratto precedentemente).
poi a seconda di quello ke ti serve puoi o memorizzare in un altro vettore la sequenza dei numeri estratti, oppure stampare a video tale sequenza ;) |
| Albatro |
Inserito il - 14/05/2006 : 13:05:58
ho fatto un passo avanti... adesso.. utilizzando la "srand" il sorteggio è diverso ad ogni apertura del programma... maaaa....
come sempre c'è un ma!
si verifica che un numero già estratto viene ri-estratto... suggerimenti??? |
| Albatro |
Inserito il - 14/05/2006 : 12:45:22
grazie.. proverò... |
| rat86 |
Inserito il - 14/05/2006 : 12:31:59
io mi ricordo ke per far variare la seuqenz prima di utilizzare la funzione random o rand o quello che era, utilizzavo ll inizio la funzione randomize() senza alcun parmametro cosi come è scrittq |
| feeb |
Inserito il - 14/05/2006 : 12:05:07
Citazione:
Messaggio inserito da Albatro
Ragazzi.. devo fare un programmino che inserito il "numero"(inteso come dimensione totale..) dei partecipanti in Input li estragga in modo casuale..
ho un piccolo problema, anzi 2....
prima di tutto se inserisco x es. "5" mi estrae sempre la stessa combinazione... 2 - 3 - 5 - 1 - 5 ...
ok.. ho letto che sta cosa si risolve con "srand".. ma.. ehm... nn riesco a farlo funzionare....
l'altro mio problema è che NATURALMENTE una volta estratto un numero NON deve riestrarlo più! (pseudo-random x l'appunto...)
chi mi sa dire qualcosa di utile???
void srand(unsigned int) usa l'argomento che gli passi per inizializzare la nuova sequenza di interi pseudo-random che sarà restituita da rand() (queste sequenze sono ripetibili passando sempre lo stesso valore a srand())
un modo per inizializzare srand() con un valore sempre diverso potrebbe essere quello di fare srand(time(NULL)) (time(NULL) ti dovrebbe restituire il numero di secondi passati dalla mezzanotte dell'1 gennaio 1970)
ecco un esempio: http://www.neuralnoise.com/rand.c
comunque se ti interessa l'argomento dei PRNG un articolo carino l'ho trovato qui: http://www.phrack.org/show.php?p=59&a=15 |
