Sequenza numeri casuali senza ripetizioni
Salve a tutti,
sto scrivendo un programma in C in cui è richiesta una funzione che generi una sequenza di 6 numeri casuali da 1 a 90 senza ripetizioni.
Ho pensato di utilizzare un array di lunghezza 6 e memorizzare lì i numeri casuali generati, ma poi per controllare che ogni valore sia diverso devo, per ognuno, scorrere tutto l'array? C'è un modo più efficiente per generare sequenze di numeri senza ripetizioni?
Ringrazio in anticipo,
Valentina
sto scrivendo un programma in C in cui è richiesta una funzione che generi una sequenza di 6 numeri casuali da 1 a 90 senza ripetizioni.
Ho pensato di utilizzare un array di lunghezza 6 e memorizzare lì i numeri casuali generati, ma poi per controllare che ogni valore sia diverso devo, per ognuno, scorrere tutto l'array? C'è un modo più efficiente per generare sequenze di numeri senza ripetizioni?
Ringrazio in anticipo,
Valentina
Risposte
Quante ne devi generare di queste successioni? Abbiamo comunque parlato molte volte di questo genere di problemi.
potresti tenere l'array ordinato per numeri crescenti,
così ad esempio se viene generato 37 e hai un array del genere [5,21,33,40,50,..] puoi evitare di scorrere tutto l'array controllando solo gli elementi(partendo dal primo) $<=37$
così ad esempio se viene generato 37 e hai un array del genere [5,21,33,40,50,..] puoi evitare di scorrere tutto l'array controllando solo gli elementi(partendo dal primo) $<=37$
Deve essere una funzione che ne genera una con tutti numeri diversi, che chiamata più volte genera ogni volta sequenze diverse che possono anche avere numeri uguali rispetto alle sequenze precedenti, ma non all'interno della sequenza stessa (tipo una simulazione del superenalotto, per intenderci). Ho cercato qui sul forum su "cerca qui" inserendo "sequenze numeri casuali senza ripetizioni" prima di postare, ma non ho trovato niente di che, e nemmeno in altri siti dove non c'era una risposta precisa alla mia domanda (ma forse perchè non c'è un metodo ben preciso, bisogna pensarci ogni volta?)...
Vista la dimensione dello spazio da cui estrai i numeri, direi che la soluzione migliore nel tuo caso sia quella di generare i numeri a caso e poi scartarli nel caso di ripetizioni. A meno che tu non debba generarne un numero particolarmente elevato mi sembra una scelta accettabile.
E per scartarli in caso di ripetizioni, può andare una cosa del tipo: (*pd è il puntatore all'array in cui ho memorizzato la sequenza calcolata senza ancora controllare se ci sono ripetizioni)
for (i=0; i<6; i++) {
for (k=0; k<6; k++) {
while (*(pd+i)==*(pd+k) && i!=k) {
*(pd+i)= lrand48()%91;
}
}
}
?
Può funzionare? Mi sembra molto macchinoso!
for (i=0; i<6; i++) {
for (k=0; k<6; k++) {
while (*(pd+i)==*(pd+k) && i!=k) {
*(pd+i)= lrand48()%91;
}
}
}
?
Può funzionare? Mi sembra molto macchinoso!
Io pensavo più che altro a qualcosa come (è in C++ perché ho usato i bool ma puoi usare un int o altro al suo posto):
Non mi sembra particolarmente complicato. Una versione alternativa potrebbe essere quella di avere un array di numeri da 1 e 90 e usare una versione alternativa dell'algoritmo di Fisher-Yates per il rimescolamento. Se vuoi posso mostrarti il codice per farlo usando questo secondo metodo.
for (i = 0; i < 6; ++i) {
bool is_valid = true;
do {
pd[i] = lrand48()%91;
for (j = 0; j < i; ++j) {
if (pd[i] == pd[j]) is_valid = false;
}
} while(!is_valid);
}
Non mi sembra particolarmente complicato. Una versione alternativa potrebbe essere quella di avere un array di numeri da 1 e 90 e usare una versione alternativa dell'algoritmo di Fisher-Yates per il rimescolamento. Se vuoi posso mostrarti il codice per farlo usando questo secondo metodo.
Penso di aver capito tranquillamente con il codice che hai scritto! Va benissimo così. Grazie mille! 
Scusa ancora, ma invece non ho capito, quello che avevo scritto io non funzionava?
Non va bene perché accedi a valori non ancora inizializzati. Accedi infatti a pd[k] prima di averlo inizializzato. Ha senso fare la verifica solo sui valori già scelti.
Aspetta, scrivo il codice completo della funzione:
void estrazione (int SESTINE[]) {
int i, *pd, k;
pd = SESTINE;
for (i=0; i<6; i++) {
*(pd+i) = lrand48() % 90 + 1;
}
for (i=0; i<6; i++) {
for (k=0; k<6; k++) {
while (*(pd+i)==*(pd+k) && i!=k) {
*(pd+k) = lrand48()%91;
}
}
}
}
In che senso valori già scelti? Scusa ma sono un po' confusa :S
void estrazione (int SESTINE[]) {
int i, *pd, k;
pd = SESTINE;
for (i=0; i<6; i++) {
*(pd+i) = lrand48() % 90 + 1;
}
for (i=0; i<6; i++) {
for (k=0; k<6; k++) {
while (*(pd+i)==*(pd+k) && i!=k) {
*(pd+k) = lrand48()%91;
}
}
}
}
In che senso valori già scelti? Scusa ma sono un po' confusa :S
Nel senso che non pensavo li avessi generati in precedenza. Quel codice non poteva starsene da solo, senza cioè il ciclo iniziale non funzionava per diverse ragioni (l'avevo comunque guardato velocemente prima per cui il mio commento non era particolarmente valido). Per il resto il codice sembra corretto. Preferisco però fare il confronto direttamente mentre si generano i valori come ti ho mostrato nel mio codice precedente (che è equivalente a tutta la tua funzione).
Attenta però alla generazione dei numeri, le seguenti righe non generano gli stessi intervalli di valori:
Quella corretta se vuoi generare numeri da 1 a 90 è la prima (mi ero sbagliato anche nel mio codice).
Ma perché usi l'aritmetica dei puntatori in questo caso?
Attenta però alla generazione dei numeri, le seguenti righe non generano gli stessi intervalli di valori:
*(pd+i) = lrand48() % 90 + 1; // ... *(pd+k) = lrand48()%91;
Quella corretta se vuoi generare numeri da 1 a 90 è la prima (mi ero sbagliato anche nel mio codice).
Ma perché usi l'aritmetica dei puntatori in questo caso?
Ah è vero, nell'altro modo generavo numeri da 0 a 90!
In effetti poi la mia funzione non è molto pratica, la tua è molto più compatta.. però volevo sapere se in generale era solo così o c'era proprio dietro un ragionamento sbagliato, non lo è, quindi già non va malaccio
Uso i puntatori perchè voglio memorizzare la sequenza in un array di lunghezza 6, e so che in C non è possibile passare direttamente un array a una funzione... non è così? Dopo nel main quando chiamo la funzione metto, come argomento, il nome dell'array su cui deve lavorare... (e ovviamente anche in dichiarazione della funzione metto come argomento il tipo dell'array seguito da [])
In effetti poi la mia funzione non è molto pratica, la tua è molto più compatta.. però volevo sapere se in generale era solo così o c'era proprio dietro un ragionamento sbagliato, non lo è, quindi già non va malaccio
Uso i puntatori perchè voglio memorizzare la sequenza in un array di lunghezza 6, e so che in C non è possibile passare direttamente un array a una funzione... non è così? Dopo nel main quando chiamo la funzione metto, come argomento, il nome dell'array su cui deve lavorare... (e ovviamente anche in dichiarazione della funzione metto come argomento il tipo dell'array seguito da [])
Puoi usare le due notazioni in modo intercambiabile e sia con array che con puntatori...
In che senso?... Posso usare gli array anche dentro una funzione, indifferentemente?
Nel senso che *(a + b) == a quasiasi sia a e b (uno dei due deve essere un puntatore o un array - che è alla fine solo una specie di puntatore costante e che in alcuni casi trasporta qualche informazione aggiuntiva sulla dimensione). Ti invito a scrivere un programma che definisce un array arr di almeno due elementi e un puntatore p al suo primo elemento e che prova a stampare i seguenti valori: arr[1], p[1], *(arr + 1), *(p + 1), 1[arr], 1
. Ti invito quindi ad osservare come tutte queste espressioni siano equivalenti.
Ah, ho capito adesso. Comunque lo farò per visualizzare la cosa! Grazie per la pazienza, buona giornata
Per completezza, avendo fatto prima riferimento ad un metodo alternativo per generare queste successioni basato su un rimescolamento di un array di 90 elementi, posto tale funzione.
void estrazione(int sestine[])
{
static int stato[90] = { 1, /* ... inserire tutti i valori mancanti ... */, 90 };
for (int i = 0; i < 6; ++i) {
int j = i + lrand48()%(90-i);
sestine[i] = stato[j];
stato[j] = stato[i];
stato[i] = sestine[i];
}
}
Grazie!...solo la prima riga della funzione non mi è chiara: che significa static davanti alla dichiarazione dell'array(che vedo viene subito riempito)? (credo che non ce l'abbiano mai detto...) significa che non può essere modificato?
Significa che non viene distrutto dopo la chiusura della funzione e che rimane lo stesso tra le diverse chiamate della funzione. Alla successiva chiamata della funzione, i suoi primi sei valori saranno allora gli elementi estratti alla precedente estrazione (tranne alla prima chiamata).
Questo metodo è particolarmente comodo quando il rapporto tra il numero di valori da estrarre e il numero di elementi da cui è possibile estrarre è basso. Se infatti tale rapporto è molto alto, il metodo in cui si scartano i valori è comunque molto efficiente e richiede molto meno spazio. Quando però tale rapporto è basso, il metodo in cui si scartano gli elementi potrebbe richiedere tempi molto elevati (e potrebbe convenire estrarre gli elementi da eliminare piuttosto che quelli da estrarre).
Questo metodo è particolarmente comodo quando il rapporto tra il numero di valori da estrarre e il numero di elementi da cui è possibile estrarre è basso. Se infatti tale rapporto è molto alto, il metodo in cui si scartano i valori è comunque molto efficiente e richiede molto meno spazio. Quando però tale rapporto è basso, il metodo in cui si scartano gli elementi potrebbe richiedere tempi molto elevati (e potrebbe convenire estrarre gli elementi da eliminare piuttosto che quelli da estrarre).
Ho capito, in effetti è un ottimo metodo! Grazie mille ancora!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo