{"id":2344,"date":"2012-11-22T12:09:59","date_gmt":"2012-11-22T12:09:59","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=2344"},"modified":"2013-03-08T05:47:38","modified_gmt":"2013-03-08T05:47:38","slug":"i1m2012-ejercicios-de-definiciones-por-recursion-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2012-ejercicios-de-definiciones-por-recursion-en-haskell\/","title":{"rendered":"I1M2012: Ejercicios de definiciones por recursi\u00f3n en Haskell"},"content":{"rendered":"

En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> hemos comentado las soluciones a los 7 primeros ejercicios de la 7\u00aa relaci\u00f3n<\/a>, que tratan sobre definiciones por recursi\u00f3n.<\/p>\n

Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n:
\n<\/p>\n

\r\n-- ---------------------------------------------------------------------\r\n-- Introducci\u00f3n                                                       --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- En esta relaci\u00f3n se presentan ejercicios con definiciones por\r\n-- recursi\u00f3n correspondientes al tema 6 cuyas transparencias se \r\n-- encuentran en  \r\n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-12\/temas\/tema-6.pdf\r\n \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir por recursi\u00f3n la funci\u00f3n\r\n--    potencia :: Integer -> Integer -> Integer\r\n-- tal que (potencia x n) es x elevado al n\u00famero natural n. Por ejemplo,  \r\n--    potencia 2 3  ==  8\r\n-- ---------------------------------------------------------------------\r\n\r\npotencia :: Integer -> Integer -> Integer\r\npotencia m 0 = 1\r\npotencia m n = m*(potencia m (n-1))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir por recursi\u00f3n la funci\u00f3n\r\n--    replicate' :: Int -> a -> [a]\r\n-- tal que (replicate' n x) es la lista formado por n copias del\r\n-- elemento x. Por ejemplo,\r\n--    replicate' 3 2  ==  [2,2,2]\r\n-- ---------------------------------------------------------------------\r\n \r\nreplicate' :: Int -> a -> [a]\r\nreplicate' 0 _     = []\r\nreplicate' n x = x : replicate' (n-1) x\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. El doble factorial de un n\u00famero n se define por \r\n--    n!! = n*(n-2)* ... * 3 * 1, si n es impar\r\n--    n!! = n*(n-2)* ... * 4 * 2, si n es par\r\n--    1!! = 1\r\n--    0!! = 1    \r\n-- Por ejemplo,\r\n--    8!! = 8*6*4*2   = 384\r\n--    9!! = 9*7*5*3*1 = 945\r\n-- Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    dobleFactorial :: Integer -> Integer\r\n-- tal que (dobleFactorial n) es el doble factorial de n. Por ejemplo,\r\n--    dobleFactorial 8  ==  384\r\n--    dobleFactorial 9  ==  945\r\n-- ---------------------------------------------------------------------\r\n\r\ndobleFactorial :: Integer -> Integer\r\ndobleFactorial 0 = 1\r\ndobleFactorial 1 = 1\r\ndobleFactorial n = n * dobleFactorial (n-2)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Dados dos n\u00fameros naturales, a y b, es posible\r\n-- calcular su m\u00e1ximo com\u00fan divisor mediante el Algoritmo de\r\n-- Euclides. Este algoritmo se puede resumir en la siguiente f\u00f3rmula:\r\n--    mcd(a,b) = a,                   si b = 0\r\n--             = mcd (b, a m\u00f3dulo b), si b > 0\r\n-- \r\n-- Definir la funci\u00f3n \r\n--    mcd :: Integer -> Integer -> Integer\r\n-- tal que (mcd a b) es el m\u00e1ximo com\u00fan divisor de a y b calculado\r\n-- mediante el algoritmo de Euclides. Por ejemplo,\r\n--    mcd 30 45  ==  15\r\n-- ---------------------------------------------------------------------\r\n\r\nmcd :: Integer -> Integer -> Integer\r\nmcd a 0 = a\r\nmcd a b = mcd b (a `mod` b)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. (Problema 5 del proyecto Euler) El problema se encuentra\r\n-- en http:\/\/goo.gl\/L5bb y consiste en calcular el menor n\u00famero\r\n-- divisible por los n\u00fameros del 1 al 20. Lo resolveremos mediante los\r\n-- distintos apartados de este ejercicio. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.1. Definir por recursi\u00f3n la funci\u00f3n\r\n--    menorDivisible :: Integer -> Integer -> Integer\r\n-- tal que (menorDivisible a b) es el menor n\u00famero divisible por los\r\n-- n\u00fameros del a al b. Por ejemplo,\r\n--    menorDivisible 2 5  ==  60\r\n-- Indicaci\u00f3n: Usar la funci\u00f3n lcm tal que (lcm x y) es el m\u00ednimo com\u00fan\r\n-- m\u00faltiplo de x e y.\r\n-- ---------------------------------------------------------------------\r\n\r\nmenorDivisible :: Integer -> Integer -> Integer\r\nmenorDivisible  a b  \r\n    | a == b    = a\r\n    | otherwise = lcm a (menorDivisible (a+1) b)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.2. Definir la constante\r\n--    euler5 :: Integer\r\n-- tal que euler5 es el menor n\u00famero divisible por los n\u00fameros del 1 al\r\n-- 20 y calcular su valor.\r\n-- ---------------------------------------------------------------------\r\n\r\neuler5 :: Integer\r\neuler5 = menorDivisible 1 20\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> euler5\r\n--    232792560\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. En un templo hind\u00fa se encuentran tres varillas de\r\n-- platino. En una de ellas, hay 64 anillos de oro de distintos radios,\r\n-- colocados de mayor a menor.\r\n-- \r\n-- El trabajo de los monjes de ese templo consiste en pasarlos todos a\r\n-- la tercera varilla, usando la segunda como varilla auxiliar, con las\r\n-- siguientes condiciones: \r\n--   * En cada paso s\u00f3lo se puede mover un anillo.\r\n--   * Nunca puede haber un anillo de mayor di\u00e1metro encima de uno de\r\n--     menor di\u00e1metro.\r\n-- La leyenda dice que cuando todos los anillos se encuentren en la\r\n-- tercera varilla, ser\u00e1 el fin del mundo.  \r\n-- \r\n-- Definir la funci\u00f3n \r\n--    numPasosHanoi :: Integer -> Integer\r\n-- tal que (numPasosHanoi n) es el n\u00famero de pasos necesarios para\r\n-- trasladar n anillos. Por ejemplo, \r\n--    numPasosHanoi 2   ==  3\r\n--    numPasosHanoi 7   ==  127\r\n--    numPasosHanoi 64  ==  18446744073709551615\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Sean A, B y C las tres varillas. La estrategia recursiva es la\r\n-- siguiente: \r\n-- * Caso base (N=1): Se mueve el disco de A a C.\r\n-- * Caso inductivo (N=M+1): Se mueven M discos de A a C. Se mueve el disco\r\n--   de A a B. Se mueven M discos de C a B.\r\n-- Por tanto,\r\n\r\nnumPasosHanoi :: Integer -> Integer\r\nnumPasosHanoi 1 = 1\r\nnumPasosHanoi n = 1 + 2 * numPasosHanoi (n-1)  \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir por recursi\u00f3n la funci\u00f3n\r\n--    and' :: [Bool] -> Bool\r\n-- tal que (and' xs) se verifica si todos los elementos de xs son\r\n-- verdadero. Por ejemplo,\r\n--    and' [1+2 < 4, 2:[3] == [2,3]]  ==  True\r\n--    and' [1+2 < 3, 2:[3] == [2,3]]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nand' :: [Bool] -> Bool\r\nand' []     = True\r\nand' (b:bs) = b && and' bs\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
En la clase de hoy de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas hemos comentado las soluciones a los 7 primeros ejercicios de la 7\u00aa relaci\u00f3n, que tratan sobre definiciones por recursi\u00f3n. Los ejercicios, y sus soluciones, se muestran a continuaci\u00f3n:<\/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":[298],"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\/2344"}],"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=2344"}],"version-history":[{"count":7,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2344\/revisions"}],"predecessor-version":[{"id":2742,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/2344\/revisions\/2742"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=2344"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=2344"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=2344"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}