Distancia esperada entre dos puntos de un cuadrado unitario
Definir, por simulación, la función
|
1 |
distanciaEsperada :: Int -> IO Double |
tal que (distanciaEsperada n) es la distancia esperada entre n puntos del cuadrado unitario de vértices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,
|
1 2 3 4 5 6 |
distanciaEsperada 10 == 0.43903617921423593 distanciaEsperada 10 == 0.6342350621260004 distanciaEsperada 100 == 0.5180418995364429 distanciaEsperada 100 == 0.5288261085653962 distanciaEsperada 1000 == 0.5143804432569616 distanciaEsperada 10000 == 0.5208360147922616 |
El valor exacto de la distancia esperada es
|
1 |
ve = (sqrt(2) + 2 + 5*log(1+sqrt(2)))/15 = 0.5214054331647207 |
Definir la función
|
1 |
graficaDistanciaEsperada :: [Int] -> IO () |
tal que (graficaDistanciaEsperada ns) dibuja las gráficas de los pares (n, distanciaEsperada n) para n en la lista creciente ns junto con la recta y = ve, donde ve es el valor exacto. Por ejemplo, (graficaDistanciaEsperada [10,30..4000]) dibuja
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 |
import Data.List (genericLength) import System.Random (newStdGen, randomRIO, randomRs) import Control.Monad (replicateM) import Graphics.Gnuplot.Simple -- 1ª solución -- =========== -- Un punto es un par de números reales. type Punto = (Double, Double) -- (puntosDelCuadrado n) es una lista de n puntos del cuadrado -- unitario de vértices opuestos (0,0) y (1,1). Por ejemplo, -- λ> puntosDelCuadrado 3 -- [(0.6067427807212623,0.24785843546479303), -- (0.9579158098726746,8.047408846191773e-2), -- (0.856758357789639,0.9814972717003113)] -- λ> puntosDelCuadrado 3 -- [(1.9785720974027532e-2,0.6343219201012211), -- (0.21903717179861604,0.20947986189590784), -- (0.4739903340716357,1.2262474491489095e-2)] puntosDelCuadrado :: Int -> IO [Punto] puntosDelCuadrado n = do gen <- newStdGen let xs = randomRs (0,1) gen (as, ys) = splitAt n xs (bs, _) = splitAt n ys return (zip as bs) -- (distancia p1 p2) es la distancia entre los puntos p1 y p2. Por -- ejemplo, -- distancia (0,0) (3,4) == 5.0 distancia :: Punto -> Punto -> Double distancia (x1,y1) (x2,y2) = sqrt ((x1-x2)^2+(y1-y2)^2) -- (distancias ps) es la lista de las distancias entre los elementos 1º -- y 2º, 3º y 4º, ... de ps. Por ejemplo, -- distancias [(0,0),(3,4),(1,1),(7,9)] == [5.0,10.0] distancias :: [Punto] -> [Double] distancias [] = [] distancias (p1:p2:ps) = distancia p1 p2 : distancias ps -- (media xs) es la media aritmética de los elementos de xs. Por ejemplo, -- media [1,7,1] == 3.0 media :: [Double] -> Double media xs = sum xs / genericLength xs -- (distanciaEsperada n) es la distancia esperada entre n puntos -- aleatorios en el cuadrado unitario. Por ejemplo, -- λ> distanciaEsperada 100 -- 0.4712858421448363 -- λ> distanciaEsperada 100 -- 0.4947745206856711 distanciaEsperada :: Int -> IO Double distanciaEsperada n = do ps <- puntosDelCuadrado (2*n) return (media (distancias ps)) -- 2ª solución -- =========== distanciaEsperada2 :: Int -> IO Double distanciaEsperada2 n = do ps <- puntosDelCuadrado2 (2*n) return (media (distancias ps)) -- (puntosDelCuadrado2 n) es una lista de n puntos del cuadrado -- unitario de vértices opuestos (0,0) y (1,1). Por ejemplo, -- λ> puntosDelCuadrado2 3 -- [(0.9836699352638695,0.5143414844876929), -- (0.8715237339877027,0.9905157772823782), -- (0.29502946161912935,0.16889248111565192)] -- λ> puntosDelCuadrado2 3 -- [(0.20405570457106392,0.47574116941605116), -- (0.7128182811364226,3.201419787777959e-2), -- (0.5576891231675457,0.9994474730919443)] puntosDelCuadrado2 :: Int -> IO [Punto] puntosDelCuadrado2 n = replicateM n puntoDelCuadrado2 -- (puntoDelCuadrado2 n) es un punto del cuadrado unitario de vértices -- opuestos (0,0) y (1,1). Por ejemplo, -- λ> puntoDelCuadrado2 -- (0.7512991739803923,0.966436016138578) -- λ> puntoDelCuadrado2 -- (0.7306826194847795,0.8984574498515252) puntoDelCuadrado2 :: IO Punto puntoDelCuadrado2 = do x <- randomRIO (0, 1.0) y <- randomRIO (0, 1.0) return (x, y) -- 3ª solución -- =========== distanciaEsperada3 :: Int -> IO Double distanciaEsperada3 n = do ds <- distanciasAleatorias n return (media ds) -- (distanciasAleatorias n) es la lista de las distancias aleatorias -- entre n pares de puntos del cuadrado unitario. Por ejemplo, -- λ> distanciasAleatorias 3 -- [0.8325589110989705,0.6803336613847881,0.1690051224111662] -- λ> distanciasAleatorias 3 -- [0.3470124940889039,0.459002678562019,0.7665623634969365] distanciasAleatorias :: Int -> IO [Double] distanciasAleatorias n = replicateM n distanciaAleatoria -- distanciaAleatoria es la distancia de un par de punto del cuadrado -- unitario elegidos aleatoriamente. Por ejemplo, -- λ> distanciaAleatoria -- 0.8982361685460913 -- λ> distanciaAleatoria -- 0.9777207485571939 -- λ> distanciaAleatoria -- 0.6042223512347842 distanciaAleatoria :: IO Double distanciaAleatoria = do p1 <- puntoDelCuadrado2 distancia p1 <$> puntoDelCuadrado2 -- 4ª solución -- =========== distanciaEsperada4 :: Int -> IO Double distanciaEsperada4 n = media <$> distanciasAleatorias n -- Gráfica -- ======= graficaDistanciaEsperada :: [Int] -> IO () graficaDistanciaEsperada ns = do ys <- mapM distanciaEsperada ns let e = (sqrt 2 + 2 + 5 * log (1 + sqrt 2)) / 15 plotLists [ Key Nothing -- , PNG "Distancia_esperada_entre_dos_puntos.png" ] [ zip ns ys , zip ns (repeat e)] |
El código se encuentra en GitHub.