Ir al contenido principal

Clases de equivalencia

Misceláneas

Definir la función

clasesEquivalencia :: [a] -> (a -> a -> Bool) -> [[a]]

tal que (clasesEquivalencia xs r) es la lista de las clases de equivalencia de xs respecto de la relación de equivalencia r. Por ejemplo,

λ> clasesEquivalencia [1..20] (\x y -> x `mod` 3 == y `mod` 3)
[[1,4,7,10,13,16,19],[2,5,8,11,14,17,20],[3,6,9,12,15,18]]
λ> clasesEquivalencia [1..20] (\x y -> (x - y) `mod` 5 == 0)
[[1,6,11,16],[2,7,12,17],[3,8,13,18],[4,9,14,19],[5,10,15,20]]
λ> clasesEquivalencia [-4..4] (\x y -> abs x == abs y)
[[-4,4],[-3,3],[-2,2],[-1,1],[0]]

Leer más…

Factorial generalizado

Misceláneas

El factorial generalizado de x respecto de y y z es el producto x(x-z)(x-2z) ... (x-(y-1)z). Por ejemplo, el factorial generalizado de 7 respecto de 3 y 2 es 7x5x3 = 105 y el de 7 respecto de 2 y 3 es 7x4 = 28

Definir la función

factGen :: Integer -> Integer -> Integer -> Integer

tal que (factGen x y z) es el factorial generalizado de x respecto de y y z. Por ejemplo,

factGen 7 3 2  ==  105
factGen 7 2 3  ==  28

Nota: Se supone que x, y y z son positivos y z < x.

Comprobar con QuickCheck que (factGen x x 1) es el factorial de x.

Leer más…

Representación decimal de números racionales

Misceláneas

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

 6/2  = 3                  se representa por (3,[],[])
 1/2  = 0.5                se representa por (0,[5],[])
 1/3  = 0.333333...        se representa por (0,[],[3])
23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

type Decimal = (Integer,[Integer],[Integer])

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

type Racional = (Integer,Integer)

Definir las funciones

decimal  :: Racional -> Decimal
racional :: Decimal -> Racional

tales que

  • (decimal r) es la representación decimal del número racional r. Por ejemplo,
decimal (1,4)    ==  (0,[2,5],[])
decimal (1,3)    ==  (0,[],[3])
decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])
  • (racional d) es el número racional cuya representación decimal es d. Por ejemplo,
racional (0,[2,5],[])           ==  (1,4)
racional (0,[],[3])             ==  (1,3)
racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

λ> let (_,_,p) = decimal (23,14) in concatMap show p
"428571"
λ> let (_,_,p) = decimal (1,47) in concatMap show p
"0212765957446808510638297872340425531914893617"
λ> let (_,_,p) = decimal (1,541) in length (concatMap show p)
540

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

Leer más…

Diccionario de frecuencias

Misceláneas

Definir la función

frecuencias :: Ord a => [a] -> Map a Int

tal que (frecuencias xs) es el diccionario formado por los elementos de xs junto con el número de veces que aparecen en xs. Por ejemplo,

λ> frecuencias "sosos"
fromList [('o',2),('s',3)]
λ> frecuencias (show (10^100))
fromList [('0',100),('1',1)]
λ> frecuencias (take (10^6) (cycle "abc"))
fromList [('a',333334),('b',333333),('c',333333)]
λ> size (frecuencias (take (10^6) (cycle [1..10^6])))
1000000

Leer más…

Números cuyos dígitos coinciden con los de sus factores primos

Misceláneas

Un número n es especial si al unir los dígitos de sus factores primos, se obtienen exactamente los dígitos de n, aunque puede ser en otro orden. Por ejemplo, 1255 es especial, pues los factores primos de 1255 son 5 y 251.

Definir la función

esEspecial :: Integer -> Bool

tal que (esEspecial n) se verifica si un número n es especial. Por ejemplo,

esEspecial 1255 == True
esEspecial 125  == False

Comprobar con QuickCheck que todo número primo es especial.

Calcular los 5 primeros números especiales que no son primos.

Leer más…

Evaluación de expresiones aritméticas

Misceláneas

Las expresiones aritméticas se pueden definir mediante el siguiente tipo de dato

data Expr  = N Int | V Char | Sum Expr Expr | Mul Expr Expr
             deriving Show

Por ejemplo, (x+3)+(7*y) se representa por

ejExpr :: Expr
ejExpr = Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))

Definir la función

valor :: Expr -> Maybe Int

