Ir al contenido principal

Número medio

Misceláneas

Un número medio es número natural que es igual a la media aritmética de las permutaciones de sus dígitos. Por ejemplo, 370 es un número medio ya que las permutaciones de sus dígitos es 073, 037, 307, 370, 703 y 730 cuya media es 2220/6 que es igual a 370.

Definir las siguientes funciones

numeroMedio                :: Integer -> Bool
densidadesNumeroMedio      :: [Double]
graficaDensidadNumeroMedio :: Int -> IO ()

tales que

  • (numeroMedio n) se verifica si n es un número medio. Por ejemplo,
λ> numeroMedio 370
True
λ> numeroMedio 371
False
λ> numeroMedio 485596707818930041152263374
True
λ> filter numeroMedio [100..600]
[111,222,333,370,407,444,481,518,555,592]
λ> filter numeroMedio [3*10^5..6*10^5]
[333333,370370,407407,444444,481481,518518,555555,592592]
  • densidades es la lista cuyo elemento n-ésimo (empezando a contar en 1) es la densidad de números medios en el intervalo [1,n]; es decir, la cantidad de números medios menores o iguales que n dividida por n. Por ejemplo,
λ> mapM_ print (take 30 densidades)
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
0.9
0.9090909090909091
0.8333333333333334
0.7692307692307693
0.7142857142857143
0.6666666666666666
0.625
0.5882352941176471
0.5555555555555556
0.5263157894736842
0.5
0.47619047619047616
0.5
0.4782608695652174
0.4583333333333333
0.44
0.4230769230769231
0.4074074074074074
0.39285714285714285
0.3793103448275862
0.36666666666666664
  • (graficaDensidadNumeroMedio n) dibuja la gráfica de las densidades de los intervalos [1,k] para k desde 1 hasta n. Por ejemplo, (graficaDensidadNumeroMedio 100) dibuja

Número medio

y (graficaDensidadNumeroMedio 1000) dibuja

Número medio

Leer más…

Tren de potencias

Misceláneas

Si n es el número natural cuya expansión decimal es abc... , el tren de potencias de n es a^bc^d... donde el último exponente es 1, si n tiene un número impar de dígitos. Por ejemplo

trenDePotencias 2453  = 2^4*5^3     = 2000
trenDePotencias 24536 = 2^4*5^3*6^1 = 12000

Definir las funciones

trenDePotencias            :: Integer -> Integer
esPuntoFijoTrenDePotencias :: Integer -> Bool
puntosFijosTrenDePotencias :: [Integer]
tablaTrenDePotencias       :: Integer -> Integer -> IO ()

tales que

  • (trenDePotencias n) es el tren de potencia de n. Por ejemplo.
trenDePotencias 20   ==  1
trenDePotencias 21   ==  2
trenDePotencias 24   ==  16
trenDePotencias 39   ==  19683
trenDePotencias 623  ==  108
  • (esPuntoFijoTrenDePotencias n) se verifica si n es un punto fijo de trenDePotencias; es decir, (trenDePotencias n) es igual a n. Por ejemplo,
esPuntoFijoTrenDePotencias 2592                        ==  True
esPuntoFijoTrenDePotencias 24547284284866560000000000  ==  True
  • puntosFijosTrenDePotencias es la lista de los puntso fijos de trenDePotencias. Por ejemplo,
take 10 puntosFijosTrenDePotencias  ==  [1,2,3,4,5,6,7,8,9,2592]
  • (tablaTrenDePotencias a b) es la tabla de los trenes de potencias de los números entre a y b. Por ejemplo,
λ> tablaTrenDePotencias 20 39
| 20 |     1 |
| 21 |     2 |
| 22 |     4 |
| 23 |     8 |
| 24 |    16 |
| 25 |    32 |
| 26 |    64 |
| 27 |   128 |
| 28 |   256 |
| 29 |   512 |
| 30 |     1 |
| 31 |     3 |
| 32 |     9 |
| 33 |    27 |
| 34 |    81 |
| 35 |   243 |
| 36 |   729 |
| 37 |  2187 |
| 38 |  6561 |
| 39 | 19683 |
λ> tablaTrenDePotencias 2340 2359
| 2340 |        8 |
| 2341 |       32 |
| 2342 |      128 |
| 2343 |      512 |
| 2344 |     2048 |
| 2345 |     8192 |
| 2346 |    32768 |
| 2347 |   131072 |
| 2348 |   524288 |
| 2349 |  2097152 |
| 2350 |        8 |
| 2351 |       40 |
| 2352 |      200 |
| 2353 |     1000 |
| 2354 |     5000 |
| 2355 |    25000 |
| 2356 |   125000 |
| 2357 |   625000 |
| 2358 |  3125000 |
| 2359 | 15625000 |

