Acciones

Relación 4

De Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]

-- I1M 2021-22: Rel_4.hs (20 de octubre de 2021)
-- Definiciones por recursión 
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------

-- En esta relación se presentan ejercicios con definiciones por
-- recursión correspondientes al tema 6 cuyas transparencias se 
-- encuentran en  
--    http://www.cs.us.es/~jalonso/cursos/i1m-19/temas/tema-6.html
 
-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                --
-- ---------------------------------------------------------------------

import Test.QuickCheck

-- ---------------------------------------------------------------------
-- Ejercicio 1.1. Definir por recursión la función
--    potencia :: Integer -> Integer -> Integer
-- tal que (potencia x n) es x elevado al número natural n. Por ejemplo,  
--    potencia 2 3  ==  8
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
potencia :: Integer -> Integer -> Integer
potencia _ 0 = 1
potencia x n = x * potencia x (n-1)

-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Comprobar con QuickCheck que la función potencia es
-- equivalente a la predefinida (^).
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_potencia :: Integer -> Integer -> Property
prop_potencia x n = n >= 0 ==> potencia x n == x^n

-- La comprobación es

-- *Main> quickCheck (prop_potencia)
-- +++ OK, passed 100 tests; 92 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 2.1. Dados dos números naturales, a y b, es posible
-- calcular su máximo común divisor mediante el Algoritmo de
-- Euclides. Este algoritmo se puede resumir en la siguiente fórmula:
--    mcd(a,b) = a,                   si b = 0
--             = mcd (b, a módulo b), si b > 0
-- 
-- Definir la función 
--    mcd :: Integer -> Integer -> Integer
-- tal que (mcd a b) es el máximo común divisor de a y b calculado
-- mediante el algoritmo de Euclides. Por ejemplo,
--    mcd 30 45  ==  15
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd a b = mcd b (mod a b)

-- ---------------------------------------------------------------------
-- Ejercicio 2.2. Definir y comprobar la propiedad prop_mcd según la
-- cual el máximo común divisor de dos números a y b (ambos mayores que
-- 0) es siempre mayor o igual que 1 y además es menor o igual que el
-- menor de los números a  y b. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_mcd :: Integer -> Integer -> Property
prop_mcd a b = a > 0 && b > 0 ==> mcd a b >= 1 && mcd a b <= min a b

-- Su comprobación es

-- *Main> quickCheck (prop_mcd)
-- +++ OK, passed 100 tests; 387 discarded.


-- ---------------------------------------------------------------------
-- Ejercicio 2.3. Teniendo en cuenta que buscamos el máximo común
-- divisor de a y b, sería razonable pensar que el máximo común divisor
-- siempre sería igual o menor que la mitad del máximo de a y b. Definir
-- esta propiedad y comprobarla.  
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_mcd_div :: Integer -> Integer -> Property
prop_mcd_div a b =  a > 0 && b > 0 && a /= b ==> mcd a b <=  div (max a b) 2

-- La comprobación es

-- *Main> quickCheck (prop_mcd_div)
-- +++ OK, passed 100 tests; 354 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 3.1, Definir por recursión la función
--    pertenece :: Eq a => a -> [a] -> Bool
-- tal que (pertenece x xs) se verifica si x pertenece a la lista xs. Por
-- ejemplo, 
--    pertenece 3 [2,3,5]  ==  True
--    pertenece 4 [2,3,5]  ==  False
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
pertenece :: Eq a => a -> [a] -> Bool
pertenece x [] = False
pertenece x xs = x == head xs || pertenece x (tail xs)

-- ---------------------------------------------------------------------
-- Ejercicio 3.2. Comprobar con quickCheck que pertenece es equivalente
-- a elem. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_pertenece :: Int -> [Int] -> Bool
prop_pertenece x xs = elem x xs == pertenece x xs

-- La comprobación es

-- *Main> quickCheck (prop_pertenece)
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 4.1. Definir por recursión la función
--    concatenaListas :: [[a]] -> [a]
-- tal que (concatenaListas xss) es la lista obtenida concatenando las listas de
-- xss. Por ejemplo,
--    concatenaListas [[1..3],[5..7],[8..10]]  ==  [1,2,3,5,6,7,8,9,10]
-- ---------------------------------------------------------------------
 
-- Álvaro Galisteo:
concatenaListas :: [[a]] -> [a]
concatenaListas [] = []
concatenaListas xss = head xss ++ concatenaListas (tail xss)

--Manuel Zamora Bernal:
concatenaListas :: [[a]] -> [a]
concatenaListas [] = []
concatenaListas xss = concatenaListas (init xss) ++ last xss

-- ---------------------------------------------------------------------
-- Ejercicio 4.2. Comprobar con QuickCheck que concatenaListas es
-- equivalente a concat. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_concat :: [[Int]] -> Bool
prop_concat xss = concatenaListas xss == concat xss

-- La comprobación es

