{"id":6807,"date":"2019-10-25T20:21:36","date_gmt":"2019-10-25T18:21:36","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=6807"},"modified":"2019-10-25T20:21:36","modified_gmt":"2019-10-25T18:21:36","slug":"i1m2019-ejercicios-de-definiciones-por-recursion","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2019-ejercicios-de-definiciones-por-recursion\/","title":{"rendered":"I1M2019: Ejercicios de definiciones por recursi\u00f3n"},"content":{"rendered":"<p>En la primera parte de la clase de hoy del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-19\">Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas<\/a> se han comentado las soluciones de los ejercicios de la 4\u00aa relaci\u00f3n sobre definiciones por recursi\u00f3n.<\/p>\n<p>Los ejercicios y su soluci\u00f3n se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\n-- ---------------------------------------------------------------------\n-- Introducci\u00f3n                                                       --\n-- ---------------------------------------------------------------------\n\n-- En esta relaci\u00f3n se presentan ejercicios con definiciones por\n-- recursi\u00f3n correspondientes al tema 6 cuyas transparencias se \n-- encuentran en  \n--    http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m-19\/temas\/tema-6.html\n \n-- ---------------------------------------------------------------------\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\n-- ---------------------------------------------------------------------\n\nimport Test.QuickCheck\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.1. Definir por recursi\u00f3n la funci\u00f3n\n--    potencia :: Integer -> Integer -> Integer\n-- tal que (potencia x n) es x elevado al n\u00famero natural n. Por ejemplo,  \n--    potencia 2 3  ==  8\n-- ---------------------------------------------------------------------\n\npotencia :: Integer -> Integer -> Integer\npotencia _ 0 = 1\npotencia m n = m * potencia m (n-1)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 1.2. Comprobar con QuickCheck que la funci\u00f3n potencia es\n-- equivalente a la predefinida (^).\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_potencia :: Integer -> Integer -> Property\nprop_potencia x n = \n  n >= 0 ==> potencia x n == x^n\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_potencia\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.1. Dados dos n\u00fameros naturales, a y b, es posible\n-- calcular su m\u00e1ximo com\u00fan divisor mediante el Algoritmo de\n-- Euclides. Este algoritmo se puede resumir en la siguiente f\u00f3rmula:\n--    mcd(a,b) = a,                   si b = 0\n--             = mcd (b, a m\u00f3dulo b), si b > 0\n-- \n-- Definir la funci\u00f3n \n--    mcd :: Integer -> Integer -> Integer\n-- tal que (mcd a b) es el m\u00e1ximo com\u00fan divisor de a y b calculado\n-- mediante el algoritmo de Euclides. Por ejemplo,\n--    mcd 30 45  ==  15\n-- ---------------------------------------------------------------------\n\nmcd :: Integer -> Integer -> Integer\nmcd a 0 = a\nmcd a b = mcd b (a `mod` b)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.2. Definir y comprobar la propiedad prop_mcd seg\u00fan la\n-- cual el m\u00e1ximo com\u00fan divisor de dos n\u00fameros a y b (ambos mayores que\n-- 0) es siempre mayor o igual que 1 y adem\u00e1s es menor o igual que el\n-- menor de los n\u00fameros a  y b. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_mcd :: Integer -> Integer -> Property\nprop_mcd a b =\n  a > 0 && b > 0 ==> m >= 1 && m <= min a b \n  where m = mcd a b\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_mcd\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 2.3. Teniendo en cuenta que buscamos el m\u00e1ximo com\u00fan\n-- divisor de a y b, ser\u00eda razonable pensar que el m\u00e1ximo com\u00fan divisor\n-- siempre ser\u00eda igual o menor que la mitad del m\u00e1ximo de a y b. Definir\n-- esta propiedad y comprobarla.  \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_mcd_div :: Integer -> Integer -> Property\nprop_mcd_div a b =\n  a > 0 && b > 0 ==> mcd a b <= max a b `div` 2\n\n-- Al verificarla, se obtiene\n--    ghci> quickCheck prop_mcd_div\n--    Falsifiable, after 0 tests:\n--    3\n--    3\n-- que la refuta. Pero si la modificamos a\u00f1adiendo la hip\u00f3tesis que los n\u00fameros\n-- son distintos,\nprop_mcd_div' :: Integer -> Integer -> Property\nprop_mcd_div' a b =\n  a > 0 && b > 0 && a \/= b ==> mcd a b <= max a b `div` 2\n\n-- entonces al comprobarla\n--    ghci> quickCheck prop_mcd_div'\n--    OK, passed 100 tests.\n-- obtenemos que se verifica.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.1, Definir por recursi\u00f3n la funci\u00f3n\n--    pertenece :: Eq a => a -> [a] -> Bool\n-- tal que (pertenece x xs) se verifica si x pertenece a la lista xs. Por\n-- ejemplo, \n--    pertenece 3 [2,3,5]  ==  True\n--    pertenece 4 [2,3,5]  ==  False\n-- ---------------------------------------------------------------------\n\npertenece :: Eq a => a -> [a] -> Bool\npertenece _ []     = False\npertenece x (y:ys) = x == y || pertenece x ys\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 3.2. Comprobar con quickCheck que pertenece es equivalente\n-- a elem. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_pertenece :: Eq a => a -> [a] -> Bool\nprop_pertenece x xs = pertenece x xs == elem x xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_pertenece\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.1. Definir por recursi\u00f3n la funci\u00f3n\n--    concatenaListas :: [[a]] -> [a]\n-- tal que (concatenaListas xss) es la lista obtenida concatenando las\n-- listas de xss. Por ejemplo,\n--    concatenaListas [[1..3],[5..7],[8..10]]  ==  [1,2,3,5,6,7,8,9,10]\n-- ---------------------------------------------------------------------\n \nconcatenaListas :: [[a]] -> [a]\nconcatenaListas []       = []\nconcatenaListas (xs:xss) = xs ++ concatenaListas xss\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 4.2. Comprobar con QuickCheck que concatenaListas es\n-- equivalente a concat. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_concat :: [[Int]] -> Bool\nprop_concat xss = concatenaListas xss == concat xss\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_concat\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.1. Definir por recursi\u00f3n la funci\u00f3n\n--    coge :: Int -> [a] -> [a]\n-- tal que (coge n xs) es la lista de los n primeros elementos de\n-- xs. Por ejemplo, \n--    coge 3 [4..12]  =>  [4,5,6]\n-- ---------------------------------------------------------------------\n\ncoge :: Int -> [a] -> [a]\ncoge n _  | n <= 0 = []\ncoge _ []          = []\ncoge n (x:xs)      = x : coge (n-1) xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 5.2. Comprobar con QuickCheck que coge es equivalente a\n-- take. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_coge :: Int -> [Int] -> Bool\nprop_coge n xs =\n  coge n xs == take n xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.1. Definir, por recursi\u00f3n, la funci\u00f3n \n--    sumaCuadradosR :: Integer -> Integer\n-- tal que (sumaCuadradosR n) es la suma de los cuadrados de los n\u00fameros\n-- de 1 a n. Por ejemplo, \n--    sumaCuadradosR 4  ==  30 \n-- ---------------------------------------------------------------------\n\nsumaCuadradosR :: Integer -> Integer\nsumaCuadradosR 0 = 0\nsumaCuadradosR n = n^2 + sumaCuadradosR (n-1) \n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.2. Comprobar con QuickCheck si sumaCuadradosR n es igual a\n-- n(n+1)(2n+1)\/6. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_SumaCuadrados :: Integer -> Property\nprop_SumaCuadrados n =\n  n >= 0 ==>\n    sumaCuadradosR n == n * (n+1) * (2*n+1) `div` 6  \n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_SumaCuadrados\n--    OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.3. Definir, por comprensi\u00f3n, la funci\u00f3n \n--    sumaCuadradosC :: Integer --> Integer\n-- tal que (sumaCuadradosC n) es la suma de los cuadrados de los n\u00fameros\n-- de 1 a n. Por ejemplo, \n--    sumaCuadradosC 4  ==  30 \n-- ---------------------------------------------------------------------\n\nsumaCuadradosC :: Integer -> Integer\nsumaCuadradosC n = sum [x^2 | x <- [1..n]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 6.4. Comprobar con QuickCheck que las funciones\n-- sumaCuadradosR y sumaCuadradosC son equivalentes sobre los n\u00fameros\n-- naturales. \n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_sumaCuadradosR :: Integer -> Property\nprop_sumaCuadradosR n =\n    n >= 0 ==> sumaCuadradosR n == sumaCuadradosC n\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_sumaCuadrados\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.1. Definir, por recursi\u00f3n, la funci\u00f3n\n--    digitosR :: Integer -> [Integer]\n-- tal que (digitosR n) es la lista de los d\u00edgitos del n\u00famero n. Por\n-- ejemplo, \n--    digitosR 320274  ==  [3,2,0,2,7,4]\n-- ---------------------------------------------------------------------\n\ndigitosR :: Integer -> [Integer]\ndigitosR n = reverse (digitosR' n)\n\ndigitosR' :: Integer -> [Integer]\ndigitosR' n\n  | n < 10    = [n]\n  | otherwise = (n `rem` 10) : digitosR' (n `div` 10)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.2. Definir, por comprensi\u00f3n, la funci\u00f3n\n--    digitosC :: Integer -> [Integer]\n-- tal que (digitosC n) es la lista de los d\u00edgitos del n\u00famero n. Por\n-- ejemplo, \n--    digitosC 320274  ==  [3,2,0,2,7,4]\n-- Indicaci\u00f3n: Usar las funciones show y read.\n-- ---------------------------------------------------------------------\n\ndigitosC :: Integer -> [Integer]\ndigitosC n = [read [x] | x <- show n]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 7.3. Comprobar con QuickCheck que las funciones digitosR y\n-- digitosC son equivalentes.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_digitos :: Integer -> Property\nprop_digitos n =\n    n >= 0 ==> \n    digitosR n == digitosC n\n  \n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_digitos\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.1. Definir, por recursi\u00f3n, la funci\u00f3n \n--    sumaDigitosR :: Integer -> Integer\n-- tal que (sumaDigitosR n) es la suma de los d\u00edgitos de n. Por ejemplo,\n--    sumaDigitosR 3     ==  3\n--    sumaDigitosR 2454  == 15\n--    sumaDigitosR 20045 == 11\n-- ---------------------------------------------------------------------\n\nsumaDigitosR :: Integer -> Integer\nsumaDigitosR n\n  | n < 10    = n\n  | otherwise = n `rem` 10 + sumaDigitosR (n `div` 10)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.2. Definir, sin usar recursi\u00f3n, la funci\u00f3n \n--    sumaDigitosNR :: Integer -> Integer\n-- tal que (sumaDigitosNR n) es la suma de los d\u00edgitos de n. Por ejemplo,\n--    sumaDigitosNR 3     ==  3\n--    sumaDigitosNR 2454  == 15\n--    sumaDigitosNR 20045 == 11\n-- ---------------------------------------------------------------------\n\nsumaDigitosNR :: Integer -> Integer\nsumaDigitosNR n = sum (digitosC n)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 8.3. Comprobar con QuickCheck que las funciones sumaDigitosR\n-- y sumaDigitosNR son equivalentes.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_sumaDigitos :: Integer -> Property\nprop_sumaDigitos n =\n    n >= 0 ==>\n    sumaDigitosR n == sumaDigitosNR n\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_sumaDigitos\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.1. Definir, por recursi\u00f3n, la funci\u00f3n \n--    listaNumeroR :: [Integer] -> Integer\n-- tal que (listaNumeroR xs) es el n\u00famero formado por los d\u00edgitos xs. Por\n-- ejemplo, \n--    listaNumeroR [5]        == 5\n--    listaNumeroR [1,3,4,7]  == 1347\n--    listaNumeroR [0,0,1]    == 1\n-- ---------------------------------------------------------------------\n\nlistaNumeroR :: [Integer] -> Integer\nlistaNumeroR xs = listaNumeroR' (reverse xs)\n\nlistaNumeroR' :: [Integer] -> Integer\nlistaNumeroR' []     = 0\nlistaNumeroR' (x:xs) = x + 10 * listaNumeroR' xs\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.2. Definir, por comprensi\u00f3n, la funci\u00f3n \n--    listaNumeroC :: [Integer] -> Integer\n-- tal que (listaNumeroC xs) es el n\u00famero formado por los d\u00edgitos xs. Por\n-- ejemplo, \n--    listaNumeroC [5]        == 5\n--    listaNumeroC [1,3,4,7]  == 1347\n--    listaNumeroC [0,0,1]    == 1\n-- ---------------------------------------------------------------------\n\n-- 1\u00aa definici\u00f3n:\nlistaNumeroC :: [Integer] -> Integer\nlistaNumeroC xs = sum [y*10^n | (y,n) <- zip (reverse xs) [0..]]\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 9.3. Comprobar con QuickCheck que las funciones\n-- listaNumeroR y listaNumeroC son equivalentes.\n-- ---------------------------------------------------------------------\n\n-- La propiedad es\nprop_listaNumero :: [Integer] -> Bool\nprop_listaNumero xs =\n  listaNumeroR xs == listaNumeroC xs\n\n-- La comprobaci\u00f3n es\n--    ghci> quickCheck prop_listaNumero\n--    +++ OK, passed 100 tests.\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.1. Definir, por recursi\u00f3n, la funci\u00f3n \n--    mayorExponenteR :: Integer -> Integer -> Integer \n-- tal que (mayorExponenteR a b) es el exponente de la mayor potencia de\n-- a que divide b. Por ejemplo,\n--    mayorExponenteR 2 8    ==  3\n--    mayorExponenteR 2 9    ==  0\n--    mayorExponenteR 5 100  ==  2\n--    mayorExponenteR 2 60   ==  2\n-- \n-- Nota: Se supone que a es mayor que 1.\n-- ---------------------------------------------------------------------\n\nmayorExponenteR :: Integer -> Integer -> Integer \nmayorExponenteR a b\n  | rem b a \/= 0 = 0\n  | otherwise    = 1 + mayorExponenteR a (b `div` a)\n\n-- ---------------------------------------------------------------------\n-- Ejercicio 10.2. Definir, por comprensi\u00f3n, la funci\u00f3n \n--    mayorExponenteC :: Integer -> Integer -> Integer \n-- tal que (mayorExponenteC a b) es el exponente de la mayor potencia de\n-- a que divide a b. Por ejemplo,\n--    mayorExponenteC 2 8    ==  3\n--    mayorExponenteC 5 100  ==  2\n--    mayorExponenteC 5 101  ==  0\n-- \n-- Nota: Se supone que a es mayor que 1.\n-- ---------------------------------------------------------------------\n\nmayorExponenteC :: Integer -> Integer -> Integer\nmayorExponenteC a b = head [x-1 | x <- [0..], mod b (a^x) \/= 0]\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>En la primera parte de la clase de hoy del curso de Inform\u00e1tica de 1\u00ba del Grado en Matem\u00e1ticas se han comentado las soluciones de los ejercicios de la 4\u00aa relaci\u00f3n sobre definiciones por recursi\u00f3n. Los ejercicios y su soluci\u00f3n 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":[331],"tags":[],"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\/6807"}],"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=6807"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6807\/revisions"}],"predecessor-version":[{"id":6808,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/6807\/revisions\/6808"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=6807"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=6807"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=6807"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}