Definir la funci\u00f3n<\/p>\n
\n descomposiciones :: Int -> [[Int]]\n<\/pre>\ntal que (descomposiciones x) es la lista de las listas de los cuadrados de cuatro n\u00fameros enteros positivos cuya suma es x. Por ejemplo.<\/p>\n
\n \u03bb> descomposiciones 4\n [[1,1,1,1]]\n \u03bb> descomposiciones 5\n []\n \u03bb> descomposiciones 7\n [[1,1,1,4],[1,1,4,1],[1,4,1,1],[4,1,1,1]]\n \u03bb> descomposiciones 10\n [[1,1,4,4],[1,4,1,4],[1,4,4,1],[4,1,1,4],[4,1,4,1],[4,4,1,1]]\n \u03bb> descomposiciones 15\n [[1,1,4,9],[1,1,9,4],[1,4,1,9],[1,4,9,1],[1,9,1,4],[1,9,4,1],\n [4,1,1,9],[4,1,9,1],[4,9,1,1],[9,1,1,4],[9,1,4,1],[9,4,1,1]]\n \u03bb> length (descomposiciones 50000)\n 5682\n<\/pre>\nSoluciones<\/h4>\n\nimport Data.Array\nimport Test.QuickCheck\n\n-- 1\u00aa definici\u00f3n\n-- =============\n\ndescomposiciones :: Int -> [[Int]]\ndescomposiciones x = aux x 4\n where \n aux 0 1 = []\n aux 1 1 = [[1]]\n aux 2 1 = []\n aux 3 1 = []\n aux y 1 | esCuadrado y = [[y]]\n | otherwise = []\n aux y n = [x^2 : zs | x <- [1..raizEntera y]\n , zs <- aux (y - x^2) (n-1)]\n\n-- (esCuadrado x) se verifica si x es un n\u00famero al cuadrado. Por\n-- ejemplo,\n-- esCuadrado 25 == True\n-- esCuadrado 26 == False\nesCuadrado :: Int -> Bool\nesCuadrado x = (raizEntera x)^2 == x\n\n-- (raizEntera n) es el mayor entero cuya ra\u00edz cuadrada es menor o igual\n-- que n. Por ejemplo,\n-- raizEntera 15 == 3\n-- raizEntera 16 == 4\n-- raizEntera 17 == 4\nraizEntera :: Int -> Int\nraizEntera = floor . sqrt . fromIntegral \n\n-- 2\u00aa definici\u00f3n\n-- =============\n\ndescomposiciones2 :: Int -> [[Int]]\ndescomposiciones2 x = a ! (x,4)\n where\n a = array ((0,1),(x,4)) [((i,j), f i j) | i <- [0..x], j <- [1..4]]\n f 0 1 = []\n f 1 1 = [[1]]\n f 2 1 = []\n f 3 1 = []\n f i 1 | esCuadrado i = [[i]]\n | otherwise = []\n f i j = [x^2 : zs | x <- [1..raizEntera i]\n , zs <- a ! (i - x^2,j-1)]\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_descomposiciones :: Positive Int -> Bool\nprop_descomposiciones (Positive x) =\n descomposiciones x == descomposiciones2 x\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_descomposiciones\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> length (descomposiciones (2*10^4))\n-- 1068\n-- (3.70 secs, 3,307,251,704 bytes)\n-- \u03bb> length (descomposiciones2 (2*10^4))\n-- 1068\n-- (0.72 secs, 678,416,144 bytes)\n<\/pre>\nPensamiento<\/h4>\n\nNo extra\u00f1\u00e9is, dulces amigos,
\nque est\u00e9 mi frente arrugada;
\nyo vivo en paz con los hombres
\ny en guerra con mis entra\u00f1as.<\/p>\n
Antonio Machado\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"
Definir la funci\u00f3n descomposiciones :: Int -> [[Int]] tal que (descomposiciones x) es la lista de las listas de los cuadrados de cuatro n\u00fameros enteros positivos cuya suma es x. Por ejemplo. \u03bb> descomposiciones 4 [[1,1,1,1]] \u03bb> descomposiciones 5 [] \u03bb> descomposiciones 7 [[1,1,1,4],[1,1,4,1],[1,4,1,1],[4,1,1,1]] \u03bb> descomposiciones 10 [[1,1,4,4],[1,4,1,4],[1,4,4,1],[4,1,1,4],[4,1,4,1],[4,4,1,1]] \u03bb> descomposiciones 15 [[1,1,4,9],[1,1,9,4],[1,4,1,9],[1,4,9,1],[1,9,1,4],[1,9,4,1], [4,1,1,9],[4,1,9,1],[4,9,1,1],[9,1,1,4],[9,1,4,1],[9,4,1,1]] \u03bb> length…<\/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":[7],"tags":[250,8,286,282,183,6,236],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4771"}],"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=4771"}],"version-history":[{"count":2,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4771\/revisions"}],"predecessor-version":[{"id":4802,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/4771\/revisions\/4802"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=4771"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=4771"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=4771"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}