{"id":4099,"date":"2018-05-24T06:00:06","date_gmt":"2018-05-24T04:00:06","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=4099"},"modified":"2018-05-31T07:40:26","modified_gmt":"2018-05-31T05:40:26","slug":"descomposiciones-de-n-como-sumas-de-1-3-o-4","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/descomposiciones-de-n-como-sumas-de-1-3-o-4\/","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<pre lang=\"haskell\">\nimport Data.List (genericLength)\nimport Data.Array\n\n-- 1\u00aa definici\u00f3n de descomposiciones (espacios de estado)\n-- ======================================================\n\ndescomposiciones1 :: Integer -> [[Integer]]\ndescomposiciones1 n = busca [inicial]\n  where\n    busca []        = []\n    busca (e:es)  \n      | esFinal n e = e : busca es\n      | otherwise   = busca (es ++ sucesores n e)\n\n-- Un estado es la lista de monedas usadas hasta ahora.\ntype Estado = [Integer] \n\n-- inicial es el estado inicial del problema; es decir, cuando no se\n-- ha usado ninguna moneda.\ninicial :: Estado\ninicial = []\n\n-- (esFinal n e) es verifica si e es un estado final del problema n. Por\n-- ejemplo, \n--    esFinal (8,5,3) (4,4,0)  ==  True\n--    esFinal (8,5,3) (4,0,4)  ==  False\nesFinal :: Integer -> Estado -> Bool\nesFinal n xs = sum xs == n\n\n-- (sucesores n e) es la lista de los sucesores del estado e en el\n-- problema n. Por ejemplo, \n--    sucesores (8,5,3) (8,0,0)  ==  [(3,5,0),(5,0,3)]\n--    sucesores (8,5,3) (3,5,0)  ==  [(0,5,3),(8,0,0),(3,2,3)]\nsucesores :: Integer -> Estado -> [Estado]\nsucesores n xs =\n     [1:xs | 1 + k <= n]\n  ++ [3:xs | 3 + k <= n]\n  ++ [4:xs | 4 + k <= n]\n  where k = sum xs\n\n-- 2\u00aa definici\u00f3n de descomposiciones (espacios de estado)\n-- ======================================================\n\ndescomposiciones2 :: Integer -> [[Integer]]\ndescomposiciones2 n = busca [inicial2 n]\n  where\n    busca []       = []\n    busca (e:es)  \n      | esFinal2 e = snd e : busca es\n      | otherwise  = busca (es ++ sucesores2 n e)\n\n-- Un estado es una par formado por la cantidad a conseguir y la lista\n-- de monedas usadas hasta ahora.\ntype Estado2 = (Integer,[Integer]) \n\n-- (inicial2 n) es el estado inicial del problema; es decir, cuando no se\n-- ha usado ninguna moneda.\ninicial2 :: Integer -> Estado2\ninicial2 n = (n,[])\n\n-- (esFinal2 e) es verifica si e es un estado final del problema. Por\n-- ejemplo, \n--    esFinal (8,5,3) (4,4,0)  ==  True\n--    esFinal (8,5,3) (4,0,4)  ==  False\nesFinal2 :: Estado2 -> Bool\nesFinal2 (k,_) = k == 0\n\n-- (sucesores2 n e) es la lista de los sucesores del estado e en el\n-- problema n. Por ejemplo, \n--    sucesores (8,5,3) (8,0,0)  ==  [(3,5,0),(5,0,3)]\n--    sucesores (8,5,3) (3,5,0)  ==  [(0,5,3),(8,0,0),(3,2,3)]\nsucesores2 :: Integer -> Estado2 -> [Estado2]\nsucesores2 n (k,xs) =\n     [(k-1, 1:xs) | k >= 1]\n  ++ [(k-3, 3:xs) | k >= 3]\n  ++ [(k-4, 4:xs) | k >= 4]\n\n-- 3\u00aa definici\u00f3n de descomposiciones\n-- =================================\n\ndescomposiciones3 :: Integer -> [[Integer]]\ndescomposiciones3 0 = [[]]\ndescomposiciones3 1 = [[1]]\ndescomposiciones3 2 = [[1,1]]\ndescomposiciones3 3 = [[1,1,1],[3]]\ndescomposiciones3 n =\n     [1:xs | xs <- descomposiciones3 (n-1)]\n  ++ [3:xs | xs <- descomposiciones3 (n-3)]\n  ++ [4:xs | xs <- descomposiciones3 (n-4)]  \n\n-- 4\u00aa definici\u00f3n de descomposiciones (din\u00e1mica)\n-- ============================================\n\ndescomposiciones4 :: Integer -> [[Integer]]\ndescomposiciones4 n = v!n\n  where v = array (0,n) [(i,aux v i) | i <- [0..n]] \n        aux v 0 = [[]]\n        aux v 1 = [[1]]\n        aux v 2 = [[1,1]]\n        aux v 3 = [[1,1,1],[3]]\n        aux v k =    map (1:) (v!(k-1))\n                  ++ map (3:) (v!(k-3))\n                  ++ map (4:) (v!(k-4))\n\n-- 1\u00aa definici\u00f3n de nDescomposiciones\n-- ==================================\n\nnDescomposiciones1 :: Integer -> Integer\nnDescomposiciones1 =\n  genericLength . descomposiciones1\n\n-- 2\u00aa definici\u00f3n de nDescomposiciones\n-- ==================================\n\nnDescomposiciones2 :: Integer -> Integer\nnDescomposiciones2 =\n  genericLength . descomposiciones2\n\n-- 3\u00aa definici\u00f3n de nDescomposiciones\n-- ==================================\n\nnDescomposiciones3 :: Integer -> Integer\nnDescomposiciones3 =\n  genericLength . descomposiciones3\n\n-- 4\u00aa definici\u00f3n de nDescomposiciones\n-- ==================================\n\nnDescomposiciones4 :: Integer -> Integer\nnDescomposiciones4 =\n  genericLength . descomposiciones4\n\n-- 5\u00aa definici\u00f3n de nDescomposiciones (din\u00e1mica)\n-- =============================================\n\nnDescomposiciones5 :: Integer -> Integer\nnDescomposiciones5 n = v!n\n  where v = array (0,n) [(i,aux v i) | i <- [0..n]] \n        aux v 0 = 1\n        aux v 1 = 1\n        aux v 2 = 1\n        aux v 3 = 2\n        aux v k = v!(k-1) + v!(k-3) + v!(k-4)\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n--    \u03bb> nDescomposiciones1 20\n--    7921\n--    (3.21 secs, 3,199,383,064 bytes)\n--    \u03bb> nDescomposiciones2 20\n--    7921\n--    (3.17 secs, 3,176,666,880 bytes)\n--    \u03bb> nDescomposiciones3 20\n--    7921\n--    (0.08 secs, 17,714,152 bytes)\n--    \n--    \u03bb> nDescomposiciones3 27\n--    229970\n--    (3.73 secs, 628,730,968 bytes)\n--    \u03bb> nDescomposiciones4 27\n--    229970\n--    (0.45 secs, 111,518,016 bytes)\n--    \n--    \u03bb> nDescomposiciones4 30\n--    974169\n--    (2.02 secs, 454,484,992 bytes)\n--    \u03bb> nDescomposiciones5 30\n--    974169\n--    (0.00 secs, 0 bytes)\n\n--    \u03bb> nDescomposiciones2 30\n--    974169\n--    (2.10 secs, 441,965,208 bytes)\n--    \u03bb> nDescomposiciones3 30\n--    974169\n--    (0.00 secs, 0 bytes)\n--    \n--    \u03bb> length (show (nDescomposiciones5 (10^5)))\n--    20899\n--    (3.00 secs, 1,050,991,880 bytes)\n<\/pre>\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":[4],"tags":[286,456],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4099"}],"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=4099"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4099\/revisions"}],"predecessor-version":[{"id":4130,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4099\/revisions\/4130"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4099"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4099"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4099"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}