Ir al contenido principal

Números como sumas de primos consecutivos.

Misceláneas

El número 311 se puede escribir de 5 formas distintas como suma de 1 o más primos consecutivos

311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
311 =  53 +  59 +  61 + 67 + 71
311 = 101 + 103 + 107
311 = 311

el número 41 se puede escribir de 4 formas

41 =  2 +  3 +  5 + 7 + 11 + 13
41 = 11 + 13 + 17
41 = 41

y el número 14 no se puede escribir como suma de primos consecutivos.

Definir la función

sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma de uno o más números primos consecutivos. Por ejemplo,

λ> sumas 311
[[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],
[53,59,61,67,71],[101,103,107],[311]]
λ> sumas 41
[[2,3,5,7,11,13],[11,13,17],[41]]
λ> sumas 14
[]
λ> [length (sumas n) | n <- [0..20]]
[0,0,1,1,0,2,0,1,1,0,1,1,1,1,0,1,0,2,1,1,0]
λ> maximum [length (sumas n) | n <- [1..600]]
5

Leer más…

Subnúmeros pares

Misceláneas

Los subnúmeros de un número x son los números que se pueden formar con dígitos de x en posiciones consecutivas. Por ejemplo, el número 254 tiene 6 subnúmeros: 2, 5, 4, 25, 54 y 254.

Definir las funciones

subnumeros       :: Integer -> [Integer]
nSubnumerosPares :: Integer -> Integer

tales que

  • (subnumerosPares x) es la lista de los subnúmeros pares de x. Por ejemplo,
subnumerosPares 254   ==  [2,254,54,4]
subnumerosPares 154   ==  [154,54,4]
subnumerosPares 15    ==  []
  • (nSubnumerosPares x) es la cantidad de subnúmeros pares de x. Por ejemplo,
nSubnumerosPares 254   ==  4
nSubnumerosPares2 (4^(10^6))  ==  90625258498

Soluciones

import Data.List ( genericLength
                 , inits
                 , tails
                 )

subnumerosPares :: Integer -> [Integer]
subnumerosPares n =
  filter even (subnumeros n)

-- (subnumeros n) es la lista de los subnúmeros de n. Por ejemplo,
--    subnumeros 254  ==  [2,25,5,254,54,4]
subnumeros :: Integer -> [Integer]
subnumeros n =
  [read x | x <- sublistas (show n)]

-- (sublistas xs) es la lista de las sublistas de xs. Por ejemplo,
--    sublistas "abc"  ==  ["a","ab","b","abc","bc","c"]
sublistas :: [a] -> [[a]]
sublistas xs =
  concat [init (tails ys) | ys <- tail (inits xs)]

-- 1ª definición
-- =============

nSubnumerosPares :: Integer -> Integer
nSubnumerosPares =
  genericLength . subnumerosPares

-- 2ª definición
-- =============

nSubnumerosPares2 :: Integer -> Integer
nSubnumerosPares2 =
  sum . posicionesDigitosPares

-- (posicionesDigitosPares x) es la lista de las posiciones de los
-- dígitos pares de x. Por ejemplo,
--    posicionesDigitosPares 254  ==  [1,3]
posicionesDigitosPares :: Integer -> [Integer]
posicionesDigitosPares x =
  [n | (n,y) <- zip [1..] (show x)
     , y `elem` "02468"]

-- Comparación de eficiencia
--    λ> nSubnumerosPares (2^(10^3))
--    22934
--    (2.83 secs, 3,413,414,872 bytes)
--    λ> nSubnumerosPares2 (2^(10^3))
--    22934
--    (0.01 secs, 0 bytes)

Elementos con su doble en el conjunto.

Misceláneas

Definir la función

conDoble :: [Int] -> [Int]

tal que (conDoble xs) es la lista de los elementos del conjunto xs (representado como una lista sin elementos repetidos) cuyo doble pertenece a xs. Por ejemplo,

conDoble [1, 4, 3, 2, 9, 7, 18, 22]  ==  [1,2,9]
conDoble [2, 4, 8, 10]               ==  [2,4]
conDoble [7, 5, 11, 13, 1, 3]        ==  []
length (conDoble4 [1..10^6])         ==  500000

Referencia: Basado en el problema Doubles de POJ (Peking University Online Judge System).

Leer más…

Buscaminas

Misceláneas

El buscaminas es un juego cuyo objetivo es despejar un campo de minas sin detonar ninguna.

