[C] Generare numeri rand con probabilità determinata

[informatico91]

Ciao a tutti!! E' da poco che scrivo nel forum. Spero di non sbagliare qualcosa...
Ho un problema con un esercizio in linguaggio C:

Dato un vettore di 50 elementi, in ogni elemento deve essere inserito un numero pseudocasualmente estratto tra 1, 2 e 3 con probabilità rispettivamente di 1/5, 2/5, 2/5.

Ho studiato sul libro "C Corso completo di programmazione " seconda ed. deitel e non ho mai incontrato esercizi del genere.
Se non ci fosse il fattore probabilità sarebbe facilissimo...qualcuno ha idea di come risolverlo??...

[marck77]

Mi viene in mente che potresti fargli estrarre un numero a caso tra 1 e 5, poi scrivi così:

if numero estratto è 4 allora numero estratto diventa 2
if numero estratto è 5 allora numero estratto diventa 3

Così avresti 1 possibilità su 5 che esca 1, 2 possibilità su 5 che esca 2 (cioè quando esce 2 o 4) e 2 possibilità su 5 che esca 3 (cioè quando esce 3 o 5)

[oNaSsIs]

Oppure sfruttando sempre questa idea in modo più efficiente potresti riempire un vettore di 5 elementi in questo modo:

int vet [] = {1,2,2,3,3}

ed estrarre casualmente l'indice del vettore (un numero compreso tra 0 e 4)...

[informatico91]

grazie delle risposte ...gli ho implementati e funzionano correttamente entrambi =)

[goldorak]

Originariamente inviato da informatico91

Ciao a tutti!! E' da poco che scrivo nel forum. Spero di non sbagliare qualcosa...
Ho un problema con un esercizio in linguaggio C:

Dato un vettore di 50 elementi, in ogni elemento deve essere inserito un numero pseudocasualmente estratto tra 1, 2 e 3 con probabilità rispettivamente di 1/5, 2/5, 2/5.

Ho studiato sul libro "C Corso completo di programmazione " seconda ed. deitel e non ho mai incontrato esercizi del genere.
Se non ci fosse il fattore probabilità sarebbe facilissimo...qualcuno ha idea di come risolverlo??...

E molto semplice, devi aiutarti con una variable casuale U con distribuzione uniforme nel intervallo (0,5).

Allora il problema si riduce a trovare una variable casuale X che prende valori 1,2,3 con probabilita' rispettive di 1/5,2/5 e 2/5.


X = 1 se 0<U<1/5
X = 2 se 1/5<U<3/5
X = 3 se 3/5<U<5

Si verifica immediatamente che p(X=1)=1/5, p(X=2)=2/5 e p(X=3)=2/5

[goldorak]

Originariamente inviato da marck77

Mi viene in mente che potresti fargli estrarre un numero a caso tra 1 e 5, poi scrivi così:

if numero estratto è 4 allora numero estratto diventa 2
if numero estratto è 5 allora numero estratto diventa 3

Così avresti 1 possibilità su 5 che esca 1, 2 possibilità su 5 che esca 2 (cioè quando esce 2 o 4) e 2 possibilità su 5 che esca 3 (cioè quando esce 3 o 5)

E se non puo' generare piu' di 3 elementi come fa ?
La tua soluzione e' concettualmente sbagliata.

[informatico91]

Originariamente inviato da goldorak

E molto semplice, devi aiutarti con una variable casuale U con distribuzione uniforme nel intervallo (0,5).

Allora il problema si riduce a trovare una variable casuale X che prende valori 1,2,3 con probabilita' rispettive di 1/5,2/5 e 2/5.


X = 1 se 0<U<1/5
X = 2 se 1/5<U<3/5
X = 3 se 3/5<U<5

Si verifica immediatamente che p(X=1)=1/5, p(X=2)=2/5 e p(X=3)=2/5

mmm.. cioè per ogni elemento del vettore devo generare un numero casuale intero tra 0 e 5 per U. e poi...??

[goldorak]

Originariamente inviato da informatico91

mmm.. cioè per ogni elemento del vettore devo generare un numero casuale intero tra 0 e 5 per U. e poi...??

