{"id":5565,"date":"2016-10-21T17:29:30","date_gmt":"2016-10-21T15:29:30","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=5565"},"modified":"2016-10-22T07:30:46","modified_gmt":"2016-10-22T05:30:46","slug":"i1m2016-ejercicios-de-definiciones-por-recursion-1","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/i1m2016-ejercicios-de-definiciones-por-recursion-1\/","title":{"rendered":"I1M2016: Ejercicios de definiciones por recursi\u00f3n (1)"},"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-16\">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-- I1M 2016-17: Rel_4_sol.hs (18 de octubre de 2016)\n-- Definiciones por recursi\u00f3n (1)\n-- Departamento de Ciencias de la Computaci\u00f3n e I.A.\n-- Universidad de Sevilla\n-- =====================================================================\n\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-16\/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 m 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 listas de\n-- 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 :: Eq a => [[a]] -> 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 n []          = []\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<\/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":[260],"tags":[270,313],"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\/5565"}],"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=5565"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5565\/revisions"}],"predecessor-version":[{"id":5566,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/5565\/revisions\/5566"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=5565"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=5565"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=5565"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}