El campo de minas se representa mediante un cuadrado con NxN casillas. Algunas casillas tienen un número, este número indica las minas que hay en todas las casillas vecinas. Cada casilla tiene como máximo 8 vecinas. Por ejemplo, el campo 4x4 de la izquierda contiene dos minas, cada una representada por el número 9, y a la derecha se muestra el campo obtenido anotando las minas vecinas de cada casilla

9 0 0 0       9 1 0 0
0 0 0 0       2 2 1 0
0 9 0 0       1 9 1 0
0 0 0 0       1 1 1 0

de la misma forma, la anotación del siguiente a la izquierda es el de la derecha

9 9 0 0 0     9 9 1 0 0
0 0 0 0 0     3 3 2 0 0
0 9 0 0 0     1 9 1 0 0

En el ejercicio se usará la librería Data.Matrix, cuyo manual se encuentra en aquí.

Los campos de minas se representan mediante matrices:

type Campo = Matrix Int

Por ejemplo, los anteriores campos de la izquierda se definen por

ejCampo1, ejCampo2 :: Campo
ejCampo1 = fromLists [[9,0,0,0],
                      [0,0,0,0],
                      [0,9,0,0],
                      [0,0,0,0]]
ejCampo2 = fromLists [[9,9,0,0,0],
                      [0,0,0,0,0],
                      [0,9,0,0,0]]

Definir la función

buscaminas :: Campo -> Campo

tal que (buscaminas c) es el campo obtenido anotando las minas vecinas de cada casilla. Por ejemplo,

λ> buscaminas ejCampo1
( 9 1 0 0 )
( 2 2 1 0 )
( 1 9 1 0 )
( 1 1 1 0 )

λ> buscaminas ejCampo2
( 9 9 1 0 0 )
( 3 3 2 0 0 )
( 1 9 1 0 0 )

Leer más…

Clases de equivalencia

Misceláneas

Definir la función

clasesEquivalencia :: Ord a =>
                      Set a -> (a -> a -> Bool) -> Set (Set a)

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

λ> let c = fromList [-3..3]
λ> clasesEquivalencia c (\x y -> x `mod` 3 == y `mod` 3)
fromList [fromList [-3,0,3],fromList [-2,1],fromList [-1,2]]
λ> clasesEquivalencia c (\x y -> (x - y) `mod` 2 == 0)
fromList [fromList [-3,-1,1,3],fromList [-2,0,2]]

Leer más…

Ampliación de una matriz

Misceláneas

Definir, usando Data.Matrix, la función

ampliaMatriz :: Matrix a -> Int -> Int -> Matrix a

tal que (ampliaMatriz p f c) es la matriz obtenida a partir de p repitiendo cada fila f veces y cada columna c veces. Por ejemplo, si ej1 es la matriz definida por

ej1 :: Matrix Char
ej1 = fromLists [" x ",
                 "x x",
                 " x "]

entonces

λ> ampliaMatriz ej1 1 2
( ' ' ' ' 'x' 'x' ' ' ' ' )
( 'x' 'x' ' ' ' ' 'x' 'x' )
( ' ' ' ' 'x' 'x' ' ' ' ' )

λ> (putStr . unlines . toLists) (ampliaMatriz ej1 1 2)
  xx
xx  xx
  xx
λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 1)
 x
 x
x x
x x
 x
 x
λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 2)
  xx
  xx
xx  xx
xx  xx
  xx
  xx
λ> (putStr . unlines . toLists) (ampliaMatriz ej1 2 3)
   xxx
   xxx
xxx   xxx
xxx   xxx
   xxx
   xxx

Nota: Este ejercicio está basado en el problema Skener de Kattis.

Leer más…

Problema de las jarras

Misceláneas

En el problema de las jarras (A,B,C) se tienen dos jarras sin marcas de medición, una de A litros de capacidad y otra de B. También se dispone de una bomba que permite llenar las jarras de agua.

El problema de las jarras (A,B,C) consiste en determinar cómo se puede lograr tener exactamente C litros de agua en alguna de las dos jarras.

Definir la función

jarras :: (Int,Int,Int) -> Maybe [(Int,Int)]

tal (jarras (a,b,c)) es una solución del problema de las jarras (a,b,c) con el mínimo número de movimientos, si el problema tiene solución y Nothing, en caso contrario. Por ejemplo,

λ> jarras (5,3,4)
Just [(0,0),(5,0),(2,3),(2,0),(0,2),(5,2),(4,3)]

La interpretación de la solución anterior es