Devi generare un numero casuale uniforme U tra 0 e 5 (non dev'essere necessariamente intero).

Poi in base al valore di U metti 1 o 2 o 3 nelle posizione corrente nell'array.

Per intenderci, generi U e trovi che il suo valore sta tra 0 e 1/5 allora metti 1 nel array. Genera di nuovo U, se trovi che il suo valore sta tra 1/5 e 3/5 allora metti 2 nell'array e cosi' via. In questo modo riempi l'array con 1 o 2 o 3 con le probabilita' giuste.

Il modo in cui hai costruito X ti garantisce che 1,2,3 verranno estratte con le probabilita' indicate dal problema.

[marck77]

Originariamente inviato da goldorak

E se non puo' generare piu' di 3 elementi come fa ?
La tua soluzione e' concettualmente sbagliata.

Cosa non può generare più di 3 elementi? Anche la tua "U" alla fine può avere 5 valori no? Non capisco la differenza tra la tua soluzione e la mia sinceramente. Dove è sbagliata la mia? Grazie mille.

[marck77]

Originariamente inviato da goldorak

Il C mette a disposizione la funzione rand() che ti genera un numero casuale tra 0 e 1. Siccome tu ne vuoi uno tra 0 e 5 devi moltiplicare la rand() per 5. Quindi U = 5*rand ().

Che io sappia la rand genera un numero pseudocasuale tra 0 e 32767 quindi per ottenere un numero pseudocasuale in un intervallo minore si usa l'operatore modulo (%)

quindi bisogna fare "rand()%5" per avere un valore tra pseudocasuale tra 0 e 4 in output. Ti risulta?

Oltretutto se fosse vero quello che dici moltiplicando la rand() per 5 otterresti solo o 0 o 5, mai un valore intermedio..

Ciao.

[Supdario]

E' così, anche se il metodo "rand()%n" genera un numero random usando le cifre meno significative, il modo giusto sarebbe:

Per generare un numero intero tra 0 e n-1

rand()*n/(RAND_MAX+1)

Per generare un numero reale nel campo 0 ≤ x < n

rand()*n/(RAND_MAX+1.0)

[goldorak]

Originariamente inviato da marck77

Cosa non può generare più di 3 elementi? Anche la tua "U" alla fine può avere 5 valori no? Non capisco la differenza tra la tua soluzione e la mia sinceramente. Dove è sbagliata la mia? Grazie mille.

Leggi le specifiche del problema. Dove sta scritto che lui debba generare i numeri 4 e 5 e poi metterli uguali a 2 e 3 ? Certo come hai fatto tu funziona ci mancherebbe altro, ma e' una soluzione fatta alla meno peggio.

Originariamente inviato da marck77

Che io sappia la rand genera un numero pseudocasuale tra 0 e 32767 quindi per ottenere un numero pseudocasuale in un intervallo minore si usa l'operatore modulo (%)

quindi bisogna fare "rand()%5" per avere un valore tra pseudocasuale tra 0 e 4 in output. Ti risulta?

Oltretutto se fosse vero quello che dici moltiplicando la rand() per 5 otterresti solo o 0 o 5, mai un valore intermedio..

Ciao.

Giusto, mi sono impappinato con la rand() del C.
Comunque il ragionamento che ho fatto e' corretto. Basta generare un valore casuale (non intero) tra 0 e 5 e poi verificare in che intervallo cade.
Sulla base di questo poi fai l'assegnamento nell'array.

[informatico91]

Originariamente inviato da goldorak

Devi generare un numero casuale uniforme U tra 0 e 5 (non dev'essere necessariamente intero).

Poi in base al valore di U metti 1 o 2 o 3 nelle posizione corrente nell'array.

Per intenderci, generi U e trovi che il suo valore sta tra 0 e 1/5 allora metti 1 nel array. Genera di nuovo U, se trovi che il suo valore sta tra 1/5 e 3/5 allora metti 2 nell'array e cosi' via. In questo modo riempi l'array con 1 o 2 o 3 con le probabilita' giuste.

Il modo in cui hai costruito X ti garantisce che 1,2,3 verranno estratte con le probabilita' indicate dal problema.

Il tuo algoritmo è interessante! Solo che non lo stavo capendo perchè io sapevo che la funzione rand() può generare un numero casuale intero

Originariamente inviato da Supdario

Per generare un numero reale nel campo 0 ≤ x < n

rand()*n/(RAND_MAX+1.0)

Usando la seguente formula effettivamente si riesce a generare dei numeri casuali con la virgola semplicemente sostituendo ad RAND_MAX 32767 e ad n il secondo estremo dell'intervallo (5 in questo caso)..
Tuttavia così facendo l'algoritmo non funziona bene. Per tutti gli algoritmi qui proposti ho randomizzando i numeri con srand(time(NULL)) e tutto ok. Ho fatto questo miniprogramma per verificare effettivamente che rand() riuscisse a generare dei numeri con la virgola

main()
{
      double x;
      srand(time(NULL));
      
      x = rand()*5/(32767+1.0);
      printf("%.10f", x);
}

e facendo degli output ripetuti (guarda l'immagine) si nota come i numeri generati siano ad intervalli ravvicinati

[informatico91]

ragazzi ce un altro problema..praticamente la seconda parte del problema chiede di scrivere quel vettore (x[50]) in un file ad accesso casuale

#include<stdio.h>

main()
{
      int x[50];
      int prob[5] = { 1, 2, 2, 3, 3 };
      int occorrenze[3] = {0};
      int restituzioni[50] = {0};
      int i;
      FILE *filePtr;
      
      srand(time(NULL));
      
      for ( i = 0; i <= 49; i++ )
      {
          x[i] = prob[(rand() % 5)]; // --> prob[ 0 <= indice < 5] <--
          ++occorrenze[x[i]-1];
      }
      
      for ( i = 0; i <=2; i++ )
      {
          printf("Occorrenze di %d: %d\n", i+1 , occorrenze[i]);
      }
      
      if ( (filePtr = fopen("vettore.dat", "wb")) == NULL)
      {
         printf("Errore!! Il file non può essere aperto\n");
      }
      else
      {
          for ( i = 0; i < 50; i++ )
          {
              fseek( filePtr, i * sizeof ( x[i] ), SEEK_SET );
              fwrite( &x[i], sizeof ( x[i] ), 1, filePtr);
          }
      }
      
/* Verifichiamo che i dati memorizzati sono stati giustamente inseriti*/      
      

        for ( i = 0; i < 50; i++ )
        {
            fread ( &restituzioni[i], sizeof( restituzioni[i] ), 1, filePtr);
            printf("%d\n", restituzioni[i]);
        }
      fclose(filePtr);
}

Per verificare che l'operazione fosse andata a buon fine ho pensato di leggere i contenuti di quel file (ultimo ciclo for) ma come output mi escono una sequenza di 0. Cioè praticamente sono rimasti intatti gli elementi del vettore originale "richeste[50]"
I dati sono stati memorizzati male nel file oppure sono stati letti scorrettamente...Dov'è che sbaglio???

[Supdario]

Originariamente inviato da informatico91

Il tuo algoritmo è interessante! Solo che non lo stavo capendo perchè io sapevo che la funzione rand() può generare un numero casuale intero



Usando la seguente formula effettivamente si riesce a generare dei numeri casuali con la virgola semplicemente sostituendo ad RAND_MAX 32767 e ad n il secondo estremo dell'intervallo (5 in questo caso)..
Tuttavia così facendo l'algoritmo non funziona bene. Per tutti gli algoritmi qui proposti ho randomizzando i numeri con srand(time(NULL)) e tutto ok. Ho fatto questo miniprogramma per verificare effettivamente che rand() riuscisse a generare dei numeri con la virgola

main()
{
      double x;
      srand(time(NULL));
      
      x = rand()*5/(32767+1.0);
      printf("%.10f", x);
}

e facendo degli output ripetuti (guarda l'immagine) si nota come i numeri generati siano ad intervalli ravvicinati

L'algoritmo in sè funziona, il problema che si verifica nel tuo caso è dovuto a 2 motivi:
1) Il seed viene inizializzato con un'unità di tempo precisa al secondo, quindi se tu esegui il programma 2-3 volte in un secondo, il seed sarà sempre uguale.
2) La variazione del seed è minima e viene generato solo un numero, dopodiché il programma viene terminato, rieseguito, ed il seed viene reinizializzato. Se provi con un programma del genere:

int main()
{
	srand((unsigned)time(NULL));
	for (int i = 0; i < 100; i++)
	{
		double x = rand()*5/(32767+1.0);
		printf("%.10f ", x);
	}
	return 0;
}

noterai che i risultati sono abbastanza sensati.

[TRF83]

Originariamente inviato da goldorak

Leggi le specifiche del problema. Dove sta scritto che lui debba generare i numeri 4 e 5 e poi metterli uguali a 2 e 3 ? Certo come hai fatto tu funziona ci mancherebbe altro, ma e' una soluzione fatta alla meno peggio.

Sinceramente, a me sembra che il ragionamento fatto sia praticamente lo stesso..se porti il tuo "/5" dall'altra parte dell'uguale, ottieni lo stesso calcolo! Anzi, così facendo l'arrangi con un rand()%5 (andando da 0 a 4, invece che da 1 a 5..cambia poco), invece di coinvolgere anche delle moltiplicazioni e divisioni.. Che poi sia più efficiente fare una rand()%4 indicante l'indice dell'array, è fuori discussione!

[tuccio`]

Originariamente inviato da informatico91

ragazzi ce un altro problema..praticamente la seconda parte del problema chiede di scrivere quel vettore (x[50]) in un file ad accesso casuale

#include<stdio.h>

main()
{
      int x[50];
      int prob[5] = { 1, 2, 2, 3, 3 };
      int occorrenze[3] = {0};
      int restituzioni[50] = {0};
      int i;
      FILE *filePtr;
      
      srand(time(NULL));
      
      for ( i = 0; i <= 49; i++ )
      {
          x[i] = prob[(rand() % 5)]; // --> prob[ 0 <= indice < 5] <--
          ++occorrenze[x[i]-1];
      }
      
      for ( i = 0; i <=2; i++ )
      {
          printf("Occorrenze di %d: %d\n", i+1 , occorrenze[i]);
      }
      
      if ( (filePtr = fopen("vettore.dat", "wb")) == NULL)
      {
         printf("Errore!! Il file non può essere aperto\n");
      }
      else
      {
          for ( i = 0; i < 50; i++ )
          {
              fseek( filePtr, i * sizeof ( x[i] ), SEEK_SET );
              fwrite( &x[i], sizeof ( x[i] ), 1, filePtr);
          }
      }
      
/* Verifichiamo che i dati memorizzati sono stati giustamente inseriti*/      
      

        for ( i = 0; i < 50; i++ )
        {
            fread ( &restituzioni[i], sizeof( restituzioni[i] ), 1, filePtr);
            printf("%d\n", restituzioni[i]);
        }
      fclose(filePtr);
}

Per verificare che l'operazione fosse andata a buon fine ho pensato di leggere i contenuti di quel file (ultimo ciclo for) ma come output mi escono una sequenza di 0. Cioè praticamente sono rimasti intatti gli elementi del vettore originale "richeste[50]"
I dati sono stati memorizzati male nel file oppure sono stati letti scorrettamente...Dov'è che sbaglio???

ci sono un po' di cose: intanto il fatto che non puoi leggere un file aperto in modalità di sola scrittura, poi che dopo aver scritto tutto il file il file pointer si è spostato alla fine, quindi dovresti fare, prima di cominciare a leggere, un fseek(filePtr, 0, SEEK_SET) che riporta all'inizio il file pointer, poi, sempre a proposito del file pointer, le chiamate a fseek che fai quando scrivi sono, di fatto, ridondanti, perché dopo aver scritto qualcosa il filepointer si trova proprio dove dovrai scrivere la prossima, poi in realtà tutto quel ciclo delle fwrite puoi sostituirlo con:

fwrite(x, sizeof (int), 50, filePtr);

che è del tutto equivalente, così come la lettura puoi sostituirla con

fseek(filePtr, 0, SEEK_SET);
fread(restituzioni, sizeof(int), 50, filePtr);