Comprobar con QuickCheck que entre 2593 y 24547284284866559999999999 la función trenDePotencias no tiene puntos fijos.

Leer más…

La sucesión del reloj astronómico de Praga

Misceláneas

La cadena infinita "1234321234321234321...", formada por la repetición de los dígitos 123432, tiene una propiedad (en la que se basa el funcionamiento del reloj astronómico de Praga: la cadena se puede partir en una sucesión de números, de forma que la suma de los dígitos de dichos números es la serie de los números naturales, como se observa a continuación:

1, 2, 3, 4, 32, 123, 43, 2123, 432, 1234, 32123, ...
1, 2, 3, 4,  5,   6,  7,    8,   9,   10,    11, ...

Definir la lista

reloj :: [Integer]

cuyos elementos son los términos de la sucesión anterior. Por ejemplo,

λ> take 11 reloj
[1,2,3,4,32,123,43,2123,432,1234,32123]

Leer más…

Puntos alcanzables en un mapa

Misceláneas

Un mapa con dos tipos de regiones (por ejemplo, tierra y mar) se puede representar mediante una matriz de ceros y unos.

Para los ejemplos usaremos los mapas definidos por

type Punto = (Int,Int)
type Mapa  = Array Punto Int

mapa1, mapa2 :: Mapa
mapa1 = listArray ((1,1),(3,4))
                  [1,1,0,0,
                   0,1,0,0,
                   1,0,0,0]
mapa2 = listArray ((1,1),(10,20))
                  [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,
                   1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,
                   0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]

Definir las funciones

alcanzables :: Mapa -> Punto -> [Punto]
esAlcanzable :: Mapa -> Punto -> Punto -> Bool

tales que

  • (alcanzables p) es la lista de los puntos de mapa m que se pueden alcanzar a partir del punto p moviéndose en la misma región que p (es decir, a través de ceros si el elemento de m en p es un cero o a través de unos, en caso contrario) y los movimientos permitidos son ir hacia el norte, sur este u oeste (pero no en diagonal). Por ejemplo,
alcanzables mapa1 (1,1)  ==  [(2,2),(1,2),(1,1)]
alcanzables mapa1 (1,2)  ==  [(2,2),(1,1),(1,2)]
alcanzables mapa1 (1,3)  ==  [(3,2),(3,4),(3,3),(2,3),(2,4),(1,4),(1,3)]
alcanzables mapa1 (3,1)  ==  [(3,1)]
  • (esAlcanzable m p1 p2) se verifica si el punto p1 es alcanzable desde el p1 en el mapa m. Por ejemplo,
esAlcanzable mapa1 (1,4) (3,2)    ==  True
esAlcanzable mapa1 (1,4) (3,1)    ==  False
esAlcanzable mapa2 (2,3) (8,16)   ==  True
esAlcanzable mapa2 (8,1) (7,3)    ==  True
esAlcanzable mapa2 (1,1) (10,20)  ==  False

Nota: Este ejercicio está basado en el problema 10 kinds of people de Kattis.

Leer más…

Recorrido en ZigZag

Misceláneas

El recorrido en ZigZag de una matriz consiste en pasar de la primera fila hasta la última, de izquierda a derecha en las filas impares y de derecha a izquierda en las filas pares, como se indica en la figura.

/             \
| 1 -> 2 -> 3 |
|           | |
|           v |
| 4 <- 5 <- 6 |   =>  Recorrido ZigZag: [1,2,3,6,5,4,7,8,9]
| |           |
| v           |
| 7 -> 8 -> 9 |
\             /

Definir la función

recorridoZigZag :: Matrix a -> [a]

tal que (recorridoZigZag m) es la lista con los elementos de la matriz m cuando se recorre esta en ZigZag. Por ejemplo,

λ> recorridoZigZag (fromLists [[1,2,3],[4,5,6],[7,8,9]])
[1,2,3,6,5,4,7,8,9]
λ> recorridoZigZag (fromLists [[1,2],[3,4],[5,6],[7,8]])
[1,2,4,3,5,6,8,7]
λ> recorridoZigZag (fromLists [[1,2,3,4],[5,6,7,8],[9,10,11,12]])
[1,2,3,4,8,7,6,5,9,10,11,12]
λ> recorridoZigZag (fromList 5 4 "Cada paso es la meta")
"Cadasap o es al meta"
λ> recorridoZigZag (fromList 4 5 "Cada paso es la meta")
"Cada  osapes laatem "
λ> recorridoZigZag (fromList 10 2 "Cada paso es la meta")
"Caad psao se l ameat"
λ> recorridoZigZag (fromList 2 10 "Cada paso es la meta")
"Cada paso atem al se"

Leer más…

Sin ceros consecutivos

Misceláneas

Definir la función

sinDobleCero :: Int -> [[Int]]

tal que (sinDobleCero n) es la lista de las listas de longitud n formadas por el 0 y el 1 tales que no contiene dos ceros consecutivos. Por ejemplo,

λ> sinDobleCero 2
[[1,0],[1,1],[0,1]]
λ> sinDobleCero 3
[[1,1,0],[1,1,1],[1,0,1],[0,1,0],[0,1,1]]
λ> sinDobleCero 4
[[1,1,1,0],[1,1,1,1],[1,1,0,1],[1,0,1,0],[1,0,1,1],
 [0,1,1,0],[0,1,1,1],[0,1,0,1]]

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…

Valores de polinomios y de expresiones

Misceláneas

Las expresiones aritméticas construidas con una variables, los números enteros y las operaciones de sumar y multiplicar se pueden representar mediante el tipo de datos Exp definido por

data Exp = Var | Const Int | Sum Exp Exp | Mul Exp  Exp
           deriving Show

Por ejemplo, la expresión 3+5x^2 se puede representar por

exp1 :: Exp
exp1 = Sum (Const 3) (Mul Var (Mul Var (Const 5)))

Por su parte, los polinomios se pueden representar por la lista de sus coeficientes. Por ejemplo, el polinomio 3+5x^2 se puede representar por [3,0,5].

Definir las funciones

valorE :: Exp -> Int -> Int
expresion :: [Int] -> Exp
valorP :: [Int] -> Int -> Int

tales que

  • (valorE e n) es el valor de la expresión e cuando se sustituye su variable por n. Por ejemplo,
λ> valorE (Sum (Const 3) (Mul Var (Mul Var (Const 5)))) 2
23
  • (expresion p) es una expresión aritmética equivalente al polinomio p. Por ejemplo,
λ> expresion [3,0,5]
Sum (Const 3) (Mul Var (Sum (Const 0) (Mul Var (Const 5))))
  • (valorP p n) es el valor del polinomio p cuando se sustituye su variable por n. Por ejemplo,
λ> valorP [3,0,5] 2
23

Comprobar con QuickCheck que, para todo polinomio p y todo entero n,

valorP p n == valorE (expresion p) n

Leer más…

Ancestro común más bajo

Misceláneas

El tipo de los árboles binarios se define por

data Arbol = H Int
           | N Int Arbol Arbol

Por ejemplo, el árbol

     5
    / \
   /   \
  3     7
 / \   / \
1   4 6   9

se define por

ejArbol :: Arbol
ejArbol = N 5 (N 3 (H 1) (H 4)) (N 7 (H 6) (H 9))

Un árbol ordenado es un árbol binario tal que para cada nodo, los elementos de su subárbol izquierdo son menores y los de su subárbol derecho son mayores. El árbol anterior es un árbol ordenado.

Los ancestros de un nodo x son los nodos y tales que x está en alguna de las ramas de x. Por ejemplo, en el árbol anterior los ancestros de 9 son 5 y 7.

El ancestro común más bajo de dos elementos x e y de un árbol a es el ancestro de x e y de menor profundidad. Por ejemplo, en el árbol anterior el ancestro común más bajo de 6 y 9 es 7.

Definir la función

ancestroComunMasBajo :: Arbol -> Int -> Int -> Int

tal que (ancestroComunMasBajo a x y) es el ancestro de menor profundidad de los nodos x e y en el árbol ordenado a, donde x e y son dos elementos distintos del árbol a. Por ejemplo,

ancestroComunMasBajo ejArbol 4 1  ==  3
ancestroComunMasBajo ejArbol 1 6  ==  5
ancestroComunMasBajo ejArbol 6 9  ==  7

Leer más…