-- Definiciones por recursión y por comprensión
-- Departamento de Ciencias de la Computación e I.A.
-- Universidad de Sevilla
-- =====================================================================
-- ---------------------------------------------------------------------
-- Introducción --
-- ---------------------------------------------------------------------
-- En esta relación se presentan ejercicios con dos definiciones (una
-- por recursión y otra por comprensión) y la comprobación de la
-- equivalencia de las dos definiciones con QuickCheck. Los ejercicios
-- corresponden a los temas 5 y 6
-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares --
-- ---------------------------------------------------------------------
import Test.QuickCheck
import Data.List
-- ---------------------------------------------------------------------
-- Ejercicio 1. Se quiere formar una escalera con bloques cuadrados,
-- de forma que tenga un número determinado de escalones. Por ejemplo,
-- una escalera con tres escalones tendría la siguiente forma:
-- XX
-- XXXX
-- XXXXXX
-- Definir, por recursión, la función
-- numeroBloquesR :: Integer -> Integer
-- tal que (numeroBloquesR n) es el número de bloques necesarios para
-- construir una escalera con n escalones. Por ejemplo,
-- numeroBloquesR 1 == 2
-- numeroBloquesR 3 == 12
-- numeroBloquesR 10 == 110
-- ---------------------------------------------------------------------
numeroBloquesR :: Integer -> Integer
numeroBloquesR 1 = 2
numeroBloquesR n = 2 * n + numeroBloquesR (n - 1)
-- ---------------------------------------------------------------------
-- Ejercicio 1.2. Definir, por comprensión, la función
-- numeroBloquesC :: Integer -> Integer
-- tal que (numeroBloquesC n) es el número de bloques necesarios para
-- construir una escalera con n escalones. Por ejemplo,
-- numeroBloquesC 1 == 2
-- numeroBloquesC 3 == 12
-- numeroBloquesC 10 == 110
-- ---------------------------------------------------------------------
numeroBloquesC :: Integer -> Integer
numeroBloquesC n = sum [2 * x | x <- [1..n]]
numeroBloquesO :: Integer -> Integer
numeroBloquesO n = foldr (+) 0 (map (*2) [1..n])
-- ---------------------------------------------------------------------
-- Ejercicio 1.3. Comprobar con QuickCheck que (numeroBloquesC n) es
-- igual a n+n^2.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_numeroBloques :: Integer -> Property
prop_numeroBloques n = n>0 ==>
numeroBloquesR n == (n + n^2) &&
numeroBloquesR n == numeroBloquesC n &&
numeroBloquesR n == numeroBloquesO n
-- ---------------------------------------------------------------------
-- Ejercicio 2.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]
-- ---------------------------------------------------------------------
digitosR :: Integer -> [Integer]
digitosR n | n < 10 = [n]
| otherwise = digitosR (div n 10) ++ [rem n 10]
-- ---------------------------------------------------------------------
-- Ejercicio 2.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.
-- ---------------------------------------------------------------------
digitosC :: Integer -> [Integer]
digitosC n = [read [x] | x <- show n]
digitosO :: Integer -> [Integer]
digitosO n = map (\ x -> read [x]) (show n)
-- ---------------------------------------------------------------------
-- Ejercicio 2.3. Comprobar con QuickCheck que las funciones digitosR y
-- digitosC son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_digitos :: Integer -> Property
prop_digitos n = n>=0 ==> digitosR n == digitosC n &&
digitosR n == digitosO n
-- ---------------------------------------------------------------------
-- Ejercicio 3.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
-- ---------------------------------------------------------------------
sumaDigitosR :: Integer -> Integer
sumaDigitosR n | n < 10 = n
| otherwise = rem n 10 + sumaDigitosR (div n 10)
-- ---------------------------------------------------------------------
-- Ejercicio 3.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
-- ---------------------------------------------------------------------
sumaDigitosNR :: Integer -> Integer
sumaDigitosNR n = sum (digitosC n)
-- ---------------------------------------------------------------------
-- Ejercicio 3.3. Comprobar con QuickCheck que las funciones sumaDigitosR
-- y sumaDigitosNR son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_sumaDigitos :: Integer -> Property
prop_sumaDigitos n = n>=0 ==> sumaDigitosR n == sumaDigitosNR n
-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
-- esDigito :: Integer -> Integer -> Bool
-- tal que (esDigito x n) se verifica si x es un dígito de n. Por
-- ejemplo,
-- esDigito 4 1041 == True
-- esDigito 3 1041 == False
-- ---------------------------------------------------------------------
esDigito :: Integer -> Integer -> Bool
esDigito x n = elem x (digitosC n)
-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir la función
-- numeroDeDigitos :: Integer -> Integer
-- tal que (numeroDeDigitos x) es el número de dígitos de x. Por ejemplo,
-- numeroDeDigitos 34047 == 5
-- ---------------------------------------------------------------------
numeroDeDigitos :: Integer -> Int
numeroDeDigitos x = length (digitosC x)
-- ---------------------------------------------------------------------
-- Ejercicio 6.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
-- ---------------------------------------------------------------------
listaNumeroR :: [Integer] -> Integer
listaNumeroR (x:[]) = x
listaNumeroR (x:xs) = last xs + 10 * listaNumeroR (x:init xs)
-- ---------------------------------------------------------------------
-- Ejercicio 6.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
-- ---------------------------------------------------------------------
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = read [head (show x) | x <- xs]
-- ---------------------------------------------------------------------
-- Ejercicio 7.1. Definir, por recursión, la función
-- pegaNumerosR :: Integer -> Integer -> Integer
-- tal que (pegaNumerosR x y) es el número resultante de "pegar" los
-- números x e y. Por ejemplo,
-- pegaNumerosR 12 987 == 12987
-- pegaNumerosR 1204 7 == 12047
-- pegaNumerosR 100 100 == 100100
-- ---------------------------------------------------------------------
pegaNumerosR :: Integer -> Integer -> Integer
pegaNumerosR x y | y < 10 = x * 10 + y
| otherwise = pegaNumerosR (x * 10 + primerDigito y) (ultimosDigitos y)
primerDigito :: Integer -> Integer
primerDigito x = head (digitosC x)
ultimosDigitos :: Integer -> Integer
ultimosDigitos x = listaNumeroC (tail (digitosC x))
-- ---------------------------------------------------------------------
-- Ejercicio 7.2. Definir, sin usar recursión, la función
-- pegaNumerosNR :: Integer -> Integer -> Integer
-- tal que (pegaNumerosNR x y) es el número resultante de "pegar" los
-- números x e y. Por ejemplo,
-- pegaNumerosNR 12 987 == 12987
-- pegaNumerosNR 1204 7 == 12047
-- pegaNumerosNR 100 100 == 100100
-- ---------------------------------------------------------------------
pegaNumerosNR :: Integer -> Integer -> Integer
pegaNumerosNR x y = listaNumeroC ((digitosC x) ++ (digitosC y))
-- ---------------------------------------------------------------------
-- Ejercicio 7.3. Comprobar con QuickCheck que las funciones
-- pegaNumerosR y pegaNumerosNR son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_pegaNumeros :: Integer -> Integer -> Property
prop_pegaNumeros x y = x >= 0 && y >= 0 ==> pegaNumerosR x y == pegaNumerosNR x y
-- ---------------------------------------------------------------------
-- Ejercicio 8.1. Definir, por recursión, la función
-- primerDigitoR :: Integer -> Integer
-- tal que (primerDigitoR n) es el primer dígito de n. Por ejemplo,
-- primerDigitoR 425 == 4
-- ---------------------------------------------------------------------
primerDigitoR :: Integer -> Integer
primerDigitoR n | n < 10 = n
| otherwise = primerDigito (div n 10)
-- ---------------------------------------------------------------------
-- Ejercicio 8.2. Definir, sin usar recursión, la función
-- primerDigitoNR :: Integer -> Integer
-- tal que (primerDigitoNR n) es la primera digito de n. Por ejemplo,
-- primerDigitoNR 425 == 4
-- ---------------------------------------------------------------------
primerDigitoNR :: Integer -> Integer
primerDigitoNR n = primerDigito n
-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Comprobar con QuickCheck que las funciones
-- primerDigitoR y primerDigitoNR son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_primerDigito :: Integer -> Property
prop_primerDigito x = x >= 0 ==> primerDigitoR x == primerDigitoNR x
-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir la función
-- ultimoDigito :: Integer -> Integer
-- tal que (ultimoDigito n) es el último dígito de n. Por ejemplo,
-- ultimoDigito 425 == 5
-- ---------------------------------------------------------------------
ultimoDigito :: Integer -> Integer
ultimoDigito n = rem n 10
-- ---------------------------------------------------------------------
-- Ejercicio 10.1. Definir la función
-- inverso :: Integer -> Integer
-- tal que (inverso n) es el número obtenido escribiendo los dígitos de n
-- en orden inverso. Por ejemplo,
-- inverso 42578 == 87524
-- inverso 203 == 302
-- ---------------------------------------------------------------------
inverso :: Integer -> Integer
inverso n = listaNumeroC (reverse (digitosC n))
-- ---------------------------------------------------------------------
-- Ejercicio 10.2. Definir, usando show y read, la función
-- inverso' :: Integer -> Integer
-- tal que (inverso' n) es el número obtenido escribiendo los dígitos de n
-- en orden inverso'. Por ejemplo,
-- inverso' 42578 == 87524
-- inverso' 203 == 302
-- ---------------------------------------------------------------------
inverso' :: Integer -> Integer
inverso' n = read (reverse (show n))
-- ---------------------------------------------------------------------
-- Ejercicio 10.3. Comprobar con QuickCheck que las funciones
-- inverso e inverso' son equivalentes.
-- ---------------------------------------------------------------------
-- La propiedad es
prop_inverso :: Integer -> Property
prop_inverso n = n >= 0 ==> inverso n == inverso' n
-- ---------------------------------------------------------------------
-- Ejercicio 11. Definir la función
-- capicua :: Integer -> Bool
-- tal que (capicua n) se verifica si si los dígitos que n son las mismas
-- de izquierda a derecha que de derecha a izquierda. Por ejemplo,
-- capicua 1234 = False
-- capicua 1221 = True
-- capicua 4 = True
-- ---------------------------------------------------------------------
capicua :: Integer -> Bool
capicua n = n == inverso n
-- ---------------------------------------------------------------------
-- Ejercicio 12. (Problema 16 del proyecto Euler) El problema se
-- encuentra en http://goo.gl/4uWh y consiste en calcular la suma de los
-- dígitos de 2^1000. Lo resolveremos mediante los distintos apartados de
-- este ejercicio.
-- ---------------------------------------------------------------------
-- ---------------------------------------------------------------------
-- Ejercicio 13.1. Definir la función
-- euler16 :: Integer -> Integer
-- tal que (euler16 n) es la suma de los dígitos de 2^n. Por ejemplo,
-- euler16 4 == 7
-- ---------------------------------------------------------------------
euler16 :: Integer -> Integer
euler16 n = sum (digitosC (2^n))
-- ---------------------------------------------------------------------
-- Ejercicio 13.2. Calcular la suma de los dígitos de 2^1000.
-- ---------------------------------------------------------------------
-- El cálculo es
-- *Main> euler16 1000
-- 1366
-- ---------------------------------------------------------------------
-- Ejercicio 14. En el enunciado de uno de los problemas de las
-- Olimpiadas matemáticas de Brasil se define el primitivo de un número
-- como sigue:
-- Dado un número natural N, multiplicamos todos sus dígitos,
-- repetimos este procedimiento hasta que quede un solo dígito al
-- cual llamamos primitivo de N. Por ejemplo para 327: 3x2x7 = 42 y
-- 4x2 = 8. Por lo tanto, el primitivo de 327 es 8.
--
-- Definir la función
-- primitivo :: Integer -> Integer
-- tal que (primitivo n) es el primitivo de n. Por ejemplo.
-- primitivo 327 == 8
-- ---------------------------------------------------------------------
primitivo :: Integer -> Integer
primitivo n | n < 10 = n
| otherwise = primitivo (product (digitosC n))
-- ---------------------------------------------------------------------
-- Ejercicio 15. Dos números son equivalentes si la media de sus dígitos
-- son iguales. Por ejemplo, 3205 y 41 son equvalentes ya que
-- (3+2+0+5)/4 = (4+1)/2. Definir la función
-- equivalentes :: Integer -> Integer -> Bool
-- tal que (equivalentes x y) se verifica si los números x e y son
-- equivalentes. Por ejemplo,
-- equivalentes 3205 41 == True
-- equivalentes 3205 25 == False
-- ---------------------------------------------------------------------
equivalentes :: Integer -> Integer -> Bool
equivalentes x y = mediaDigitos x == mediaDigitos y
where mediaDigitos x = (fromIntegral (sum (digitosC x)))/(fromIntegral (numeroDeDigitos x))
-- ---------------------------------------------------------------------
-- Ejercicio 16. Un número x es especial si el número de ocurrencia de
-- cada dígito d de x en x^2 es el doble del número de ocurrencia de d
-- en x. Por ejemplo, 72576 es especial porque tiene un 2, un 5, un 6 y
-- dos 7 y su cuadrado es 5267275776 que tiene exactamente dos 2, dos 5,
-- dos 6 y cuatro 7.
--
-- Definir la función
-- especial :: Integer -> Bool
-- tal que (especial x) se verifica si x es un número especial. Por
-- ejemplo,
-- especial 72576 == True
-- especial 12 == False
-- Calcular el menor número especial mayor que 72576.
-- ---------------------------------------------------------------------
especial :: Integer -> Bool
especial x = and [numeroOcurrencias y (x^2) == 2 * (numeroOcurrencias y x) | y <- digitosC x]
numeroOcurrencias :: Integer -> Integer -> Integer
numeroOcurrencias y x = sum [1 | z <- digitosC x, z == y]
-- El cálculo es
-- head [x | x <- [1..], x > 72576, especial x]
-- 406512
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)