-- *Main> quickCheck (prop_concat)
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 5.1. Definir por recursión la función
--    coge :: Int -> [a] -> [a]
-- tal que (coge n xs) es la lista de los n primeros elementos de
-- xs. Por ejemplo, 
--    coge   3  [4..12]  ==  [4,5,6]
--    coge (-3) [4..12]  ==  []
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
coge :: Int -> [a] -> [a]
coge n xs | n <= 0 = []
           | null xs = []
           | otherwise = [head xs] ++ coge (n-1) (tail xs) 

-- ---------------------------------------------------------------------
-- Ejercicio 5.2. Comprobar con QuickCheck que coge es equivalente a
-- take. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_coge :: Int -> [Int] -> Bool
prop_coge n xs = coge n xs == take n xs

-- La comprobación es

-- *Main> quickCheck (prop_coge)
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 6.1. Definir, por recursión, la función 
--    sumaCuadradosR :: Integer -> Integer
-- tal que (sumaCuadradosR n) es la suma de los cuadrados de los números
-- de 1 a n. Por ejemplo, 
--    sumaCuadradosR 4  ==  30 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaCuadradosR :: Integer -> Integer
sumaCuadradosR 0 = 0
sumaCuadradosR n = n^2 + sumaCuadradosR (n-1)

-- ---------------------------------------------------------------------
-- Ejercicio 6.2. Comprobar con QuickCheck si sumaCuadradosR n es igual a
-- n(n+1)(2n+1)/6. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_SumaCuadrados :: Integer -> Property
prop_SumaCuadrados n = n > 0 ==> sumaCuadradosR n == div (n*(n+1)*(2*n+1)) 6

-- La comprobación es

-- *Main> quickCheck (prop_SumaCuadrados)
-- +++ OK, passed 100 tests; 119 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 6.3. Definir, por comprensión, la función 
--    sumaCuadradosC :: Integer --> Integer
-- tal que (sumaCuadradosC n) es la suma de los cuadrados de los números
-- de 1 a n. Por ejemplo, 
--    sumaCuadradosC 4  ==  30 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
sumaCuadradosC :: Integer -> Integer
sumaCuadradosC n = sum [x^2 | x <- [1..n]]

-- ---------------------------------------------------------------------
-- Ejercicio 6.4. Comprobar con QuickCheck que las funciones
-- sumaCuadradosR y sumaCuadradosC son equivalentes sobre los números
-- naturales. 
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_sumaCuadradosR :: Integer -> Property
prop_sumaCuadradosR n = n > 0 ==> sumaCuadradosR n == sumaCuadradosC n 

-- La comprobación es

-- *Main> quickCheck (prop_sumaCuadradosR)
-- +++ OK, passed 100 tests; 112 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 7.1. Definir, por recursión, la función
--    digitosR :: Integer -> [Integer]
-- tal que (digitosR n) es la lista de los dígitos del número n. Por
-- ejemplo, 
--    digitosR 320274  ==  [3,2,0,2,7,4]
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
digitosR :: Integer -> [Integer]
digitosR 0 = []
digitosR n = digitosR (div n 10) ++ [mod n 10]

-- ---------------------------------------------------------------------
-- Ejercicio 7.2. Definir, por comprensión, la función
--    digitosC :: Integer -> [Integer]
-- tal que (digitosC n) es la lista de los dígitos del número n. Por
-- ejemplo, 
--    digitosC 320274  ==  [3,2,0,2,7,4]
-- Indicación: Usar las funciones show y read.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
digitosC :: Integer -> [Integer]
digitosC n = [read [show n !! x] | x <- [0..(length (show n) - 1)]]

-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que las funciones digitosR y
-- digitosC son equivalentes.
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
-- La propiedad es
prop_digitos :: Integer -> Property
prop_digitos n = n > 0 ==> digitosR n == digitosC n
  
-- La comprobación es
-- *Main> quickCheck (prop_digitos)
-- +++ OK, passed 100 tests; 113 discarded.

-- ---------------------------------------------------------------------
-- Ejercicio 8.1. Definir, por recursión, la función 
--    sumaDigitosR :: Integer -> Integer
-- tal que (sumaDigitosR n) es la suma de los dígitos de n. Por ejemplo,
--    sumaDigitosR 3     ==  3
--    sumaDigitosR 2454  == 15
--    sumaDigitosR 20045 == 11
-- ---------------------------------------------------------------------

-- Enrique Rodriguez Quintero, Álvaro Galisteo:
sumaDigitosR :: Integer -> Integer
sumaDigitosR 0 = 0
sumaDigitosR n = sumaDigitosR (div n 10) + mod n 10

-- ---------------------------------------------------------------------
-- Ejercicio 8.2. Definir, sin usar recursión, la función 
--    sumaDigitosNR :: Integer -> Integer
-- tal que (sumaDigitosNR n) es la suma de los dígitos de n. Por ejemplo,
--    sumaDigitosNR 3     ==  3
--    sumaDigitosNR 2454  == 15
--    sumaDigitosNR 20045 == 11
-- ---------------------------------------------------------------------

