{"id":3843,"date":"2013-11-22T18:24:48","date_gmt":"2013-11-22T17:24:48","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3843"},"modified":"2013-11-24T08:26:05","modified_gmt":"2013-11-24T07:26:05","slug":"i1m2013-ejercicios-de-definiciones-por-recursion","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-ejercicios-de-definiciones-por-recursion\/","title":{"rendered":"I1M2013: Ejercicios de definiciones por recursi\u00f3n"},"content":{"rendered":"<p>En la clase de hoy del curso <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-13\">Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas)<\/a> se han comentado las soluciones de los ejercicios de la 7\u00aa relaci\u00f3n y los 3 primeros de la 8\u00aa sobre definiciones por recursi\u00f3n<\/p>\n<p>Los ejercicios y sus soluciones se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\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-13\/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\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. Definir por recursi\u00f3n la funci\u00f3n\r\n--    elem' :: Eq a => a -> [a] -> Bool\r\n-- tal que (elem' x xs) se verifica si x pertenece a la lista xs. Por\r\n-- ejemplo, \r\n--    elem' 3 [2,3,5]  ==  True\r\n--    elem' 4 [2,3,5]  ==  False\r\n-- ---------------------------------------------------------------------\r\n\r\nelem' :: Eq a => a -> [a] -> Bool\r\nelem' x []                 = False\r\nelem' x (y:ys) | x == y    = True\r\n               | otherwise = elem' x ys\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 9. Definir por recursi\u00f3n la funci\u00f3n\r\n--    last' :: [a] -> a\r\n-- tal que (last xs) es el \u00faltimo elemento de xs. Por ejemplo,\r\n--    last' [2,3,5]  =>  5\r\n-- ---------------------------------------------------------------------\r\n\r\nlast' :: [a] -> a\r\nlast' [x]    = x\r\nlast' (_:xs) = last' xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 10. Definir por recursi\u00f3n la funci\u00f3n\r\n--    concat' :: [[a]] -> [a]\r\n-- tal que (concat' xss) es la lista obtenida concatenando las listas de\r\n-- xss. Por ejemplo,\r\n--    concat' [[1..3],[5..7],[8..10]]  ==  [1,2,3,5,6,7,8,9,10]\r\n-- ---------------------------------------------------------------------\r\n \r\nconcat' :: [[a]] -> [a]\r\nconcat' []       = []\r\nconcat' (xs:xss) = xs ++ concat' xss\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 11. Definir por recursi\u00f3n la funci\u00f3n\r\n--    selecciona :: [a] -> Int -> a\r\n-- tal que (selecciona xs n) es el n-\u00e9simo elemento de xs. Por ejemplo,\r\n--    selecciona [2,3,5,7] 2  ==  5 \r\n-- ---------------------------------------------------------------------\r\n\r\nselecciona :: [a] -> Int -> a\r\nselecciona (x:_)  0 = x\r\nselecciona (_:xs) n = selecciona xs (n-1)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 12. Definir por recursi\u00f3n la funci\u00f3n\r\n--    take' :: Int -> [a] -> [a]\r\n-- tal que (take' n xs) es la lista de los n primeros elementos de\r\n-- xs. Por ejemplo, \r\n--    take' 3 [4..12]  =>  [4,5,6]\r\n-- ---------------------------------------------------------------------\r\n\r\ntake' :: Int -> [a] -> [a]\r\ntake' 0 _      = []\r\ntake' n []     = []\r\ntake' n (x:xs) = x : take' (n-1) xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 13. Definir la funci\u00f3n\r\n--    refinada :: [Float] -> [Float]\r\n-- tal que (refinada xs) es la lista obtenida intercalando entre cada\r\n-- dos elementos consecutivos de xs su media aritm\u00e9tica. Por ejemplo,\r\n--    refinada [2,7,1,8]  ==  [2.0,4.5,7.0,4.0,1.0,4.5,8.0]\r\n--    refinada [2]        ==  [2.0]\r\n--    refinada []         ==  []\r\n-- ---------------------------------------------------------------------\r\n\r\nrefinada :: [Float] -> [Float]\r\nrefinada (x:y:zs) = x : (x+y)\/2 : refinada (y:zs)\r\nrefinada xs       = xs\r\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-13\/temas\/tema-6.pdf\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1. Definir la funci\u00f3n\r\n--    duplicaPrimo :: [Int] -> [Int]\r\n-- tal que (duplicaPrimo xs) es la lista obtenida sustituyendo cada\r\n-- n\u00famero primo de xs por su doble. Por ejemplo,\r\n--    duplicaPrimo [2,5,9,7,1,3]  ==  [4,10,9,14,1,6]\r\n-- --------------------------------------------------------------------- \r\n\r\nduplicaPrimo :: [Int] -> [Int]\r\nduplicaPrimo []     = []\r\nduplicaPrimo (x:xs) | primo x   = (2*x) : duplicaPrimo xs\r\n                    | otherwise = x : duplicaPrimo xs\r\n\r\n-- (primo x) se verifica si x es primo. Por ejemplo,\r\n--    primo 7  ==  True\r\n--    primo 8  ==  False\r\nprimo :: Int -> Bool\r\nprimo x = divisores x == [1,x]\r\n\r\n-- (divisores x) es la lista de los divisores de x. Por ejemplo,\r\n--    divisores 30  ==  [1,2,3,5,6,10,15,30]\r\ndivisores :: Int -> [Int]\r\ndivisores x = [y | y <- [1..x], rem x y == 0]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2. Definir, por recursi\u00f3n, el predicado\r\n--    alMenos :: Int -> [Int] -> Bool \r\n-- tal que (alMenos k xs) se verifica si xs contiene, al menos, k\r\n-- n\u00fameros primos. Por ejemplo, \r\n--    alMenos 1 [1,3,7,10,14] == True\r\n--    alMenos 3 [1,3,7,10,14] == False\r\n-- ---------------------------------------------------------------------\r\n\r\nalMenos :: Int -> [Int] -> Bool \r\nalMenos 0 _  = True\r\nalMenos _ [] = False\r\nalMenos k (x:xs) | primo x   = alMenos (k-1) xs\r\n                  | otherwise = alMenos k xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    ceros :: Int -> Int \r\n-- tal que (ceros n) es el n\u00famero de ceros en los que termina el n\u00famero\r\n-- n. Por ejemplo, \r\n--    ceros 3020000  ==  4\r\n-- ---------------------------------------------------------------------\r\n\r\nceros :: Int -> Int \r\nceros n | rem n 10 \/= 0 = 0\r\n        | otherwise     = 1 + ceros (div n 10)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la clase de hoy del curso Inform\u00e1tica (de 1\u00ba de Grado en Matem\u00e1ticas) se han comentado las soluciones de los ejercicios de la 7\u00aa relaci\u00f3n y los 3 primeros de la 8\u00aa 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":"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":[222],"tags":[270,300],"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\/3843"}],"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=3843"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3843\/revisions"}],"predecessor-version":[{"id":3844,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3843\/revisions\/3844"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3843"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3843"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3843"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}