Dopo aver visto Project Euler - Longest Collatz Sequence (n.14) - codice C, vediamo un altro caso interessante ovvero la probabilità associata ad un gioco di dadi (dati che in generale essere "particolari").
Questo esempio è interessante perché, sebbene l'algoritmo in sé non sia complicato (altre challenge di Project Euler sono ben più difficili!) è opportuno che l'algoritmo sia scritto in modo molto efficiente, ad esempio memorizzando come "register" tutte le variabili e possibilmente allocando uno spazio non più grande del necessario (short, int, long int) per evitare quindi inefficienza.
Il testo, che trovate qui lo possiamo sintetizzare così: Peter ha un dado con 4 facce (1,2,3,4) mentre Colin un dado con 6 facce (1,2,3,4,5,6). Entrambi lanciano i rispettivi dadi, chi ottiene il numero più alto vince (se il numero è uguale, è pareggio e non si conta). Calcolare la probabilità di vincita di Peter (che ad intuito sappiamo già essere più bassa dato che il valore atteso dei dadi è 2.5 e 3.5 rispettivamente), con 7 cifre decimali.
Da qui capiamo l'importanza di rendere efficiente il codice, occorre fare una media su N iterazioni con N sufficientemente grande (il valore che ho scelto è un miliardo!), in modo tale da avere convergenza statistica al valore finale che altrimenti potrebbe avere una componente aleatoria.
Ricordiamo inoltre che la filosofia di Project Euler è quella di creare codice che su una macchina "normale" richieda un tempo di esecuzione inferiore al minuto, altrimenti non è scritto in modo abbastanza efficiente. Il codice che segue, ha richiesto circa 19 secondi di esecuzione e il risultato tende a quanto previsto. Quindi senza dover "scomodare" la potenza di calcolo grazie al calcolo distribuito 😄
Riporto il codice scritto in C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
short randomx(short x);
int main(){
srand(time(0));
register unsigned int i;
register unsigned int x1=0;
register unsigned int x2=0;
register unsigned int N=1000000000;
register unsigned int cont1=0;
clock_t start = clock();
for(i=0;i<N;i++){
x1=randomx(4);
x2=randomx(6);
if(x1>x2){
cont1++;
}
}
clock_t end = clock();
printf("P(win1) = %.7f\n",(float)(1.0*cont1/N));
printf("tempo di esecuzione: %f s\n", (float)(end - start) / CLOCKS_PER_SEC);
return 0;
}
short randomx(short x){
return rand()%(x)+1;
}
Osservazione interessante: in questo caso risulta 0.25 ovvero la probabilità che vinca Peter è del 25%. L'osservazione interessante che si può fare è questa, il programma è molto flessibile e può facilmente adattarsi ad atri casi, ad esempio cambiando i numeri 4 e 6 con qualcos'altro (un dado con 20 facce, e così via).
