{"id":3869,"date":"2013-11-29T18:11:44","date_gmt":"2013-11-29T17:11:44","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=3869"},"modified":"2013-12-01T08:13:03","modified_gmt":"2013-12-01T07:13:03","slug":"i1m2013-ejercicios-de-definiciones-por-recursion-y-comprension-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2013-ejercicios-de-definiciones-por-recursion-y-comprension-1\/","title":{"rendered":"I1M2013: Ejercicios de definiciones por recursi\u00f3n y comprensi\u00f3n (1)"},"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 4 a 8 de la 8\u00aa relaci\u00f3n y los 5 primeros de la 10\u00aa. En la relaci\u00f3n 8 se proponen ejercicios por recursi\u00f3n de ex\u00e1menes del curso anterior. En la relaci\u00f3n 10 se proponen ejercicios con dos definiciones (una por recursi\u00f3n y otra por comprensi\u00f3n) y la comprobaci\u00f3n de la equivalencia de las dos definiciones con QuickCheck.<\/p>\n<p>Los ejercicios 4 a 8 de la relaci\u00f3n 8 y soluciones se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    suma :: Num a => [[a]] -> a\r\n-- tal que (suma xss) es la suma de todos los elementos de todas las\r\n-- listas de xss. Por ejemplo,\r\n--    suma [[1,3,5],[2,4,1],[3,7,9]]  ==  35\r\n-- ---------------------------------------------------------------------\r\n\r\nsuma :: Num a => [[a]] -> a\r\nsuma []       = 0\r\nsuma (xs:xss) = sum xs + suma xss\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    maximaDiferencia :: [Integer] -> Integer\r\n-- tal que (maximaDiferencia xs) es la mayor de las diferencias en\r\n-- valor absoluto entre elementos consecutivos de la lista xs. Por\r\n-- ejemplo,  \r\n--    maximaDiferencia [2,5,-3]           ==  8\r\n--    maximaDiferencia [1,5]              == 4\r\n--    maximaDiferencia [10,-10,1,4,20,-2] == 22\r\n-- ---------------------------------------------------------------------\r\n \r\nmaximaDiferencia :: [Integer] -> Integer\r\nmaximaDiferencia [x,y]    = abs (x-y)\r\nmaximaDiferencia (x:y:ys) = max (abs (x-y)) (maximaDiferencia (y:ys))\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 6. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    acumulada :: Num a => [a] -> [a]\r\n-- tal que (acumulada xs) es la lista que tiene en cada posici\u00f3n i el valor que\r\n-- resulta de sumar los elementos de la lista xs desde la posicion 0\r\n-- hasta la i. Por ejemplo,\r\n--    acumulada [2,5,1,4,3] == [2,7,8,12,15]\r\n--    acumulada [1,-1,1,-1] == [1,0,1,0]\r\n-- ---------------------------------------------------------------------\r\n\r\n-- 1\u00aa definici\u00f3n:\r\nacumulada :: Num a => [a] -> [a]\r\nacumulada [] =  []\r\nacumulada xs =  acumulada (init xs) ++ [sum xs]\r\n\r\n-- 2\u00aa definici\u00f3n:\r\nacumulada2 :: Num a => [a] -> [a]\r\nacumulada2 [] = []\r\nacumulada2 (x:xs) = reverse (aux xs [x])\r\n    where aux [] ys = ys\r\n          aux (x:xs) (y:ys) = aux xs (x+y:y:ys)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 7. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    inicialesDistintos :: Eq a => [a] -> Int\r\n-- tal que (inicialesDistintos xs) es el n\u00famero de elementos que hay en\r\n-- xs antes de que aparezca el primer repetido. Por ejemplo,\r\n--    inicialesDistintos [1,2,3,4,5,3] == 2\r\n--    inicialesDistintos [1,2,3]       == 3\r\n--    inicialesDistintos \"ahora\"       == 0\r\n--    inicialesDistintos \"ahorA\"       == 5\r\n-- ---------------------------------------------------------------------\r\n\r\ninicialesDistintos :: Eq a => [a] -> Int\r\ninicialesDistintos [] = 0\r\ninicialesDistintos (x:xs) \r\n    | elem x xs = 0 \r\n    | otherwise = 1 + inicialesDistintos xs\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 8. [Problema 387 del Proyecto Euler]. Un n\u00famero de Harshad\r\n-- es un entero divisible entre la suma de sus d\u00edgitos. Por ejemplo, 201\r\n-- es un n\u00famero de Harshad porque es divisible por 3 (la suma de sus\r\n-- d\u00edgitos). Cuando se elimina el \u00faltimo d\u00edgito de 201 se obtiene 20 que\r\n-- tambi\u00e9n es un n\u00famero de Harshad. Cuando se elimina el \u00faltimo d\u00edgito\r\n-- de 20 se obtiene 2 que tambi\u00e9n es un n\u00famero de Harshad. Los n\u00famero\r\n-- como el 201 que son de Harshad y que los n\u00fameros obtenidos eliminando\r\n-- sus \u00faltimos d\u00edgitos siguen siendo de Harshad se llaman n\u00fameros de\r\n-- Harshad hereditarios por la derecha. \r\n-- \r\n-- Definir la funci\u00f3n\r\n--    numeroHHD :: Int -> Bool\r\n-- tal que (numeroHHD n) se verifica si n es un n\u00famero de Harshad\r\n-- hereditario por la derecha. Por ejemplo,\r\n--    numeroHHD 201  ==  True\r\n--    numeroHHD 140  ==  False\r\n--    numeroHHD 1104 ==  False\r\n-- Calcular el mayor n\u00famero de Harshad hereditario por la derecha con\r\n-- tres d\u00edgitos.\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroHHD :: Int -> Bool \r\nnumeroHHD n | n < 10    = True\r\n            | otherwise = numeroH n &#038;&#038; numeroHHD (div n 10) \r\n\r\n-- (numeroH n) se verifica si n es un n\u00famero de Harshad.\r\n--    numeroH 201  ==  True\r\nnumeroH :: Int -> Bool\r\nnumeroH n = rem n (sum (digitos n)) == 0\r\n\r\n-- (digitos n) es la lista de los d\u00edgitos de n. Por ejemplo,\r\n--    digitos 201  ==  [2,0,1]\r\ndigitos :: Int -> [Int]\r\ndigitos n = [read [d] | d <- show n]\r\n\r\n-- El c\u00e1lculo es\r\n--    ghci> head [n | n <- [999,998..100], numeroHHD n]\r\n--    902\r\n<\/pre>\n<p>Los 5 primeros ejercicios la relaci\u00f3n 10 y soluciones se muestran a continuaci\u00f3n<br \/>\n<!--more--><\/p>\n<pre lang=\"haskell\">\r\n-- ---------------------------------------------------------------------\r\n-- Importaci\u00f3n de librer\u00edas auxiliares                                --\r\n-- ---------------------------------------------------------------------\r\n\r\nimport Test.QuickCheck\r\nimport Data.List\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.1. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    sumaCuadradosR :: Integer -> Integer\r\n-- tal que (sumaCuadradosR n) es la suma de los cuadrados de los n\u00fameros\r\n-- de 1 a n. Por ejemplo, \r\n--    sumaCuadradosR 4  ==  30 \r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCuadradosR :: Integer -> Integer\r\nsumaCuadradosR 0 = 0\r\nsumaCuadradosR n = n^2 + sumaCuadradosR (n-1) \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.2. Comprobar con QuickCheck si sumaCuadradosR n es igual a\r\n-- n(n+1)(2n+1)\/6. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_SumaCuadrados n =\r\n  n >= 0 ==>\r\n    sumaCuadradosR n == n * (n+1) * (2*n+1) `div` 6  \r\n\r\n-- La comprobaci\u00f3n es\r\n--    Main> quickCheck prop_SumaCuadrados\r\n--    OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.3. Definir, por comprensi\u00f3n, la funci\u00f3n \r\n--    sumaCuadradosC :: Integer --> Integer\r\n-- tal que (sumaCuadradosC n) es la suma de los cuadrados de los n\u00fameros\r\n-- de 1 a n. Por ejemplo, \r\n--    sumaCuadradosC 4  ==  30 \r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCuadradosC :: Integer -> Integer\r\nsumaCuadradosC n = sum [x^2 | x <- [1..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 1.4. Comprobar con QuickCheck que las funciones\r\n-- sumaCuadradosR y sumaCuadradosC son equivalentes sobre los n\u00fameros\r\n-- naturales. \r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_sumaCuadradosR n =\r\n    n >= 0 ==> sumaCuadradosR n == sumaCuadradosC n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_sumaCuadrados\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.1. Se quiere formar una escalera con bloques cuadrados,\r\n-- de forma que tenga un n\u00famero determinado de escalones. Por ejemplo,\r\n-- una escalera con tres escalones tendr\u00eda la siguiente forma:\r\n--        XX\r\n--      XXXX\r\n--    XXXXXX\r\n-- Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    numeroBloquesR :: Integer -> Integer    \r\n-- tal que (numeroBloquesR n) es el n\u00famero de bloques necesarios para\r\n-- construir una escalera con n escalones. Por ejemplo,\r\n--    numeroBloquesR 1   ==   2\r\n--    numeroBloquesR 3   ==  12\r\n--    numeroBloquesR 10  == 110\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroBloquesR :: Integer -> Integer    \r\nnumeroBloquesR 0 = 0\r\nnumeroBloquesR n = 2*n + numeroBloquesR (n-1) \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.2. Definir, por comprensi\u00f3n, la funci\u00f3n \r\n--    numeroBloquesC :: Integer -> Integer    \r\n-- tal que (numeroBloquesC n) es el n\u00famero de bloques necesarios para\r\n-- construir una escalera con n escalones. Por ejemplo,\r\n--    numeroBloquesC 1   == 2\r\n--    numeroBloquesC 3   == 12\r\n--    numeroBloquesC 10  == 110\r\n-- ---------------------------------------------------------------------\r\n\r\nnumeroBloquesC :: Integer -> Integer    \r\nnumeroBloquesC n = sum [2*x | x <- [1..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 2.3. Comprobar con QuickCheck que (numeroBloquesC n) es\r\n-- igual a n+n^2.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_numeroBloquesR n =\r\n    n > 0 ==> numeroBloquesC n == n+n^2\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_numeroBloques\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.1. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    sumaCuadradosImparesR :: Integer -> Integer\r\n-- tal que (sumaCuadradosImparesR n) es la suma de los cuadrados de los\r\n-- n\u00fameros impares desde 1 hasta n. \r\n--    sumaCuadradosImparesR 1  ==   1\r\n--    sumaCuadradosImparesR 7  ==  84\r\n--    sumaCuadradosImparesR 4  ==  10\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCuadradosImparesR :: Integer -> Integer\r\nsumaCuadradosImparesR 1 = 1\r\nsumaCuadradosImparesR n \r\n    | odd n     = n^2 + sumaCuadradosImparesR (n-1)\r\n    | otherwise = sumaCuadradosImparesR (n-1)\r\n                     \r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.2. Definir, por comprensi\u00f3n, la funci\u00f3n \r\n--    sumaCuadradosImparesC :: Integer -> Integer\r\n-- tal que (sumaCuadradosImparesC n) es la suma de los cuadrados de los\r\n-- n\u00fameros impares desde 1 hasta n. \r\n--    sumaCuadradosImparesC 1  ==   1\r\n--    sumaCuadradosImparesC 7  ==  84\r\n--    sumaCuadradosImparesC 4  ==  10\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaCuadradosImparesC :: Integer -> Integer\r\nsumaCuadradosImparesC n = sum [x^2 | x <- [1..n], odd x]\r\n\r\n-- Otra definici\u00f3n m\u00e1s simple es\r\nsumaCuadradosImparesC' :: Integer -> Integer\r\nsumaCuadradosImparesC' n = sum [x^2 | x <- [1,3..n]]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.3. Se considera la funci\u00f3n\r\n--    f :: Integer -> Integer\r\n--    f n = (4*m^3-m) `div` 3\r\n--        where m = (n+1) `div` 2\r\n--\r\n-- Definir la funci\u00f3n\r\n--    prop_sumaCuadradosImparesR :: Integer -> Integer -> Bool\r\n-- tal que (prop_sumaCuadradosImparesR m n) se verifica si las funciones\r\n-- sumaCuadradosImparesR y f son equivalentes para todos los n\u00fameros\r\n-- entre m y n. Por ejemplo,\r\n--    prop_sumaCuadradosImparesR 1 100  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nf :: Integer -> Integer\r\nf n = (4*m^3-m) `div` 3\r\n    where m = (n+1) `div` 2\r\n\r\nprop_sumaCuadradosImparesR :: Integer -> Integer -> Bool\r\nprop_sumaCuadradosImparesR m n =\r\n    and [sumaCuadradosImparesR x == f x | x <- [m..n]] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 3.4. Definir la funci\u00f3n\r\n--    prop_sumaCuadradosImparesC :: Integer -> Integer -> Bool\r\n-- tal que (prop_sumaCuadradosImparesC m n) se verifica si las funciones\r\n-- sumaCuadradosImparesC y f son equivalentes para todos los n\u00fameros\r\n-- entre m y n. Por ejemplo,\r\n--    prop_sumaCuadradosImparesC 1 100  ==  True\r\n-- ---------------------------------------------------------------------\r\n\r\nprop_sumaCuadradosImparesC :: Integer -> Integer -> Bool\r\nprop_sumaCuadradosImparesC m n =\r\n    and [sumaCuadradosImparesC x == f x | x <- [m..n]] \r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4.1. Definir, por recursi\u00f3n, la funci\u00f3n\r\n--    digitosR :: Integer -> [Integer]\r\n-- tal que (digitosR n) es la lista de los d\u00edgitos del n\u00famero n. Por\r\n-- ejemplo, \r\n--    digitosR 320274  ==  [3,2,0,2,7,4]\r\n-- ---------------------------------------------------------------------\r\n\r\ndigitosR :: Integer -> [Integer]\r\ndigitosR n = reverse (digitosR' n)\r\n\r\ndigitosR' n\r\n    | n < 10    = [n]\r\n    | otherwise = (n `rem` 10) : digitosR' (n `div` 10)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4.2. Definir, por comprensi\u00f3n, la funci\u00f3n\r\n--    digitosC :: Integer -> [Integer]\r\n-- tal que (digitosC n) es la lista de los d\u00edgitos del n\u00famero n. Por\r\n-- ejemplo, \r\n--    digitosC 320274  ==  [3,2,0,2,7,4]\r\n-- Indicaci\u00f3n: Usar las funciones show y read.\r\n-- ---------------------------------------------------------------------\r\n\r\ndigitosC :: Integer -> [Integer]\r\ndigitosC n = [read [x] | x <- show n]\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 4.3. Comprobar con QuickCheck que las funciones digitosR y\r\n-- digitosC son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_digitos :: Integer -> Property\r\nprop_digitos n =\r\n    n >= 0 ==> \r\n    digitosR n == digitosC n\r\n  \r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_digitos\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.1. Definir, por recursi\u00f3n, la funci\u00f3n \r\n--    sumaDigitosR :: Integer -> Integer\r\n-- tal que (sumaDigitosR n) es la suma de los d\u00edgitos de n. Por ejemplo,\r\n--    sumaDigitosR 3     ==  3\r\n--    sumaDigitosR 2454  == 15\r\n--    sumaDigitosR 20045 == 11\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaDigitosR :: Integer -> Integer\r\nsumaDigitosR n\r\n    | n < 10    = n\r\n    | otherwise = n `rem` 10 + sumaDigitosR (n `div` 10)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.2. Definir, sin usar recursi\u00f3n, la funci\u00f3n \r\n--    sumaDigitosNR :: Integer -> Integer\r\n-- tal que (sumaDigitosNR n) es la suma de los d\u00edgitos de n. Por ejemplo,\r\n--    sumaDigitosNR 3     ==  3\r\n--    sumaDigitosNR 2454  == 15\r\n--    sumaDigitosNR 20045 == 11\r\n-- ---------------------------------------------------------------------\r\n\r\nsumaDigitosNR :: Integer -> Integer\r\nsumaDigitosNR n = sum (digitosC n)\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Ejercicio 5.3. Comprobar con QuickCheck que las funciones sumaDigitosR\r\n-- y sumaDigitosNR son equivalentes.\r\n-- ---------------------------------------------------------------------\r\n\r\n-- La propiedad es\r\nprop_sumaDigitos :: Integer -> Property\r\nprop_sumaDigitos n =\r\n    n >= 0 ==>\r\n    sumaDigitosR n == sumaDigitosNR n\r\n\r\n-- La comprobaci\u00f3n es\r\n--    *Main> quickCheck prop_sumaDigitos\r\n--    +++ OK, passed 100 tests.\r\n\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 4 a 8 de la 8\u00aa relaci\u00f3n y los 5 primeros de la 10\u00aa. En la relaci\u00f3n 8 se proponen ejercicios por recursi\u00f3n de ex\u00e1menes del curso anterior. En la relaci\u00f3n 10 se&#8230;<\/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,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\/3869"}],"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=3869"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3869\/revisions"}],"predecessor-version":[{"id":3870,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/3869\/revisions\/3870"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=3869"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=3869"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=3869"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}