Problema de las puertas
Enunciado
|
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 |
-- Un hotel dispone de n habitaciones y n camareros. Los camareros -- tienen la costumbre de cambiar de estado las puestas (es decir, -- abrir las cerradas y cerrar las abiertas). El proceso es el -- siguiente: -- * Inicialmente todas las puertas están cerradas. -- * El primer camarero cambia de estado las puertas de todas las -- habitaciones. -- * El segundo cambia de estado de las puertas de las habitaciones -- pares. -- * El tercero cambia de estado todas las puertas que son -- múltiplos de 3. -- * El cuarto cambia de estado todas las puertas que son múltiplos -- de 4 -- * Así hasta que ha pasado el último camarero. -- Por ejemplo, para n = 5 -- Pase | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5 -- --------+----------+----------+----------+----------+--------- -- Inicial | Cerrada | Cerrada | Cerrada | Cerrada | Cerrada -- Pase 1 | Abierta | Abierta | Abierta | Abierta | Abierta -- Pase 2 | Abierta | Cerrada | Abierta | Cerrada | Abierta -- Pase 3 | Abierta | Cerrada | Cerrada | Cerrada | Abierta -- Pase 4 | Abierta | Cerrada | Cerrada | Abierta | Abierta -- Pase 5 | Abierta | Cerrada | Cerrada | Abierta | Cerrada -- -- Los estados de las puertas se representan por el siguiente tipo de -- datos -- data Estado = Abierta | Cerrada deriving Show -- -- Definir la función -- final :: Int -> [Estado] -- tal que (final n) es la lista de los estados de las n puertas después -- de que hayan pasado los n camareros. Por -- ejemplo, -- ghci> final 5 -- [Abierta,Cerrada,Cerrada,Abierta,Cerrada] -- ghci> final 7 -- [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada] |
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 |
-- 1ª solución -- =========== data Estado = Abierta | Cerrada deriving (Eq, Show) cambia Abierta = Cerrada cambia Cerrada = Abierta -- (inicial n) es el estado inicial para el problema de las n -- habitaciones. Por ejemplo, -- inicial 5 == [Cerrada,Cerrada,Cerrada,Cerrada,Cerrada] inicial :: Int -> [Estado] inicial n = replicate n Cerrada -- (pase k es) es la lista de los estados de las puertas después de pasar el -- camarero k que las encuentra en los estados es. Por ejemplo, -- ghci> pase 1 (inicial 5) -- [Abierta,Abierta,Abierta,Abierta,Abierta] -- ghci> pase 2 it -- [Abierta,Cerrada,Abierta,Cerrada,Abierta] -- ghci> pase 3 it -- [Abierta,Cerrada,Cerrada,Cerrada,Abierta] -- ghci> pase 4 it -- [Abierta,Cerrada,Cerrada,Abierta,Abierta] -- ghci> pase 5 it -- [Abierta,Cerrada,Cerrada,Abierta,Cerrada] pase :: [Estado] -> Int -> [Estado] pase es k = zipWith cambiaK es[1..] where cambiaK e n | n `mod` k == 0 = cambia e | otherwise = e final :: Int -> [Estado] final n = aux [1..n] (inicial n) where aux [] es = es aux (k:ks) es = aux ks (pase es k) -- 2ª solución (con foldl') -- ======================== final2 :: Int -> [Estado] final2 n = foldl pase (inicial n) [1..n] -- 3ª definición (basada en los cambios de cada posición) -- ====================================================== final3 :: Int -> [Estado] final3 n = map f [1..n] where f x | even (length (divisores x)) = Cerrada | otherwise = Abierta divisores :: Int -> [Int] divisores n = [x| x <- [1..n], n `mod` x == 0] -- 4ª definición (basada en posiciones de abiertas) -- ================================================ -- En primer lugar, vamos a determinar la lista de las posiciones -- (comenzando a contar en 1) de las puertas que quedan abierta en el -- problema de las n puertas. posicionesAbiertas :: Int -> [Int] posicionesAbiertas n = [x | (x,y) <- zip [1..] (final n), y == Abierta] -- Al calcularlas, -- ghci> posicionesAbiertas 200 -- [1,4,9,16,25,36,49,64,81,100,121,144,169,196] -- Se observa las que quedan abiertas son las que sus posiciones son -- cuadrados perfectos. Usando esta observación se construye la -- siguiente definición final4 :: Int -> [Estado] final4 n = aux [1..n] [k*k | k <- [1..]] where aux (x:xs) (y:ys) | x == y = Abierta : aux xs ys aux (x:xs) ys = Cerrada : aux xs ys aux [] _ = [] |