-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
numeroBloquesR :: Integer -> Integer
numeroBloquesR 1 = 2
numeroBloquesR n = numeroBloquesR (n-1) + 2
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
numeroBloquesC :: Integer -> Integer
numeroBloquesC n = sum [2*x | x <- [1..n]]
-- ---------------------------------------------------------------------
-- Ejercicio 1.3. Comprobar con QuickCheck que (numeroBloquesC n) es
-- igual a n+n^2.
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
-- La propiedad es
prop_numeroBloquesR :: Integer -> Property
prop_numeroBloquesR n = n>0 ==> numeroBloquesC n == n+n^2
-- La comprobación es
-- *Main> quickCheck prop_numeroBloquesR
-- +++ OK, passed 100 tests; 107 discarded.
-- ---------------------------------------------------------------------
-- 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]
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
digitosR :: Integer -> [Integer]
digitosR n = if n == mod n 10 then [n] else digitosR (div n 10) ++ [(mod 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.
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
digitosC :: Integer -> [Integer]
digitosC n = [read [x] :: Integer | x <- (show n) ]
-- ---------------------------------------------------------------------
-- Ejercicio 2.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; 81 discarded.
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
sumaDigitosR :: Integer -> Integer
sumaDigitosR n = if n == mod n 10 then n else sumaDigitosR (div n 10) + (mod 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
sumaDigitosNR :: Integer -> Integer
sumaDigitosNR n = sum [read [x] :: Integer | x <- (show n) ]
-- ---------------------------------------------------------------------
-- Ejercicio 3.3. Comprobar con QuickCheck que las funciones sumaDigitosR
-- y sumaDigitosNR son equivalentes.
-- ---------------------------------------------------------------------
-- Á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; 90 discarded.
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
esDigito :: Integer -> Integer -> Bool
esDigito x n = elem x [read [x] :: Integer | x <- (show 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
numeroDeDigitos :: Integer -> Int
numeroDeDigitos x = if x == mod x 10 then 1 else numeroDeDigitos (div x 10) + 1
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
listaNumeroR :: [Integer] -> Integer
listaNumeroR [] = 0
listaNumeroR (x:xs) = x*10^(length xs) + listaNumeroR 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
listaNumeroC :: [Integer] -> Integer
listaNumeroC xs = sum [x*10^y | (x,y) <- zip xs (reverse [0..(length xs - 1)])]
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
pegaNumerosR :: Integer -> Integer -> Integer
pegaNumerosR x y = listaNumeroR (digitosR x ++ digitosR y)
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
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.
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
-- La propiedad es
prop_pegaNumeros :: Integer -> Integer -> Property
prop_pegaNumeros x y = x>=0 && y>=0 ==> pegaNumerosR x y == pegaNumerosNR x y
-- La comprobación es
-- *Main> quickCheck prop_pegaNumeros
-- +++ OK, passed 100 tests; 291 discarded.
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
primerDigitoR :: Integer -> Integer
primerDigitoR n = if n == mod n 10 then n else primerDigitoR (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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
primerDigitoNR :: Integer -> Integer
primerDigitoNR n = head [read [x] :: Integer | x <- (show n) ]
-- ---------------------------------------------------------------------
-- Ejercicio 8.3. Comprobar con QuickCheck que las funciones
-- primerDigitoR y primerDigitoNR son equivalentes.
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
-- La propiedad es
prop_primerDigito :: Integer -> Property
prop_primerDigito x = x>=0 ==> primerDigitoR x == primerDigitoNR x
-- La comprobación es
-- *Main> quickCheck prop_primerDigito
-- +++ OK, passed 100 tests; 86 discarded.
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
ultimoDigito :: Integer -> Integer
ultimoDigito n = mod 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
inverso :: Integer -> Integer
inverso n = sum [x*10^y | (x,y) <- zip (digitosR n) [0..]]
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
inverso' :: Integer -> Integer
inverso' n = read (reverse (show n)) :: Integer
-- ---------------------------------------------------------------------
-- Ejercicio 10.3. Comprobar con QuickCheck que las funciones
-- inverso e inverso' son equivalentes.
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
-- La propiedad es
prop_inverso :: Integer -> Property
prop_inverso n = n>=0 ==> inverso n == inverso' n
-- La comprobación es
-- *Main> quickCheck prop_inverso
-- +++ OK, passed 100 tests; 93 discarded.
-- ---------------------------------------------------------------------
-- 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
capicua :: Integer -> Bool
capicua n = and [x==y | (x,y) <- zip (digitosR n) (reverse (digitosR 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
euler16 :: Integer -> Integer
euler16 n = sumaDigitosR (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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
primitivo :: Integer -> Integer
primitivo n = if productoDeDigitos n == mod (productoDeDigitos n) 10 then productoDeDigitos n else primitivo (productoDeDigitos n)
where productoDeDigitos n = product (digitosR 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
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
equivalentes :: Integer -> Integer -> Bool
equivalentes x y = fromIntegral((sumaDigitosR x)) / fromIntegral(numeroDigitos x) == fromIntegral((sumaDigitosR y)) / fromIntegral(numeroDigitos y)
where numeroDigitos n = sum [1 | _ <- (digitosR n)]
-- ---------------------------------------------------------------------
-- 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.
-- ---------------------------------------------------------------------
-- Álvaro Galisteo:
especial :: Integer -> Bool
especial x = intersect (union (digitosR x) (digitosR x)) (digitosR (x^2)) == union (digitosR x) (digitosR x)
-- El cálculo es
calculoEspecial = head [x | x <- [72577..], especial x]
-- *Main> calculoEspecial
-- 72577
![Informática de 1º de Matemáticas [Curso 2021-22, Grupo 3]](/WIKIS/I1M2021G3/resources/assets/logoUS.png)