{"id":2449,"date":"2013-01-05T01:51:35","date_gmt":"2013-01-05T01:51:35","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2449"},"modified":"2013-03-16T08:01:04","modified_gmt":"2013-03-16T08:01:04","slug":"la-sucesion-de-perrin-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/la-sucesion-de-perrin-en-haskell\/","title":{"rendered":"La sucesi\u00f3n de Perrin en Haskell"},"content":{"rendered":"<p>Esta relaci\u00f3n de ejercicios est\u00e1 dedicada al estudio de propiedades de la <a href=\"http:\/\/en.wikipedia.org\/wiki\/Perrin_number\">sucesi\u00f3n de Perrin<\/a> Dicha sucesi\u00f3n est\u00e1 definida por la relaci\u00f3n de recurrencia <\/p>\n<blockquote><p>\nP(0) = 3,<br \/>\nP(1) = 0,<br \/>\nP(2) = 2,<br \/>\nP(n) = P(n-2) + P(n-3), para n > 2\n<\/p><\/blockquote>\n<p>La serie comienza por<\/p>\n<blockquote><p>\n3, 0, 2, 3, 2, 5, 5, 7, 10, 12, 17, 22, 29, 39, 51, 68, &#8230;\n<\/p><\/blockquote>\n<p><!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- \u00a7 Librer\u00edas auxiliares                                             --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n \r\n--    perrin :: Integer -> Integer\r\n-- tal que (perrin n) es el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de\r\n-- Perrin. Por ejemplo,  \r\n--    perrin 8                  ==  10\r\n--    [perrin x | x <- [0..9]]  == [3,0,2,3,2,5,5,7,10]\r\n-- ---------------------------------------------------------------------\r\n\r\nperrin :: Integer -> Integer\r\nperrin 0 = 3\r\nperrin 1 = 0\r\nperrin 2 = 2\r\nperrin n = perrin (n-2) + perrin (n-3)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir la funci\u00f3n \r\n--    perrinIter :: Integer -> Integer\r\n-- tal que (perrinIter n) es n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Perrin\r\n-- calculada de manera iterativa usando acumuladores. Por ejemplo, para \r\n-- calcular el t\u00e9rmino octavo,\r\n--    n | a | b | c \r\n--   ---+---+---+----\r\n--    8 | 3 | 0 | 2 \r\n--    7 | 0 | 2 | 3 \r\n--    6 | 2 | 3 | 2 \r\n--    5 | 3 | 2 | 5 \r\n--    4 | 2 | 5 | 5 \r\n--    3 | 5 | 5 | 7 \r\n--    2 | 5 | 7 | 10\r\n--    1 | 7 |10 | 10\r\n--    0 |10 |10 | 17\r\n-- ---------------------------------------------------------------------\r\n\r\nperrinIter :: Integer -> Integer\r\nperrinIter n = perrinIterAux n 3 0 2\r\n\r\nperrinIterAux :: Integer -> Integer -> Integer -> Integer -> Integer\r\nperrinIterAux 0     a b c = a\r\nperrinIterAux (n+1) a b c = perrinIterAux n b c (a+b)\r\n\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Escribir el proceso de c\u00e1lculo de perrinIter \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El procesos es\r\n--    perrinIter 8 =\r\n--    = perrinIterAux 8  3  0  2 \r\n--    = perrinIterAux 7  0  2  3 \r\n--    = perrinIterAux 6  2  3  2 \r\n--    = perrinIterAux 5  3  2  5 \r\n--    = perrinIterAux 4  2  5  5 \r\n--    = perrinIterAux 3  5  5  7 \r\n--    = perrinIterAux 2  5  7 10 \r\n--    = perrinIterAux 1  7 10 10 \r\n--    = perrinIterAux 0 10 10 17 \r\n--    = 10\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Establecer la relaci\u00f3n existente entre perrinIter y\r\n-- perrinIterAux y comprobarla con QuickCheck. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_perrinIterAux i j =\r\n    i >= 0 && j >= 0 ==>\r\n      pIA i (pI j) (pI (j+1)) (pI (j+2)) == pI (j+i)\r\n      where pI  = perrinIter\r\n            pIA = perrinIterAux\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> quickCheck prop_perrinIterAux\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Comprobar que las definiciones perrin y perrinIter\r\n-- coinciden sobre los 20 primeros t\u00e9rminos de la sucesi\u00f3n.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comprobaci\u00f3n es\r\n--    ghci> and [perrin x == perrinIter x | x <- [0..19]]\r\n--    True\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Comparar los costes de calcular (perrin 50) y \r\n-- (perrinIter 50).\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La comparaci\u00f3n es\r\n--    ghci> :set +s\r\n--    ghci> perrin 50\r\n--    1276942\r\n--    (5.80 secs, 203889276 bytes)\r\n--    ghci> perrinIter 50\r\n--    1276942\r\n--    (0.00 secs, 0 bytes)\r\n--    ghci> :unset +s\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir la funci\u00f3n \r\n--    cocientePerrin :: Integer -> Double\r\n-- tal que (cocientePerrin n) es el cociente entre el t\u00e9rmino n-\u00e9simo de\r\n-- la sucesi\u00f3n de Perrin y su t\u00e9rmino anterior, para n >= 3. Por ejemplo,\r\n--    cocientePerrin 5  ==  2.5\r\n--    cocientePerrin 6  ==  1.0\r\n-- ---------------------------------------------------------------------\r\n\r\ncocientePerrin :: Integer -> Double\r\ncocientePerrin n  \r\n    | n >= 3 = (perrin' n)\/(perrin' (n-1))\r\n    where perrin' n = fromIntegral (perrinIter n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8, Calcular el cociente de Perrin para n de 3 a 50.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> [cocientePerrin n | n <- [3..50]]\r\n--    [1.5,               0.6666666666666666, 2.5, \r\n--    1.0,                1.4,                1.4285714285714286, \r\n--    1.2,                1.4166666666666667, 1.2941176470588236, \r\n--    1.3181818181818181, 1.3448275862068966, 1.3076923076923077, \r\n--    1.3333333333333333, 1.3235294117647058, 1.3222222222222222, \r\n--    1.3277310924369747, 1.3227848101265822, 1.325358851674641, \r\n--    1.3249097472924187, 1.32425068119891,   1.3251028806584362, \r\n--    1.3245341614906831, 1.3247362250879249, 1.3247787610619468, \r\n--    1.3246492985971945, 1.32476046394352,   1.3247049866768177,\r\n--    1.3247126436781609, 1.3247288503253796, 1.324709349926314, \r\n--    1.3247218788627935, 1.3247177381729962, 1.3247164893991688, \r\n--    1.3247195193279098, 1.3247170265714057, 1.3247182159738213, \r\n--    1.3247180988540976, 1.3247177043406195, 1.3247181492342783, \r\n--    1.324717874044412,  1.3247179578589308, 1.324717992419995, \r\n--    1.3247179218053005, 1.3247179775532176, 1.3247179521808965,\r\n--    1.3247179535727094, 1.3247179630950467, 1.3247179529740076]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir la funci\u00f3n \r\n--    proximos :: (Num a, Ord a) => [a] -> a -> [a]\r\n-- tal que (proximos xs d) es el primer par de elementos consecutivos de\r\n-- la lista xs tal que el valor absoluto de su diferencia es menor o\r\n-- igual que d. Por ejemplo,\r\n--    proximos :: (Num a, Ord a) => [a] -> a -> [a]\r\n--    proximos [3,5,6,9,10] 1  ==  [5,6]\r\n--    proximos [3,5,4,9,10] 1  ==  [5,4]\r\n--    proximos [3,5,3,9,12] 1  ==  []\r\n-- ---------------------------------------------------------------------\r\n\r\nproximos [] _  = []\r\nproximos [x] _ = []\r\nproximos (x:y:xs) d \r\n    | abs(x-y) <= d = [x,y]\r\n    | otherwise     = proximos (y:xs) d\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Calcular los dos primeros t\u00e9rminos consecutivos de la\r\n-- sucesi\u00f3n de cocientes de Perrin tales que el valor absoluto de su\r\n-- diferencia sea menor que 10^(-32). \u00bfQu\u00e9 se puede decir del l\u00edmite\r\n-- de la sucesi\u00f3n de cocientes? \r\n-- ---------------------------------------------------------------------\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> proximos [cocientePerrin n | n <- [3..]] 1e-32\r\n--    [1.324717957244746,1.324717957244746]\r\n-- Esto indica que el l\u00edmite de la sucesi\u00f3n de cocientes es\r\n-- 1.324717957244746. \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Sea p(n) el n-\u00e9simo t\u00e9rmino de la sucesi\u00f3n de Perrin y\r\n-- q(n)=p(n)\/p(n-1) (para n >= 3). Demostrar que el l\u00edmite de q(n) es\r\n-- una ra\u00edz de la ecuaci\u00f3n x^3-x-1=0.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Por definici\u00f3n de la sucesi\u00f3n de Perrin, se tiene que\r\n--    P(n) = P(n-2)+P(n-3).\r\n-- Por tanto,\r\n--    P(n)\/P(n-1)} \r\n--    = P(n-2)\/P(n-1)} + P(n-3)\/P(n-2) * P(n-2)\/P(n-1)\r\n--    = P(n-2)\/P(n-1)} + 1\/(P(n-3)\/P(n-2)) * 1\/(P(n-2)\/P(n-1))\r\n-- Sea x el l\u00edmite de Q(n). Entonces\r\n--    x = 1\/x + 1\/x^2\r\n-- Por tanto,\r\n--    x^3 = x+1\r\n-- y x es una ra\u00edz de x^3-x-1 = 0.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Las ra\u00edces de una ecuaci\u00f3n pueden aproximarse por el\r\n-- m\u00e9todo de bisecci\u00f3n que se basa en el siguiente teorema: \r\n--    [Teorema del valor medio] Sea f una funci\u00f3n continua en un\r\n--    intervalo [a,b] y supongamos que f(a) y f(b) tienen signos\r\n--    opuestos. Entonces para cada y entre f(a) y f(b), existe un x en\r\n--    [a,b] tal que f(x)=y. \r\n-- El m\u00e9todo de bisecci\u00f3n consiste en calcular el punto medio del\r\n-- intervalo: m=(a+b)\/2. Se consideran tres casos:\r\n-- * si |f(m)| < 10^{-9}, entonces m es una ra\u00edz de f(x)=0,\r\n-- * si f(m) tiene el mismo signo que f(a) se repite el procedimiento en \r\n--   el intervalo [m,b],\r\n-- * en otro caso, se repite el procedimiento en el intervalo [a,m].\r\n-- \r\n-- Definir la funci\u00f3n \r\n--    biseccion :: (Double -> Double) -> Double -> Double -> Double\r\n-- tal que (biseccion f a b) es la ra\u00edz de f en el intervalo [a,b]\r\n-- calculada por el m\u00e9todo de bisecci\u00f3n. Por ejemplo, \r\n--    biseccion (\\x -> x^2-9) 2 5  ==>  3.0000000001164153\r\n-- ---------------------------------------------------------------------\r\n\r\nbiseccion :: (Double -> Double) -> Double -> Double -> Double\r\nbiseccion f a b \r\n    | abs (f m) < 1e-9             = m\r\n    | signum (f m) == signum (f a) = biseccion f m b\r\n    | otherwise                    = biseccion f a m \r\n    where m = (a+b)\/2\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Calcular por el m\u00e9todo de bisecci\u00f3n la soluci\u00f3n de\r\n-- x^3-x-1=0 en el intervalo [1,2] y compararla con el l\u00edmite de la\r\n-- sucesi\u00f3n de cocientes de Perrin. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La soluci\u00f3n se calcula por\r\n--    ghci> biseccion (\\x -> x^3-x-1) 1 2\r\n--    1.324717957060784\r\n-- Se observa que coincide con el l\u00edmite de la sucesi\u00f3n de cocientes de Perrin.\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Esta relaci\u00f3n de ejercicios est\u00e1 dedicada al estudio de propiedades de la sucesi\u00f3n de Perrin Dicha sucesi\u00f3n est\u00e1 definida por la relaci\u00f3n de recurrencia P(0) = 3, P(1) = 0, P(2) = 2, P(n) = P(n-2) + P(n-3), para n > 2 La serie comienza por 3, 0, 2, 3, 2, 5, 5, 7, 10,&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","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":[1],"tags":[27,270,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\/2449"}],"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=2449"}],"version-history":[{"count":5,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2449\/revisions"}],"predecessor-version":[{"id":3130,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2449\/revisions\/3130"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2449"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2449"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2449"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}