Ir al contenido principal

Subconjuntos divisibles

Misceláneas

Definir la función

subconjuntosDivisibles :: [Int] -> [[Int]]

tal que (subconjuntosDivisibles xs) es la lista de todos los subconjuntos de xs en los que todos los elementos tienen un factor común mayor que 1. Por ejemplo,

subconjuntosDivisibles []         ==  [[]]
subconjuntosDivisibles [1]        ==  [[]]
subconjuntosDivisibles [3]        ==  [[3],[]]
subconjuntosDivisibles [1,3]      ==  [[3],[]]
subconjuntosDivisibles [3,6]      ==  [[3,6],[3],[6],[]]
subconjuntosDivisibles [1,3,6]    ==  [[3,6],[3],[6],[]]
subconjuntosDivisibles [2,3,6]    ==  [[2,6],[2],[3,6],[3],[6],[]]
subconjuntosDivisibles [2,3,6,8]  ==  [[2,6,8],[2,6],[2,8],[2],[3,6],[3],[6,8],[6],[8],[]]
length (subconjuntosDivisibles [1..10])  ==  41
length (subconjuntosDivisibles [1..20])  ==  1097
length (subconjuntosDivisibles [1..30])  ==  33833
length (subconjuntosDivisibles [1..40])  ==  1056986

Leer más…

Matriz girada 180 grados

Misceláneas

Definir la función

matrizGirada180 :: Matrix a -> Matrix a

tal que (matrizGirada180 p) es la matriz obtenida girando 180 grados la matriz p. Por ejemplo,

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

λ> matrizGirada180 (fromList 4 3 [1..])
( 12 11 10 )
(  9  8  7 )
(  6  5  4 )
(  3  2  1 )

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

λ> matrizGirada180 (fromList 3 4 [1..])
( 12 11 10  9 )
(  8  7  6  5 )
(  4  3  2  1 )

Leer más…

Árboles cuyas ramas cumplen una propiedad

Misceláneas

Los árboles se pueden representar mediante el siguiente tipo de dato

data Arbol a = N a [Arbol a]
  deriving Show

Por ejemplo, los árboles

   -1           1            1
   / \         / \          /|\
  2   3      -2   3        / | \
 / \          |          -2  7  3
4   5        -4          / \
                        4   5

se representan por

ej1, ej2, ej3 :: Arbol Int
ej1 = N (-1) [N 2 [N 4 [], N 5 []], N 3 []]
ej2 = N 1 [N (-2) [N (-4) []], N 3 []]
ej3 = N 1 [N (-2) [N 4 [], N 5 []], N 7 [], N 3 []]

Definir la función

todasDesdeAlguno :: (a -> Bool) -> Arbol a -> Bool

tal que (todasDesdeAlguno p ar) se verifica si para toda rama existe un elemento a partir del cual todos los elementos de la rama verifican la propiedad p. Por ejemplo,

todasDesdeAlguno (>0) ej1 == True
todasDesdeAlguno (>0) ej2 == False
todasDesdeAlguno (>0) ej3 == True

Leer más…

El problema del número perdido

Misceláneas

Sea xs una lista de números consecutivos (creciente o decreciente), en la que puede faltar algún número. El problema del número perdido en xs consiste en lo siguiente:

  • si falta un único número z, devolver Just z
  • si no falta ninguno, devolver Nothing

Definir la función

numeroPerdido :: [Int] -> Maybe Int

tal que (numeroPerdido xs) es el resultado del problema del número perdidio en xs. Por ejemplo,

numeroPerdido [7,6,4,3]                     == Just 5
numeroPerdido [1,2,4,5,6]                   == Just 3
numeroPerdido [6,5..3]                      == Nothing
numeroPerdido [1..6]                        == Nothing
numeroPerdido ([5..10^6] ++ [10^6+2..10^7]) == Just 1000001

Leer más…

Matriz de mínimas distancias

Misceláneas

Definir las funciones

minimasDistancias             :: Matrix Int -> Matrix Int
sumaMinimaDistanciasIdentidad :: Int -> Int

tales que

  • (mininasDistancias a) es la matriz de las mínimas distancias de cada elemento de a hasta alcanzar un 1 donde un paso es un movimiento hacia la izquierda, derecha, arriba o abajo. Por ejemplo,
λ> minimasDistancias (fromLists [[0,1,1],[0,0,1]])
( 1 0 0 )
( 2 1 0 )
λ> minimasDistancias (fromLists [[0,0,1],[1,0,0]])
( 1 1 0 )
( 0 1 1 )
λ> minimasDistancias (identity 5)
( 0 1 2 3 4 )
( 1 0 1 2 3 )
( 2 1 0 1 2 )
( 3 2 1 0 1 )
( 4 3 2 1 0 )
  • (sumaMinimaDistanciasIdentidad n) es la suma de los elementos de la matriz de las mínimas distancias correspondiente a la matriz identidad de orden n. Por ejemplo,
sumaMinimaDistanciasIdentidad 5       ==  40
sumaMinimaDistanciasIdentidad (10^2)  ==  333300
sumaMinimaDistanciasIdentidad (10^4)  ==  333333330000
sumaMinimaDistanciasIdentidad (10^6)  ==  333333333333000000

Leer más…

La sucesión ECG

Misceláneas

La sucesión ECG estás definida por a(1) = 1, a(2) = 2 y, para n >= 3, a(n) es el menor natural que auún no está en la sucesión tal que a(n) tiene algún divisor común con a(n-1).

Los primeros términos de la sucesión son 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15, ...