(0,0) se inicia con las dos jarras vacías,
(5,0) se llena la jarra de 5 con el grifo,
(2,3) se llena la de 3 con la de 5,
(2,0) se vacía la de 3,
(0,2) se pasa el contenido de la primera a la segunda,
(5,2) se llena la primera con el grifo,
(4,3) se llena la segunda con la primera.

Otros ejemplos:

λ> jarras (3,5,4)
Just [(0,0),(0,5),(3,2),(0,2),(2,0),(2,5),(3,4)]
λ> jarras (15,10,5)
Just [(0,0),(15,0),(5,10)]
λ> jarras (15,10,4)
Nothing
λ> length <$> jarras (181,179,100)
Just 199

Leer más…

El problema de las N torres

Misceláneas

El problema de las N torres consiste en colocar N torres en un tablero con N filas y N columnas de forma que no haya dos torres en la misma fila ni en la misma columna.

Cada solución del problema de puede representar mediante una matriz con ceros y unos donde los unos representan las posiciones ocupadas por las torres y los ceros las posiciones libres. Por ejemplo,

( 0 1 0 )
( 1 0 0 )
( 0 0 1 )

representa una solución del problema de las 3 torres.

Definir las funciones

torres  :: Int -> [Matrix Int]
nTorres :: Int -> Integer

tales que + (torres n) es la lista de las soluciones del problema de las n torres. Por ejemplo,

λ> torres 3
[( 1 0 0 )
 ( 0 1 0 )
 ( 0 0 1 )
,( 1 0 0 )
 ( 0 0 1 )
 ( 0 1 0 )
,( 0 1 0 )
 ( 1 0 0 )
 ( 0 0 1 )
,( 0 1 0 )
 ( 0 0 1 )
 ( 1 0 0 )
,( 0 0 1 )
 ( 1 0 0 )
 ( 0 1 0 )
,( 0 0 1 )
 ( 0 1 0 )
 ( 1 0 0 )
]
  • (nTorres n) es el número de soluciones del problema de las n torres. Por ejemplo,
λ> nTorres 3
6
λ> length (show (nTorres (10^4)))
35660

Leer más…

Densidades de números abundantes, perfectos y deficientes

Misceláneas

La n-ésima densidad de un tipo de número es el cociente entre la cantidad de los números entre 1 y n que son del tipo considerado y n. Por ejemplo, la 7-ésima densidad de los múltiplos de 3 es 2/7 ya que entre los 7 primeros números sólo 2 son múltiplos de 3.

Definir las funciones

densidades :: Int -> (Double,Double,Double)
graficas   :: Imt -> IO ()

tales que

  • (densidades n) es la terna formada por la n-ésima densidad de los números abundantes (es decir, para los que la suma de sus divisores propios es mayor que el número), de los números perfectos (es decir, para los que la suma de sus divisores propios es mayor que el número) y de los números deficientes (es decir, para los que la suma de sus divisores propios es menor que el número). Por ejemplo,
densidades 100     ==  (0.22,    2.0e-2, 0.76)
densidades 1000    ==  (0.246,   3.0e-3, 0.751)
densidades 10000   ==  (0.2488,  4.0e-4, 0.7508)
densidades 100000  ==  (0.24795, 4.0e-5, 0.75201)
  • (graficas n) dibuja las gráficas de las k-ésimas densidades (para k entre 1 y n) de los números abundantes, de los números perfectos y de los números deficientes. Por ejemplo, (graficas 100) dibuja

Densidades de números abundantes, perfectos y deficientes

y (graficas 400) dibuja

Densidades de números abundantes, perfectos y deficientes

Leer más…

Enumeración de árboles binarios

Misceláneas

Los árboles binarios se pueden representar mediante el tipo Arbol definido por

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
             deriving Show

Por ejemplo, el árbol

      "B"
      / \
     /   \
    /     \
  "B"     "A"
  / \     / \
"A" "B" "C" "C"

se puede definir por

ej1 :: Arbol String
ej1 = N "B" (N "B" (H "A") (H "B")) (N "A" (H "C") (H "C"))

Definir la función

enumeraArbol :: Arbol t -> Arbol Int

tal que (enumeraArbol a) es el árbol obtenido numerando las hojas y los nodos de a desde la hoja izquierda hasta la raíz. Por ejemplo,

λ> enumeraArbol ej1
N 6 (N 2 (H 0) (H 1)) (N 5 (H 3) (H 4))

Gráficamente,

      6
     / \
    /   \
   /     \
  2       5
 / \     / \
0   1   3   4

Leer más…