{"id":3317,"date":"2017-05-18T07:51:18","date_gmt":"2017-05-18T05:51:18","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=3317"},"modified":"2021-04-25T17:04:13","modified_gmt":"2021-04-25T15:04:13","slug":"descomposiciones-de-n-como-sumas-de-1-3-o-4-17","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/descomposiciones-de-n-como-sumas-de-1-3-o-4-17\/","title":{"rendered":"Descomposiciones de N como sumas de 1, 3 \u00f3 4."},"content":{"rendered":"<p>El n\u00famero 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 \u00f3 4:<\/p>\n<pre lang=\"text\">\n   5 = 1 + 1 + 1 + 1 + 1\n   5 = 1 + 1 + 3\n   5 = 1 + 3 + 1\n   5 = 3 + 1 + 1\n   5 = 1 + 4\n   5 = 4 + 1\n<\/pre>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   descomposiciones  :: Integer -> [[Integer]]\n   nDescomposiciones :: Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 \u00f3 4. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n      \u03bb> descomposiciones1 4\n      [[4],[3,1],[1,3],[1,1,1,1]]\n      \u03bb> descomposiciones1 5\n      [[4,1],[1,4],[3,1,1],[1,3,1],[1,1,3],[1,1,1,1,1]]\n      \u03bb> descomposiciones1 6\n      [[3,3],[4,1,1],[1,4,1],[1,1,4],[3,1,1,1],[1,3,1,1],[1,1,3,1],\n       [1,1,1,3],[1,1,1,1,1,1]]\n<\/pre>\n<ul>\n<li>(nDescomposiciones n) es el n\u00famero de descomposiciones de n como sumas cuyos sumandos sean 1, 3 \u00f3 4. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     nDescomposiciones 5                       ==  6\n     nDescomposiciones 10                      ==  64\n     nDescomposiciones 20                      ==  7921\n     nDescomposiciones 30                      ==  974169\n     length (show (nDescomposiciones (10^5)))  ==  20899\n<\/pre>\n<p><strong>Nota<\/strong>: Se puede usar programaci\u00f3n din\u00e1mica.<\/p>\n<h4>Soluciones<\/h4>\n<p>[schedule expon=&#8217;2017-05-25&#8242; expat=\u00bb06:00&#8243;]<\/p>\n<ul>\n<li>Las soluciones se pueden escribir en los comentarios hasta el 25 de mayo.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\u00bbhaskell\u00bb&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<p>[\/schedule]<\/p>\n<p>[schedule on=&#8217;2017-05-25&#8242; at=\u00bb06:00&#8243;]<\/p>\n<pre lang=\"haskell\">\r\nimport Data.List (genericLength)\r\nimport Data.Array\r\n\r\n-- 1\u00aa definici\u00f3n de descomposiciones (espacios de estado)\r\n-- ======================================================\r\n\r\ndescomposiciones1 :: Integer -> [[Integer]]\r\ndescomposiciones1 n = busca [inicial]\r\n  where\r\n    busca []        = []\r\n    busca (e:es)  \r\n      | esFinal n e = e : busca es\r\n      | otherwise   = busca (es ++ sucesores n e)\r\n\r\n-- Un estado es la lista de monedas usadas hasta ahora.\r\ntype Estado = [Integer] \r\n\r\n-- inicial es el estado inicial del problema; es decir, cuando no se\r\n-- ha usado ninguna moneda.\r\ninicial :: Estado\r\ninicial = []\r\n\r\n-- (esFinal n e) es verifica si e es un estado final del problema n. Por\r\n-- ejemplo, \r\n--    esFinal (8,5,3) (4,4,0)  ==  True\r\n--    esFinal (8,5,3) (4,0,4)  ==  False\r\nesFinal :: Integer -> Estado -> Bool\r\nesFinal n xs = sum xs == n\r\n\r\n-- (sucesores n e) es la lista de los sucesores del estado e en el\r\n-- problema n. Por ejemplo, \r\n--    sucesores (8,5,3) (8,0,0)  ==  [(3,5,0),(5,0,3)]\r\n--    sucesores (8,5,3) (3,5,0)  ==  [(0,5,3),(8,0,0),(3,2,3)]\r\nsucesores :: Integer -> Estado -> [Estado]\r\nsucesores n xs =\r\n     [1:xs | 1 + k <= n]\r\n  ++ [3:xs | 3 + k <= n]\r\n  ++ [4:xs | 4 + k <= n]\r\n  where k = sum xs\r\n\r\n-- 2\u00aa definici\u00f3n de descomposiciones (espacios de estado)\r\n-- ======================================================\r\n\r\ndescomposiciones2 :: Integer -> [[Integer]]\r\ndescomposiciones2 n = busca [inicial2 n]\r\n  where\r\n    busca []       = []\r\n    busca (e:es)  \r\n      | esFinal2 e = snd e : busca es\r\n      | otherwise  = busca (es ++ sucesores2 n e)\r\n\r\n-- Un estado es una par formado por la cantidad a conseguir y la lista\r\n-- de monedas usadas hasta ahora.\r\ntype Estado2 = (Integer,[Integer]) \r\n\r\n-- (inicial2 n) es el estado inicial del problema; es decir, cuando no se\r\n-- ha usado ninguna moneda.\r\ninicial2 :: Integer -> Estado2\r\ninicial2 n = (n,[])\r\n\r\n-- (esFinal2 e) es verifica si e es un estado final del problema. Por\r\n-- ejemplo, \r\n--    esFinal (8,5,3) (4,4,0)  ==  True\r\n--    esFinal (8,5,3) (4,0,4)  ==  False\r\nesFinal2 :: Estado2 -> Bool\r\nesFinal2 (k,_) = k == 0\r\n\r\n-- (sucesores2 n e) es la lista de los sucesores del estado e en el\r\n-- problema n. Por ejemplo, \r\n--    sucesores (8,5,3) (8,0,0)  ==  [(3,5,0),(5,0,3)]\r\n--    sucesores (8,5,3) (3,5,0)  ==  [(0,5,3),(8,0,0),(3,2,3)]\r\nsucesores2 :: Integer -> Estado2 -> [Estado2]\r\nsucesores2 n (k,xs) =\r\n     [(k-1, 1:xs) | k >= 1]\r\n  ++ [(k-3, 3:xs) | k >= 3]\r\n  ++ [(k-4, 4:xs) | k >= 4]\r\n\r\n-- 3\u00aa definici\u00f3n de descomposiciones\r\n-- =================================\r\n\r\ndescomposiciones3 :: Integer -> [[Integer]]\r\ndescomposiciones3 0 = [[]]\r\ndescomposiciones3 1 = [[1]]\r\ndescomposiciones3 2 = [[1,1]]\r\ndescomposiciones3 3 = [[1,1,1],[3]]\r\ndescomposiciones3 n =\r\n     [1:xs | xs <- descomposiciones3 (n-1)]\r\n  ++ [3:xs | xs <- descomposiciones3 (n-3)]\r\n  ++ [4:xs | xs <- descomposiciones3 (n-4)]  \r\n\r\n-- 4\u00aa definici\u00f3n de descomposiciones (din\u00e1mica)\r\n-- ============================================\r\n\r\ndescomposiciones4 :: Integer -> [[Integer]]\r\ndescomposiciones4 n = v!n\r\n  where v = array (0,n) [(i,aux v i) | i <- [0..n]] \r\n        aux v 0 = [[]]\r\n        aux v 1 = [[1]]\r\n        aux v 2 = [[1,1]]\r\n        aux v 3 = [[1,1,1],[3]]\r\n        aux v k =    map (1:) (v!(k-1))\r\n                  ++ map (3:) (v!(k-3))\r\n                  ++ map (4:) (v!(k-4))\r\n\r\n-- 1\u00aa definici\u00f3n de nDescomposiciones\r\n-- ==================================\r\n\r\nnDescomposiciones1 :: Integer -> Integer\r\nnDescomposiciones1 =\r\n  genericLength . descomposiciones1\r\n\r\n-- 2\u00aa definici\u00f3n de nDescomposiciones\r\n-- ==================================\r\n\r\nnDescomposiciones2 :: Integer -> Integer\r\nnDescomposiciones2 =\r\n  genericLength . descomposiciones2\r\n\r\n-- 3\u00aa definici\u00f3n de nDescomposiciones\r\n-- ==================================\r\n\r\nnDescomposiciones3 :: Integer -> Integer\r\nnDescomposiciones3 =\r\n  genericLength . descomposiciones3\r\n\r\n-- 4\u00aa definici\u00f3n de nDescomposiciones\r\n-- ==================================\r\n\r\nnDescomposiciones4 :: Integer -> Integer\r\nnDescomposiciones4 =\r\n  genericLength . descomposiciones4\r\n\r\n-- 5\u00aa definici\u00f3n de nDescomposiciones (din\u00e1mica)\r\n-- =============================================\r\n\r\nnDescomposiciones5 :: Integer -> Integer\r\nnDescomposiciones5 n = v!n\r\n  where v = array (0,n) [(i,aux v i) | i <- [0..n]] \r\n        aux v 0 = 1\r\n        aux v 1 = 1\r\n        aux v 2 = 1\r\n        aux v 3 = 2\r\n        aux v k = v!(k-1) + v!(k-3) + v!(k-4)\r\n\r\n-- Comparaci\u00f3n de eficiencia\r\n-- =========================\r\n\r\n--    \u03bb> nDescomposiciones1 20\r\n--    7921\r\n--    (3.21 secs, 3,199,383,064 bytes)\r\n--    \u03bb> nDescomposiciones2 20\r\n--    7921\r\n--    (3.17 secs, 3,176,666,880 bytes)\r\n--    \u03bb> nDescomposiciones3 20\r\n--    7921\r\n--    (0.08 secs, 17,714,152 bytes)\r\n--    \r\n--    \u03bb> nDescomposiciones3 27\r\n--    229970\r\n--    (3.73 secs, 628,730,968 bytes)\r\n--    \u03bb> nDescomposiciones4 27\r\n--    229970\r\n--    (0.45 secs, 111,518,016 bytes)\r\n--    \r\n--    \u03bb> nDescomposiciones4 30\r\n--    974169\r\n--    (2.02 secs, 454,484,992 bytes)\r\n--    \u03bb> nDescomposiciones5 30\r\n--    974169\r\n--    (0.00 secs, 0 bytes)\r\n\r\n--    \u03bb> nDescomposiciones2 30\r\n--    974169\r\n--    (2.10 secs, 441,965,208 bytes)\r\n--    \u03bb> nDescomposiciones3 30\r\n--    974169\r\n--    (0.00 secs, 0 bytes)\r\n--    \r\n--    \u03bb> length (show (nDescomposiciones5 (10^5)))\r\n--    20899\r\n--    (3.00 secs, 1,050,991,880 bytes)\r\n<\/pre>\n<p>[\/schedule]<\/p>\n","protected":false},"excerpt":{"rendered":"<p>El n\u00famero 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 \u00f3 4: 5 = 1 + 1 + 1 + 1 + 1 5 = 1 + 1 + 3 5 = 1 + 3 + 1 5 = 3 + 1 + 1 5 = 1 +&#8230;<\/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":[2],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3317"}],"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=3317"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3317\/revisions"}],"predecessor-version":[{"id":3320,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/3317\/revisions\/3320"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=3317"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=3317"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=3317"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}