Tirare i dadi

Qualche giorno fa su un (poco) noto social, il buon Zar poneva una questione apparentemente semplice.

“Ci sono cinque dadi a sei facce recanti (le facce) i seguenti numeri: 0, 0, 1, 2, 3, 4. Si lanciano tutti insieme e si fa la somma dei valori ottenuti. Problema: calcolare le probabilità di uscita dei numeri da 0 a 20.”

Nel post linkato Zar fa la trattazione matematica, e vi consiglio di leggerlo tutto perché merita. Nel “socialino dell’ammmore” abbiamo anche discusso alcune soluzioni al problema tramite programmini in vari linguaggi di programmazione. Io, che nel frattempo mi sono parecchio arrugginito con Haskell, ne ho approfittato per proporre 2 soluzioni con questo elegante linguaggio di programmazione: la prima semplice semplice, la seconda una generalizzazione della prima. Dato che le soluzioni le avevo messe su pastebin e chissà che fine faranno, adesso le riposto qui, così magari viene voglia anche a voi di provare nel vostro linguaggio di programmazione preferito.

Cominciamo con la prima:

module Main where
import System.Environment

main :: IO ()
main = do args <- getArgs          
          putStrLn("Probabilità di " ++
                   (args !! 0) ++ " con 5 dadi : " ++ " = " ++ 
                   show( prob_dadi (read (args!!0)::Integer) 5 ))
          -- putStrLn("Test : " ++ show(test))


prob_faccia :: Integer -> Rational               
prob_faccia 0 = 2/6
prob_faccia 1 = 1/6
prob_faccia 2 = 1/6
prob_faccia 3 = 1/6
prob_faccia 4 = 1/6
prob_faccia n = 0
                
prob_dadi :: Integer -> Integer -> Rational
             
prob_dadi n 0 | n == 0   = 1
              | n > 0    = 0
              | n < 0    = 0
                           
prob_dadi n nd  =  (prob_faccia 0)  *  (prob_dadi n (nd-1)) + 
                   (prob_faccia 1)  *  (prob_dadi (n-1) (nd-1)) +
                   (prob_faccia 2)  *  (prob_dadi (n-2) (nd-1)) +  
                   (prob_faccia 3)  *  (prob_dadi (n-3) (nd-1)) +
                   (prob_faccia 4)  *  (prob_dadi (n-4) (nd-1))


test = (test_loop 20)

test_loop (-1) = 0
test_loop n = (prob_dadi n 5) + test_loop (n-1)

Il programmino prende sulla linea di comando il numero di cui si vuole calcolare la probabilità (tra 5 e 20 ovviamente) e restituisce la probabilità in forma di frazione. La funzione principale è prob_dadi che naturalmente è ricorsiva. Il primo parametro n è il numero di cui si vuole calcolare la probabilità, il secondo è il numero di dadi da lanciare.

Per ottenere n, si lancia un dado e:
– si calcola la probabilità che venga 1, e si moltiplica per la probabilità che i restanti nd-1 dadi ottengano n-1;
– si calcola la probabilità che venga 2, e si moltiplica per la probabilità che i restanti nd-1 dadi ottengano il numero n-2
– ecc.
Tutte queste probabilità si sommano per ottenere la probabilità finale.
Resta da stabilire la fine della ricorsione: la probabilità di ottenere n > 0 con 0 dadi, è sempre 0; la probabilità di ottenere n == 0 con 0 dadi è pari a 1.

E’ chiaro? Spero di si. Se avete capito questo programmino, potrete agevolmente capire il secondo programmino che generalizza il contenuto delle facce mettendolo in una lista.
Ecco il codice (ATTENZIONE: per mia praticità, e per confondervi un po’ le idee, qui ho scambiato l’ordine dei parametri della prob_dadi! adesso prende prima il numero dei dadi e poi il numero da ottenere):

module Main where
import System.Environment