-- Enrique Rodriguez Quintero, Álvaro Galisteo:
sumaDigitosNR :: Integer -> Integer
sumaDigitosNR n = sum [read [show n !! x] | x <- [0..(length (show n) - 1)]]

-- Marta Zaitsev Borrero:
sumaDigitosNR :: Integer -> Integer
sumaDigitosNR n = sum (digitosC n)

-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Comprobar con QuickCheck que las funciones sumaDigitosR
-- y sumaDigitosNR son equivalentes.
-- ---------------------------------------------------------------------

-- Enrique Rodriguez Quintero, Álvaro Galisteo:
-- La propiedad es
prop_sumaDigitos :: Integer -> Property
prop_sumaDigitos n =  n > 0 ==> sumaDigitosR n == sumaDigitosNR n 
  
-- La comprobación es
-- *Main> quickCheck prop_sumaDigitos
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 9.1. Definir, por recursión, la función 
--    listaNumeroR :: [Integer] -> Integer
-- tal que (listaNumeroR xs) es el número formado por los dígitos xs. Por
-- ejemplo, 
--    listaNumeroR [5]        == 5
--    listaNumeroR [1,3,4,7]  == 1347
--    listaNumeroR [0,0,1]    == 1
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
listaNumeroR :: [Integer] -> Integer
listaNumeroR [] = 0
listaNumeroR xs = (head xs) * 10^(length xs - 1) + (listaNumeroR (tail xs))

-- ---------------------------------------------------------------------
-- Ejercicio 9.2. Definir, por comprensión, la función 
--    listaNumeroC :: [Integer] -> Integer
-- tal que (listaNumeroC xs) es el número formado por los dígitos xs. Por
-- ejemplo, 
--    listaNumeroC [5]        == 5
--    listaNumeroC [1,3,4,7]  == 1347
--    listaNumeroC [0,0,1]    == 1
-- ---------------------------------------------------------------------

-- Marta Zaitsev Borrero:
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = sum [(xs !! n)*10^(length xs -n-1) | n <- [0..(length xs -1)]]


-- Álvaro Galisteo: 
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = sum [x*10^y | (x,y) <- zip (reverse xs) [0..]]

-- ---------------------------------------------------------------------
-- Ejercicio 9.3. Comprobar con QuickCheck que las funciones
-- listaNumeroR y listaNumeroC son equivalentes.
-- ---------------------------------------------------------------------

-- Marta Zaitsev Borrero, Álvaro Galisteo:
-- La propiedad es
prop_listaNumero :: [Integer] -> Bool
prop_listaNumero xs = listaNumeroR xs == listaNumeroC xs

-- La comprobación es
-- quickCheck prop_listaNumero
-- +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- Ejercicio 10.1. Definir, por recursión, la función 
--    mayorExponenteR :: Integer -> Integer -> Integer 
-- tal que (mayorExponenteR a b) es el exponente de la mayor potencia de
-- a que divide b. Por ejemplo,
--    mayorExponenteR 2 8    ==  3
--    mayorExponenteR 2 9    ==  0
--    mayorExponenteR 5 100  ==  2
--    mayorExponenteR 2 60   ==  2
-- ---------------------------------------------------------------------

-- Álvaro Galisteo:
mayorExponenteR :: Integer -> Integer -> Integer
mayorExponenteR a b = if rem b a == 0 then 1 + mayorExponenteR a (div b a) else 0

-- Marta Zatsev Borrero 
mayorExponenteR :: Integer -> Integer -> Integer 
mayorExponenteR 0 _ = 0 
mayorExponenteR n 0 = 0
mayorExponenteR a b = if mod b a == 0
                      then 1 + mayorExponenteR a (div b a)
                      else 0 

-- ---------------------------------------------------------------------
-- Ejercicio 10.2. Definir, por comprensión, la función 
--    mayorExponenteC :: Integer -> Integer -> Integer 
-- tal que (mayorExponenteC a b) es el exponente de la mayor potencia de
-- a que divide a b. Por ejemplo,
--    mayorExponenteC 2 8    ==  3
--    mayorExponenteC 5 100  ==  2
--    mayorExponenteC 5 101  ==  0
-- ---------------------------------------------------------------------
-- Enrique Rodriguez Quintero 
mayorExponenteC :: Integer -> Integer -> Integer
mayorExponenteC a b = maximum [n | n <- [0..b], a^n <= b , mod b (a^n) == 0]

-- Álvaro Galisteo:
mayorExponenteC :: Integer -> Integer -> Integer
mayorExponenteC a b = sum [1 | x <- [1..b], n <- [0..b], rem x a == 0, rem b x ==0, div b (a^n) == x ]

-- Marta Zaitsev Borrero:
mayorExponenteC :: Integer -> Integer -> Integer
mayorExponenteC a b = last [x | x <- [0..b], a>=1 && b>=1, (div b (a^x))* (a^x)==b]
Obtenido de «https://www.glc.us.es/WIKIS/I1M2021G3/index.php?title=Relación_4&oldid=213»