En las Olimpiadas de Matem\u00e1ticas del 2001<\/a> se propuso el siguiente problema<\/p>\n
\nBuscar todas las sucesiones finitas (x(0), x(1),…,x(n)) tales que para todo j, 0 \u2264 j \u2264 n, x(j) es igual al n\u00famero de veces que aparece j en la sucesi\u00f3n.\n<\/p><\/blockquote>\n
Las sucesiones que cumplen la anterior condici\u00f3n se llaman auto descriptivas. Un ejemplo de sucesi\u00f3n auto descriptiva es [5,2,1,0,0,1,0,0,0] ya que <\/p>\n
\n
- el 0 aparece 5 veces,\n
- el 1 aparece 2 veces,\n
- el 2 aparece 1 vez,\n
- el 3 aparece 0 veces,\n
- el 4 aparece 0 veces,\n
- el 5 aparece 1 vez,\n
- el 6 aparece 0 veces,\n
- el 7 aparece 0 veces y\n
- el 8 aparece 0 veces.\n<\/ul>\n
En la siguiente relaci\u00f3n de ejercicios, elaborada para la asignatura de Inform\u00e1tica (de 1\u00ba del Grado en Matem\u00e1ticas)<\/a> y para la siguiente versi\u00f3n del libro Piensa en Haskell<\/a>, se resuelve el problema con Haskell.
\n <\/p>\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Librer\u00edas auxiliares --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Data.List\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Ejercicios --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n-- ocurrencias :: Eq a => a -> [a] -> Int\r\n-- tal que (ocurrencias x ys) es el n\u00famero de veces que x ocurre en\r\n-- ys. Por ejemplo,\r\n-- ocurrencias 2 [3,2,5,2,2,7] == 3\r\n-- ---------------------------------------------------------------------\r\n\r\nocurrencias :: Eq a => a -> [a] -> Int\r\nocurrencias x ys = length [y | y <- ys, y == x]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n\r\n-- esAutoDescriptiva:: [Int] -> Bool\r\n-- tal que (esAutoDescriptiva xs) se verifica si la sucesi\u00f3n xs es auto\r\n-- descriptiva. Por ejemplo,\r\n-- esAutoDescriptiva [5,2,1,0,0,1,0,0,0] == True\r\n-- esAutoDescriptiva [6,2,1,0,0,1,0,0,0] == False\r\n-- ---------------------------------------------------------------------\r\n\r\nesAutoDescriptiva:: [Int] -> Bool\r\nesAutoDescriptiva xs = \r\n and [xs!!j == ocurrencias j xs | j <- [0..length xs - 1]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir la funci\u00f3n\r\n-- variacionesR :: Int -> [a] -> [[a]]\r\n-- tal que (variacionesR k xs) es la lista de las variaciones de orden k\r\n-- de los elementos de xs con repeticiones. Por ejemplo, \r\n-- ghci> variacionesR 1 \"ab\"\r\n-- [\"a\",\"b\"]\r\n-- ghci> variacionesR 2 \"ab\"\r\n-- [\"aa\",\"ab\",\"ba\",\"bb\"]\r\n-- ghci> variacionesR 3 \"ab\"\r\n-- [\"aaa\",\"aab\",\"aba\",\"abb\",\"baa\",\"bab\",\"bba\",\"bbb\"]\r\n-- ---------------------------------------------------------------------\r\n\r\nvariacionesR :: Int -> [a] -> [[a]]\r\nvariacionesR _ [] = []\r\nvariacionesR 0 _ = [[]] \r\nvariacionesR k xs = [z:ys | z <- xs, ys <- variacionesR (k-1) xs]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir la funci\u00f3n\r\n-- autoDescriptivas1 :: Int -> [Int] -> [[Int]]\r\n-- tal que (autoDescriptivas1 n xs) es la listas de las sucesiones\r\n-- auto descriptivas de longitud n y valores en xs. Por ejemplo,\r\n-- autoDescriptivas1 4 [0..3] == [[1,2,1,0],[2,0,2,0]]\r\n-- ---------------------------------------------------------------------\r\n\r\nautoDescriptivas1 :: Int -> [Int] -> [[Int]]\r\nautoDescriptivas1 n xs = \r\n [ys | ys <- variacionesR n xs, esAutoDescriptiva ys]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Calcular el valor de (autoDescriptivas1 n [0..6]) para n\r\n-- de 0 a 9.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El resultado del c\u00e1lculo es\r\n-- autoDescriptivas1 0 [0..6] == [[]]\r\n-- autoDescriptivas1 1 [0..6] == []\r\n-- autoDescriptivas1 2 [0..6] == []\r\n-- autoDescriptivas1 3 [0..6] == []\r\n-- autoDescriptivas1 4 [0..6] == [[1,2,1,0],[2,0,2,0]]\r\n-- autoDescriptivas1 5 [0..6] == [[2,1,2,0,0]]\r\n-- autoDescriptivas1 6 [0..6] == []\r\n-- autoDescriptivas1 7 [0..6] == [[3,2,1,1,0,0,0]]\r\n-- autoDescriptivas1 7 [0..6] == [[3,2,1,1,0,0,0]]\r\n-- autoDescriptivas1 8 [0..6] == [[4,2,1,0,1,0,0,0]]\r\n-- autoDescriptivas1 8 [0..6] == [[4,2,1,0,1,0,0,0]]\r\n-- autoDescriptivas1 9 [0..6] == [[5,2,1,0,0,1,0,0,0]]\r\n-- autoDescriptivas1 9 [0..6] == [[5,2,1,0,0,1,0,0,0]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. \u00bfQu\u00e9 relaci\u00f3n hay entre la longitud de las sucesiones\r\n-- auto descriptivas y la suma de sus elementos?\r\n-- ---------------------------------------------------------------------\r\n\r\n-- En en ejercicio anterior se observa que si xs es una sucesi\u00f3n auto\r\n-- descriptiva, entonces la suma de los elementos de xs es igual a la\r\n-- longitud de xs. \r\n-- \r\n-- La demostraci\u00f3n de la propiedad es trivial.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n\r\n-- sucLongSum :: Int -> Int -> [[Int]]\r\n-- tal que (sucLongSum m n) es la lista de las sucesiones de longitud m\r\n-- cuyos elementos suman n. Por ejemplo,\r\n-- sucLongSum 2 3 == [[0,3],[1,2],[2,1],[3,0]]\r\n-- sucLongSum 3 2 == [[0,0,2],[0,1,1],[0,2,0],[1,0,1],[1,1,0],[2,0,0]]\r\n-- ---------------------------------------------------------------------\r\n\r\nsucLongSum :: Int -> Int -> [[Int]]\r\nsucLongSum 0 0 = [[]]\r\nsucLongSum 0 n = []\r\nsucLongSum 1 n = [[n]]\r\nsucLongSum m n = [x:ys | x <- [0..n], ys <- sucLongSum (m-1) (n-x)]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir, usando los ejercicios 7 y 8, la funci\u00f3n\r\n-- autoDescriptivas2 :: Int -> [[Int]]\r\n-- tal que (autoDescriptivas2 n) es la listas de las sucesiones\r\n-- auto descriptivas de longitud n. Por ejemplo,\r\n-- autoDescriptivas2 4 == [[1,2,1,0],[2,0,2,0]]\r\n-- ---------------------------------------------------------------------\r\n\r\nautoDescriptivas2 :: Int -> [[Int]]\r\nautoDescriptivas2 n = \r\n [ys | ys <- sucLongSum n n, esAutoDescriptiva ys]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9: Calcular (autoDescriptivas2 n) para n entre 0 y 1.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El resultado del c\u00e1lculo es\r\n-- autoDescriptivas2 0 == [[]]\r\n-- autoDescriptivas2 1 == []\r\n-- autoDescriptivas2 2 == []\r\n-- autoDescriptivas2 3 == []\r\n-- autoDescriptivas2 4 == [[1,2,1,0],[2,0,2,0]]\r\n-- autoDescriptivas2 5 == [[2,1,2,0,0]]\r\n-- autoDescriptivas2 6 == []\r\n-- autoDescriptivas2 7 == [[3,2,1,1,0,0,0]]\r\n-- autoDescriptivas2 8 == [[4,2,1,0,1,0,0,0]]\r\n-- autoDescriptivas2 9 == [[5,2,1,0,0,1,0,0,0]]\r\n-- autoDescriptivas2 10 == [[6,2,1,0,0,0,1,0,0,0]]\r\n-- autoDescriptivas2 11 == [[7,2,1,0,0,0,0,1,0,0,0]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir, usando el ejercicios 9, la funci\u00f3n\r\n-- autoDescriptivas3 :: Int -> [[Int]]\r\n-- tal que (autoDescriptivas3 n) es la listas de las sucesiones\r\n-- auto descriptivas de longitud n. Por ejemplo,\r\n-- autoDescriptivas3 4 == [[1,2,1,0],[2,0,2,0]]\r\n-- autoDescriptivas3 15 == [[11,2,1,0,0,0,0,0,0,0,0,1,0,0,0]]\r\n-- autoDescriptivas3 16 == [[12,2,1,0,0,0,0,0,0,0,0,0,1,0,0,0]]\r\n-- ---------------------------------------------------------------------\r\n\r\nautoDescriptivas3 :: Int -> [[Int]]\r\nautoDescriptivas3 n \r\n | n == 0 = [[]]\r\n | n <= 3 = []\r\n | n == 4 = [[1,2,1,0],[2,0,2,0]]\r\n | n == 5 = [[2,1,2,0,0]]\r\n | n == 6 = []\r\n | otherwise = [[n-4,2,1] ++ replicate (n-7) 0 ++ [1,0,0,0]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir la funci\u00f3n\r\n-- autoDescriptivas3Correcta1 :: Int -> Bool\r\n-- tal que (autoDescriptivas3Correcta1 n) se verifica si todas las\r\n-- sucesiones de (autoDescriptivas3 n) son auto descriptivas. Por\r\n-- ejemplo, \r\n-- autoDescriptivas3Correcta1 100 == True\r\n-- ---------------------------------------------------------------------\r\n\r\nautoDescriptivas3Correcta1 :: Int -> Bool\r\nautoDescriptivas3Correcta1 n =\r\n all esAutoDescriptiva (autoDescriptivas3 n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Comprobar que las listas calculadas por \r\n-- (autoDescriptivas3 n), para n entre 0 y 300, son auto descriptivas.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n-- ghci> all autoDescriptivas3Correcta1 [0..300]\r\n-- True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Comprobar con QuickCheck que una lista de n\u00fameros\r\n-- naturales xs es auto descriptiva si, y s\u00f3lo si, xs pertenece a\r\n-- (autoDescriptivas3 n) donde n es la longitud de xs.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nautoDescriptivas3Correcta2 :: [Int] -> Bool\r\nautoDescriptivas3Correcta2 xs =\r\n esAutoDescriptiva xs' == elem xs' (autoDescriptivas3 n)\r\n where xs' = map abs xs\r\n n = length xs\r\n\r\n-- La comprobaci\u00f3n es\r\n-- ghci> quickCheck autoDescriptivas3Correcta2\r\n-- +++ OK, passed 100 tests.\r\n<\/pre>\nEn el \u00faltimo ejercicio s\u00f3lo se ha hecho una comprobaci\u00f3n, para completar el problema queda pendiente demostrar formalmente la propiedad.<\/p>\n","protected":false},"excerpt":{"rendered":"
En las Olimpiadas de Matem\u00e1ticas del 2001 se propuso el siguiente problema Buscar todas las sucesiones finitas (x(0), x(1),…,x(n)) tales que para todo j, 0 \u2264 j \u2264 n, x(j) es igual al n\u00famero de veces que aparece j en la sucesi\u00f3n. Las sucesiones que cumplen la anterior condici\u00f3n se llaman auto descriptivas. Un ejemplo…<\/p>\n","protected":false},"author":2,"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":[5,221],"tags":[270,279,200,299,126],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3672"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=3672"}],"version-history":[{"count":4,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3672\/revisions"}],"predecessor-version":[{"id":3676,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3672\/revisions\/3676"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3672"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3672"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3672"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}