Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente:<\/p>\n
Por ejemplo, para n = 5<\/p>\n
\n Pase | Puerta 1 | Puerta 2 | Puerta 3 | Puerta 4 | Puerta 5\n Inicial | Cerrada | Cerrada | Cerrada | Cerrada | Cerrada\n Pase 1 | Abierta | Abierta | Abierta | Abierta | Abierta\n Pase 2 | Abierta | Cerrada | Abierta | Cerrada | Abierta\n Pase 3 | Abierta | Cerrada | Cerrada | Cerrada | Abierta\n Pase 4 | Abierta | Cerrada | Cerrada | Abierta | Abierta\n Pase 5 | Abierta | Cerrada | Cerrada | Abierta | Cerrada \n<\/pre>\nLos estados de las puertas se representan por el siguiente tipo de datos<\/p>\n
\n data Estado = Abierta | Cerrada deriving Show\n<\/pre>\nDefinir la funci\u00f3n<\/p>\n
\n final :: Int -> [Estado]\n<\/pre>\ntal que (final n) es la lista de los estados de las n puertas despu\u00e9s de que hayan pasado los n camareros. Por ejemplo,<\/p>\n
\n ghci> final 5\n [Abierta,Cerrada,Cerrada,Abierta,Cerrada]\n ghci> final 7\n [Abierta,Cerrada,Cerrada,Abierta,Cerrada,Cerrada,Cerrada]\n<\/pre>\nSoluciones<\/h4>\n
[schedule on=’2020-06-05′ at=\u00bb06:00″]<\/p>\n
\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ndata Estado = Abierta | Cerrada \n deriving (Eq, Show)\n \ncambia Abierta = Cerrada\ncambia Cerrada = Abierta\n\n-- (inicial n) es el estado inicial para el problema de las n\n-- habitaciones. Por ejemplo,\n-- inicial 5 == [Cerrada,Cerrada,Cerrada,Cerrada,Cerrada]\ninicial :: Int -> [Estado]\ninicial n = replicate n Cerrada\n\n-- (pase k es) es la lista de los estados de las puertas despu\u00e9s de pasar el\n-- camarero k que las encuentra en los estados es. Por ejemplo,\n-- ghci> pase 1 (inicial 5)\n-- [Abierta,Abierta,Abierta,Abierta,Abierta]\n-- ghci> pase 2 it\n-- [Abierta,Cerrada,Abierta,Cerrada,Abierta]\n-- ghci> pase 3 it\n-- [Abierta,Cerrada,Cerrada,Cerrada,Abierta]\n-- ghci> pase 4 it\n-- [Abierta,Cerrada,Cerrada,Abierta,Abierta]\n-- ghci> pase 5 it\n-- [Abierta,Cerrada,Cerrada,Abierta,Cerrada]\npase :: [Estado] -> Int -> [Estado] \npase es k = zipWith cambiaK es [1..] \n where cambiaK e n | n `mod` k == 0 = cambia e\n | otherwise = e\n \nfinal :: Int -> [Estado]\nfinal n = aux [1..n] (inicial n) \n where aux [] es = es \n aux (k:ks) es = aux ks (pase es k)\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nfinal2 :: Int -> [Estado]\nfinal2 n = foldl pase (inicial n) [1..n] \n\n-- 3\u00aa soluci\u00f3n\n-- =============\n\nfinal3 :: Int -> [Estado]\nfinal3 n = map f [1..n]\n where f x | even (length (divisores x)) = Cerrada\n | otherwise = Abierta\n\ndivisores :: Int -> [Int]\ndivisores n = [x | x <- [1..n], n `mod` x == 0]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\n-- En primer lugar, vamos a determinar la lista de las posiciones\n-- (comenzando a contar en 1) de las puertas que quedan abierta en el\n-- problema de las n puertas. \nposicionesAbiertas :: Int -> [Int]\nposicionesAbiertas n = \n [x | (x,y) <- zip [1..] (final n), y == Abierta]\n\n-- Al calcularlas,\n-- ghci> posicionesAbiertas 200\n-- [1,4,9,16,25,36,49,64,81,100,121,144,169,196]\n-- Se observa las que quedan abiertas son las que sus posiciones son\n-- cuadrados perfectos. Usando esta observaci\u00f3n se construye la\n-- siguiente definici\u00f3n\n\nfinal4 :: Int -> [Estado]\nfinal4 n = aux [1..n] [k*k | k <- [1..]] \n where aux (x:xs) (y:ys) | x == y = Abierta : aux xs ys\n aux (x:xs) ys = Cerrada : aux xs ys\n aux [] _ = []\n\n-- ---------------------------------------------------------------------\n-- \u00a7 Comparaci\u00f3n de eficiencia --\n-- ---------------------------------------------------------------------\n\n-- ghci> last (final 1000)\n-- Cerrada\n-- (0.23 secs, 218727400 bytes)\n-- ghci> last (final 2000)\n-- Cerrada\n-- (1.78 secs, 868883080 bytes)\n-- ghci> last (final2 1000)\n-- Cerrada\n-- (0.08 secs, 218729392 bytes)\n-- ghci> last (final2 2000)\n-- Cerrada\n-- (1.77 secs, 868948600 bytes)\n-- ghci> last (final3 1000)\n-- Cerrada\n-- (0.01 secs, 1029256 bytes)\n-- ghci> last (final3 2000)\n-- Cerrada\n-- (0.01 secs, 2121984 bytes)\n-- ghci> last (final4 1000)\n-- Cerrada\n-- (0.01 secs, 1029328 bytes)\n-- ghci> last (final4 2000)\n-- Cerrada\n-- (0.01 secs, 1578504 bytes)\n-- ghci> last (final3 10000)\n-- Abierta\n-- (0.01 secs, 4670104 bytes)\n-- ghci> last (final3 100000)\n-- Cerrada\n-- (0.09 secs, 38717032 bytes)\n-- ghci> last (final3 1000000)\n-- Abierta\n-- (1.27 secs, 377100832 bytes)\n-- ghci> last (final4 1000000)\n-- Abierta\n-- (1.41 secs, 273292448 bytes)\n<\/pre>\nOtras soluciones<\/h4>\n\n- Se pueden escribir otras soluciones en los comentarios.\n
- El c\u00f3digo se debe escribir entre una l\u00ednea con <pre lang="haskell"> y otra con <\/pre>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"
Un hotel dispone de n habitaciones y n camareros. Los camareros tienen la costumbre de cambiar de estado las puertas (es decir, abrir las cerradas y cerrar las abiertas). El proceso es el siguiente: Inicialmente todas las puertas est\u00e1n cerradas. El primer camarero cambia de estado las puertas de todas las habitaciones. El segundo cambia…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[4],"tags":[11,19,60,133,76],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5823"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=5823"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5823\/revisions"}],"predecessor-version":[{"id":5854,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5823\/revisions\/5854"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5823"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5823"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5823"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}