tal que (valor e) es 'Just v' si la expresión e es numérica y v es su valor, o bien 'Nothing' si e no es numérica. Por ejemplo:

valor (Sum (N 7) (N 9))                            == Just 16
valor (Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))) == Nothing
valor (Sum (Sum (N 1) (N 3))(Mul (N 7) (N 2)))     == Just 18

Leer más…

Posiciones de máximos locales

Misceláneas

Los vectores se definen usando tablas como sigue:

type Vector a = Array Int a

Un elemento de un vector es un máximo local si no tiene ningún elemento adyacente mayor o igual que él.

Definir la función

posMaxVec :: Ord a => Vector a -> [Int]

tal que (posMaxVec p) devuelve las posiciones del vector p en las que p tiene un máximo local. Por ejemplo,

posMaxVec (listArray (1,6) [3,2,6,7,5,3]) == [1,4]
posMaxVec (listArray (1,2) [5,5])         == []
posMaxVec (listArray (1,1) [5])           == [1]

Leer más…

Comportamiento del último dígito en primos consecutivos

Misceláneas

El pasado 11 de marzo se ha publicado el artículo Unexpected biases in the distribution of consecutive primes en el que muestra que los números primos repelen a otros primos que terminan en el mismo dígito.

La lista de los últimos dígitos de los 30 primeros números es

[2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1,3,9,3,9,7,1,3,7,9,3]

Se observa que hay 6 números que su último dígito es un 1 y de sus consecutivos 4 terminan en 3 y 2 terminan en 7.

Definir la función

distribucionUltimos :: Int -> M.Matrix Integer

tal que (distribucionUltimos n) es la matriz cuyo elemento (i,j) indica cuántos de los n primeros números primos terminan en i y su siguiente número primo termina en j. Por ejemplo,

λ> distribucionUltimos 30
( 0 0 4 0 0 0 2 0 0 )
( 0 0 1 0 0 0 0 0 0 )
( 0 0 0 0 1 0 4 0 4 )
( 0 0 0 0 0 0 0 0 0 )
( 0 0 0 0 0 0 1 0 0 )
( 0 0 0 0 0 0 0 0 0 )
( 4 0 1 0 0 0 0 0 2 )
( 0 0 0 0 0 0 0 0 0 )
( 2 0 3 0 0 0 1 0 0 )

λ> distribucionUltimos (10^5)
( 4104    0 7961    0    0    0 8297    0 4605 )
(    0    0    1    0    0    0    0    0    0 )
( 5596    0 3604    0    1    0 7419    0 8387 )
(    0    0    0    0    0    0    0    0    0 )
(    0    0    0    0    0    0    1    0    0 )
(    0    0    0    0    0    0    0    0    0 )
( 6438    0 6928    0    0    0 3627    0 8022 )
(    0    0    0    0    0    0    0    0    0 )
( 8830    0 6513    0    0    0 5671    0 3995 )

Nota: Se observa cómo se "repelen" ya que en las filas del 1, 3, 7 y 9 el menor elemento es el de la diagonal.

Leer más…

Máxima suma de elementos consecutivos

Misceláneas

Definir la función

sumaMaxima :: [Integer] -> Integer

tal que (sumaMaxima xs) es el valor máximo de la suma de elementos consecutivos de la lista xs. Por ejemplo,

sumaMaxima []             ==  0
sumaMaxima [2,-2,3,-3,4]  ==  4
sumaMaxima [-1,-2,-3]     ==  0
sumaMaxima [2,-1,3,-2,3]  ==  5
sumaMaxima [1,-1,3,-2,4]  ==  5
sumaMaxima [2,-1,3,-2,4]  ==  6
sumaMaxima [1..10^6]      ==  500000500000

Comprobar con QuickCheck que

sumaMaxima xs == sumaMaxima (reverse xs)

Leer más…

Rotación de una matriz

Misceláneas

En la siguiente figura, al rotar girando 90 grados en el sentido del reloj la matriz de la izquierda, obtenemos la de la derecha

1 2 3        7 4 1
4 5 6        8 5 2
7 8 9        9 6 3

Definir la función

rota :: Matrix Int -> Matrix Int

tal que (rota p) es la matriz obtenida girando en el sentido del reloj la matriz cuadrada p. Por ejemplo,

λ> rota (fromList 3 3 [1..9])
( 7 4 1 )
( 8 5 2 )
( 9 6 3 )

λ> rota (fromList 3 3 [7,4,1,8,5,2,9,6,3])
( 9 8 7 )
( 6 5 4 )
( 3 2 1 )

Leer más…