[c] Numero casuale

[Dark Bard]

Come posso ottenere un numero casuale compreso in un intervallo ???

[nik600]

con la funzione random

[Poker1]

Sappi che, il sorteggio dei numeri casuali..non è così casuale come sembra.

Infatti non è altro che una sequenza che si ripete.

Es:

Random di 6 numeri -> 0 1 2 3 4 5

1° Sorteggiato numero 5 (rimanenti 0 1 2 3 4 6)
2° Sorteggiato numero 3 (rimanenti 0 1 2 4 6)
3° Sorteggiato numero 4 (rimanenti 0 1 2 6)
4° Sorteggiato numero 2 (rimanenti 0 1 6)
5° Sorteggiato numero 0 (rimanenti 1)
6° Sorteggiato numero 1 (rimanenti )

A questo punto, se fai un altro sorteggio, la sequenza di estrazione sarà identica alla precedente.

Per usare un sorteggio "veramente" casuale, devi scegliere come seme il numero di clock del sistema di quel momento ( che nn ricordo bene come si faccia). Così facendo hai una estrazione..quasi casuale.

[Trader]

Ciao,
con questo programma puoi, selezionando i valori delle variabili min e max, generare una sequenza di numeri casuali compresi nell' intervallo definito da min-max
nell' esempio ho posto min=25, max=30.
provalo.
ciao
Sergio

#include<time.h>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

void main()
{

int min = 25;
int max = 30;
int i, num_casuale;

srand( time(NULL) %10 );
for( i = 0 ; i < 300; i++ )
{

while( (num_casuale = rand()) < min || num_casuale > max)
;
printf(" %d ",num_casuale);
}
getch();

}

[Andrea Simonassi]

quest'ultimo algoritmo è quanto meno inefficiente, se devo cercare un numero in un dato RANGE > 0 , dato che rand genera un numero compreso tra 0 e RAND_MAX, la probabilità di beccare un numero nel RANGE ad ogni iterazione è di RANGE / RAND_MAXX, dove RAND_MAXX = RAND_MAX + 1.

In pratica prima di beccare un certo numero devi fare rand_max / 2 tentativi in media, e te lo dimostro.....

Utilizziamo la distribuzione binomiale per calcolare quanti tentativi sono necessari affinchè la probabilità di colpire un numero nel range sia del 50%.

se dovessimo trovare qual'è la probabilità che su n iterazioni almeno k risultati siano positivi la formula sarebbe

P(n,k) = n! / (k! * (n-k)!) * p^k * (1-p)^(n-k)

nel nostro caso il loop si interrompe alla prima iterazione con risultato positivo, quindi k=1

sia p = RANGE / RAND_MAXX
sia q = 1 - p

P(n,1) = n * p * q ^ (n - 1)

se poniamo P(n,1) = 0.5

0.5 = n * p * q ^ (n - 1)

ovvero

0 = n * p * q ^ (n - 1) - 0.5

su cui discutiamo un attimo prima di risolvere, rinominiamo intanto n in x:

0 = x * p * q ^ (x - 1) - 0.5

questa curva per x = 0 => y = -0.5

piu p si avvicina a zero e piu q si avvicina ad uno essendo q = 1 - p.

separiamo x * p, chiamiamolo J, e notiamo che questo valore cresce molto lentamente per p tendente a zero, quindi per p tendente a zero x deve tendere molto rapidamente a + infinito per fare si che J superi 0.5

prendiamo ora q ^ (x - 1) e chiamiamolo K

man mano che q tende ad 1 K tende ad avvicinarsi ad 1 rimanendo sempre minore di uno.

riepilogando J richiede x molto grandi per avvicinarsi a 0.5, K per x molto grandi tende ad avvicinarsi ad 1 quindi ignoriamolo un attimo visto che 1 è l'identità per il prodotto.

Cio significa che piu RAND_MAXX è grande piu il numero di iterazioni necessarie a trovare un numero in un range stretto cresce

esempio:
quante iterazion si fanno in media per trovare 1 numero tra 0 e 1 se rand max = 32678?

x * 3.06E-5 * 0.99997 ^ (n-1) - 0.5 = 0

0.99997 ^ (n-1) lo ignoriamo visto che sarà qualcosa di vicino ad 1 che non sposta di molto il risultato finale quindi

x * 3.06E-5 - 0.5 = 0

x = 0.5 / 3.06E-5

circa 16399 tentativi in media.....

ancora esempio:
RAND_MAX = 2^31

circa 1073741824 in media

senza contare che è (poco) possibile anche il caso in cui non si ottiene mai il risultato.

Fine della dim.

Ora la soluzione al problema era molto piu semplice e cioe

num = rand() % (max - min) + min;

[Trader]

...anche se ho fatto un po' fatica a seguire tutta la dimostrazione.
Purtroppo non ho ancora avuto il piacere di studiare la distribuzione binomiale, sai in seconda superiore il programma matematico non e' molto ampio.....
Comunque grazie

[Andrea Simonassi]

Poco male, tanto ho fatto un errore di calcolo!