Al dibujar su gráfica, se parece a la de los electrocardiogramas (abreviadamente, ECG). Por ello, la sucesión se conoce como la sucesión ECG.

Definir las funciones

sucECG :: [Integer]
graficaSucECG :: Int -> IO ()
  • sucECG es la lista de los términos de la sucesión ECG. Por ejemplo,
λ> take 20 sucECG
[1,2,4,6,3,9,12,8,10,5,15,18,14,7,21,24,16,20,22,11]
λ> sucECG !! 6000
6237
  • (graficaSucECG n) dibuja la gráfica de los n primeros términos de la sucesión ECG. Por ejemplo, (graficaSucECG 160) dibuja

La sucesión ECG

Leer más…

Siguiente mayor

Misceláneas

Definir la función

siguienteMayor :: Ord a => [a] -> [Maybe a]

tal que (siguienteMayos xs) es la lista obtenida sustiyendo cada elemento de xs por el primer elemento de xs a la derechha de x que sea mayor que x, si esxte y Nothing en caso contrario. Por ejemplo,

λ> siguienteMayor [4,5,2,3,9]
[Just 5,Just 9,Just 3,Just 9,Nothing]
λ> siguienteMayor [9,5,2,3,4]
[Nothing,Nothing,Just 3,Just 4,Nothing]
λ> siguienteMayor [9,5,2,2,4]
[Nothing,Nothing,Just 4,Just 4,Nothing]
λ> siguienteMayor "betis"
[Just 'e',Just 't',Nothing,Just 's',Nothing]
λ> siguienteMayor "sevilla"
[Just 'v',Just 'v',Nothing,Just 'l',Nothing,Nothing,Nothing]

Leer más…

Caminos minimales en un arbol numérico

Misceláneas

En la librería Data.Tree se definen los tipos de árboles y bosques como sigue

data Tree a   = Node a (Forest a)
type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

λ> putStrLn (drawTree (fmap show ej))
3
|
+- 5
|  |
|  `- 9
|
`- 7

Los mayores divisores de un número x son los divisores u tales que u > 1 y existe un v tal que 1 < v < u y u.v = x. Por ejemplo, los mayores divisores de 24 son 12, 8 y 6.

El árbol de los predecesores y mayores divisores de un número x es el árbol cuya raíz es x y los sucesores de cada nodo y > 1 es el conjunto formado por y-1 junto con los mayores divisores de y. Los nodos con valor 1 no tienen sucesores. Por ejemplo, el árbol de los predecesores y mayores divisores del número 6 es

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

Definir las siguientes funciones

mayoresDivisores :: Int -> [Int]
arbol            :: Int -> Tree Int
caminos          :: Int -> [[Int]]
caminosMinimales :: Int -> [[Int]]

tales que + (mayoresDivisores x) es la lista de los mayores divisores de x. Por ejemplo,

mayoresDivisores 24  ==  [12,8,6]
mayoresDivisores 16  ==  [8,4]
mayoresDivisores 10  ==  [5]
mayoresDivisores 17  ==  []
  • (arbol x) es el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
λ> putStrLn (drawTree (fmap show (arbol 6)))
6
|
+- 5
|  |
|  `- 4
|     |
|     +- 3
|     |  |
|     |  `- 2
|     |     |
|     |     `- 1
|     |
|     `- 2
|        |
|        `- 1
|
`- 3
   |
   `- 2
      |
      `- 1
  • (caminos x) es la lista de los caminos en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
λ> caminos 6
[[6,5,4,3,2,1],[6,5,4,2,1],[6,3,2,1]]
  • (caminosMinimales x) es la lista de los caminos en de menor longitud en el árbol de los predecesores y mayores divisores del número x. Por ejemplo,
λ> caminosMinimales 6
[[6,3,2,1]]
λ> caminosMinimales 17
[[17,16,4,2,1]]
λ> caminosMinimales 50
[[50,25,5,4,2,1],[50,10,9,3,2,1],[50,10,5,4,2,1]]

Leer más…

Permutación de elementos consecutivos

Misceláneas

Definir la función

permutaConsecutivos :: [a] -> [a]

tal que (permutaConsecutivos xs) es la lista obtenida permutando los elementos consecutivos de xs. Por ejemplo,

permutaConsecutivos [1..8]         ==  [2,1,4,3,6,5,8,7]
permutaConsecutivos [1..9]         ==  [2,1,4,3,6,5,8,7,9]
permutaConsecutivos "simplemente"  ==  "ispmelemtne"

Leer más…

Cambio con el menor número de monedas

Misceláneas

El problema del cambio con el menor número de monedas consiste en, dada una lista ms de tipos de monedas (con infinitas monedas de cada tipo) y una cantidad objetivo x, calcular el menor número de monedas de ms cuya suma es x. Por ejemplo, con monedas de 1, 3 y 4 céntimos se puede obtener 6 céntimos de 4 formas

1, 1, 1, 1, 1, 1
1, 1, 1, 3
1, 1, 4
3, 3

El menor número de monedas que se necesita es 2. En cambio, con monedas de 2, 5 y 10 es imposible obtener 3.

Definir

monedas :: [Int] -> Int -> Maybe Int

tal que (monedas ms x) es el menor número de monedas de ms cuya suma es x, si es posible obtener dicha suma y es Nothing en caso contrario. Por ejemplo,

monedas [1,3,4]  6                    ==  Just 2
monedas [2,5,10] 3                    ==  Nothing
monedas [1,2,5,10,20,50,100,200] 520  ==  Just 4

Leer más…