main :: IO ()
main = do args <- getArgs          
          putStrLn("Probabilità di " ++
                   (args !! 0) ++ " con 5 dadi : " ++ " = " ++ 
                   show( prob_dadi 5 (read (args!!0)::Integer)))
          -- putStrLn("Test : " ++ show(test))

facce :: [Integer]
facce = [0, 0, 1, 2, 3, 4]

prob_faccia :: Rational
prob_faccia = 1/6

prob_partial:: Integer -> Integer -> Integer -> Rational
prob_partial nd n faccia =  
  prob_faccia * (prob_dadi (nd-1) (n-faccia))


prob_dadi :: Integer -> Integer -> Rational             
prob_dadi 0 n | n == 0   = 1
              | n > 0    = 0
              | n < 0    = 0

prob_dadi nd n =
  sum (map (prob_partial nd n) facce)  

test = (test_loop 20)

test_loop (-1) = 0
test_loop n = (prob_dadi 5 n) + test_loop (n-1)

Qui prob_dadi fa una sommatoria (che nel programma precedente era svolta a mano, elemento per elemento) di una lista che risulta dall’applicazione (tramite map) della funzione prob_partial agli elementi della lista facce.

La funzione prob_partial fa la moltiplicazione di prima:
– calcola la probabilità di ottenere una certa faccia, e la moltiplica per la probabilità di ottenere il numero n-faccia con nd-1 dadi.

E adesso a voi! (Voglio la stessa cosa in Lisp, mi raccomando!)

Annunci
Post a comment or leave a trackback: Trackback URL.

Commenti

  • Jean M. M.  On 7 marzo 2015 at 10:59

    Tanto per giocare, ecco come si potrebbe fare in J

    v =: 0 0 1 2 3 4
    A =: , v+/^:4 v
    x: (+/ A =/ i.21) % 6^5

    Il verbo +/ produce una tabella con il prodotto cartesiano tra v e v,
    e l’avverbio ^:4 ripete questo prodotto 4 volte (e quindi per 5
    dadi). Il verbo , fa il “flatten” del risultato, quindi A è un vettore
    di lunghezza 7776=5^6 con tutti i possibili lanci dei 5 dadi.

    Il verbo = confronta questo vettore, elemento per elemento, con un
    numero, e produce 1 per ogni occorrenza del numero e 0 altrimenti. Con
    +/ sommo tutti gli 1, quindi ad esempio +/ A = 3 restituisce 280, che
    sono quanti lanci di cinque dati restituiscono somma 3.

    Uso ancora una volta l’avverbio / per ripetere il confronto, con =/,
    su tutti i numeri da 0 a 20, ossia per ogni elemento del vettore i.21.

    Per completare, calcolo la probabilità in modo esatto come frazione
    semplificata, con x:, rapportando il numero di modi di ottenere i
    totali da 0 a 20 ai casi possibili, 6^5. Il risultato inizia con

    1r243 5r486 5r243 35r972 25r432 601r7776 745r7776

    Non hai messo i risultati, quindi non posso confrontare 🙂

    • juhan  On 7 marzo 2015 at 12:49

      Jean rockz! 😀 Ma j è davvero stregoneria, molto più di PERL che già non scherza.

    • glipari  On 7 marzo 2015 at 22:55

      Ecco i risultati del programma, che calcola le probabilità dei numeri da 0 a 20, in forma di lista:

      [1 % 243,
      5 % 486,
      5 % 243,
      35 % 972,
      25 % 432,
      601 % 7776,
      745 % 7776,
      95 % 864,
      905 % 7776,
      865 % 7776,
      781 % 7776,
      655 % 7776,
      505 % 7776,
      355 % 7776,
      235 % 7776,
      47 % 2592,
      25 % 2592,
      35 % 7776,
      5 % 2592,
      5 % 7776,
      1 % 7776]

      Mi sembra che i primi che hai messo coincidano! J è un po criptico, bisogna abituarsi alla sintassi piuttosto concisa (ma ci si abitua a tutto con un po’ di sforzo mentale…) Grazie per il contributo 🙂

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: