Ir al contenido principal

Máxima longitud de sublistas crecientes

Misceláneas

Definir la función

longitudMayorSublistaCreciente :: Ord a => [a] -> Int

tal que (longitudMayorSublistaCreciente xs) es la el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]
3
λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]
6
λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
6
λ> longitudMayorSublistaCreciente [1..2000]
2000
λ> longitudMayorSublistaCreciente [2000,1999..1]
1
λ> import System.Random
λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
λ> longitudMayorSublistaCreciente2 xs
61
λ> longitudMayorSublistaCreciente3 xs
61

Leer más…

Diagonales invertidas

Misceláneas

Definir la función

diagonalesInvertidas :: Matrix a -> Matrix a

tal que (diagonalesInvertidas q) es la matriz obtenida invirtiendo el orden de los elementos de la diagonal principal y de la diagonal secundaria de q. Por ejemplo,

λ> fromList 5 5 [1..]
┌                ┐
│  1  2  3  4  5 │
│  6  7  8  9 10 │
│ 11 12 13 14 15 │
│ 16 17 18 19 20 │
│ 21 22 23 24 25 │
└                ┘
λ> diagonalesInvertidas (fromList 5 5 [1..])
┌                ┐
│ 25  2  3  4 21 │
│  6 19  8 17 10 │
│ 11 12 13 14 15 │
│ 16  9 18  7 20 │
│  5 22 23 24  1 │
└                ┘
λ> fromList 3 3 ['a','b'..]
┌             ┐
│ 'a' 'b' 'c' │
│ 'd' 'e' 'f' │
│ 'g' 'h' 'i' │
└             ┘
λ> diagonalesInvertidas (fromList 3 3 ['a','b'..])
┌             ┐
│ 'i' 'b' 'g' │
│ 'd' 'e' 'f' │
│ 'c' 'h' 'a' │
└             ┘

Leer más…

Números cíclopes

Misceláneas

Un número cíclope es un número natural cuya representación binaria sólo tiene un cero en el centro. Por ejemplo,

  0      es ciclope porque su representación binaria es 0
  1   no es ciclope porque su representación binaria es 1
  5      es ciclope porque su representación binaria es 101
  9   no es ciclope porque su representación binaria es 1001
 10   no es ciclope porque su representación binaria es 1010
 27      es ciclope porque su representación binaria es 11011
 85   no es ciclope porque su representación binaria es 1010101
101   no es ciclope porque su representación binaria es 1100101
111   no es ciclope porque su representación binaria es 1101111
119      es ciclope porque su representación binaria es 1110111

Definir las funciones

esCiclope       :: Integer -> Bool
ciclopes        :: [Integer]
graficaCiclopes :: Int -> IO ()

tales que

  • (esCiclope n) se verifica si el número natual n es cíclope. Por ejemplo,
esCiclope 0    ==  True
esCiclope 1    ==  False
esCiclope 5    ==  True
esCiclope 9    ==  False
esCiclope 10   ==  False
esCiclope 27   ==  True
esCiclope 85   ==  False
esCiclope 101  ==  False
esCiclope 111  ==  False
esCiclope 119  ==  True
  • ciclopes es la lista de los número cíclopes. Por ejemplo,
λ> take 12 ciclopes
[0,5,27,119,495,2015,8127,32639,130815,523775,2096127,8386559]
λ> length (show (ciclopes !! (10^5)))
60207
  • (graficaCiclopes n) dibuja la gráfica del último dígito de los n primeros números cíclopes. Por ejemplo, (graficaCiclopes n) dibuja

Números cíclopes

Leer más…

Combinaciones divisibles

Misceláneas

Definir la función

tieneCombinacionDivisible :: [Int] -> Int -> Bool

tal que (tieneCombinacionDivisible xs m) se verifica si existe alguna forma de combinar todos los elementos de la lista (con las operaciones suma o resta) de forma que el resultado sea divisible por m. Por ejemplo,

tieneCombinacionDivisible [1,3,4,6] 4  ==  True
tieneCombinacionDivisible [1,3,9]   2  ==  False

En el primer ejemplo, 1 - 2 + 3 + 4 + 6 = 12 es una combinación divisible por 4. En el segundo ejemplo, las combinaciones de [1,3,9] son

 1 + 3 + 9 =  13
-1 + 3 + 9 =  11
 1 - 3 + 9 =   7
-1 - 3 + 9 =   5
 1 + 3 - 9 =  -5
-1 + 3 - 9 =  -7
 1 - 3 - 9 = -11
-1 - 3 - 9 = -13

y ninguna de las 4 es divisible por 2.

Leer más…

Camino de máxima suma en una matriz

Misceláneas

(  1  6 11  2 )
(  7 12  3  8 )
(  3  8  4  9 )

moviéndose en cada paso una casilla hacia abajo o hacia la derecha, son los siguientes:

1, 7,  3, 8, 4, 9
1, 7, 12, 8, 4, 9
1, 7, 12, 3, 4, 9
1, 7, 12, 3, 8, 9
1, 6, 12, 8, 4, 9
1, 6, 12, 3, 4, 9
1, 6, 12, 3, 8, 9
1, 6, 11, 3, 4, 9
1, 6, 11, 3, 8, 9
1, 6, 11, 2, 8, 9

Las sumas de los caminos son 32, 41, 36, 40, 40, 35, 39, 34, 38 y 37, respectivamente. El camino de máxima suma es el segundo (1, 7, 12, 8, 4, 9) que tiene una suma de 41.

Definir la función

caminoMaxSuma :: Matrix Int -> [Int]

tal que (caminoMaxSuma m) es un camino de máxima suma en la matriz m desde el extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia abajo o hacia la derecha. Por ejemplo,

λ> caminoMaxSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
[1,7,12,8,4,9]
λ> sum (caminoMaxSuma3 (fromList 800 800 [1..]))
766721999
(1.68 secs, 1,082,106,856 bytes)

Leer más…

Suma de segmentos iniciales

Misceláneas

Los segmentos iniciales de [3,1,2,5] son [3], [3,1], [3,1,2] y [3,1,2,5]. Sus sumas son 3, 4, 6 y 9, respectivamente. La suma de dichas sumas es 24.

Definir la función

sumaSegmentosIniciales :: [Integer] -> Integer

tal que (sumaSegmentosIniciales xs) es la suma de las sumas de los segmentos iniciales de xs. Por ejemplo,

sumaSegmentosIniciales [3,1,2,5]     ==  24
sumaSegmentosIniciales3 [1..3*10^6]  ==  4500004500001000000

Comprobar con QuickCheck que la suma de las sumas de los segmentos iniciales de la lista formada por n veces el número uno es el n-ésimo número triangular; es decir que

sumaSegmentosIniciales (genericReplicate n 1)

es igual a

n * (n + 1) `div` 2

Leer más…

Números como suma de sus dígitos

Misceláneas

El número 23 se puede escribir de 4 formas como suma de sus dígitos

2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3
2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 3 + 3
2 + 2 + 2 + 2 + 3 + 3 + 3 + 3 + 3
2 + 3 + 3 + 3 + 3 + 3 + 3 + 3

La de menor número de sumando es la última, que tiene 8 sumandos.

Definir las funciones

minimoSumandosDigitos        :: Integer -> Integer
graficaMinimoSumandosDigitos :: Integer -> IO ()

tales que

  • (minimoSumandosDigitos n) es el menor número de dígitos de n cuya suma es n. Por ejemplo,
minimoSumandosDigitos 23    ==  8
minimoSumandosDigitos 232   ==  78
minimoSumandosDigitos 2323  ==  775
  • (graficaMinimoSumandosDigitos n) dibuja la gráfica de (minimoSumandosDigitos k) par los k primeros números naturales. Por ejemplo, (graficaMinimoSumandosDigitos 300) dibuja

Números como suma de sus dígitos

Leer más…

Las torres de Hanói

Misceláneas

Las torres de Hanoi es un rompecabeza que consta de tres postes que llamaremos A, B y C. Hay N discos de distintos tamaños en el poste A, de forma que no hay un disco situado sobre otro de menor tamaño. Los postes B y C están vacíos. Sólo puede moverse un disco a la vez y todos los discos deben de estar ensartados en algún poste. Ningún disco puede situarse sobre otro de menor tamaño. El problema consiste en colocar los N discos en el poste C.

Los postes se pueden representar mediante el siguiente tipo de datos

data Poste = A | B | C
  deriving Show

Definir las funciones

movimientos :: Integer -> [(Integer,Poste,Poste)]
hanoi       :: Integer -> IO ()

tales que

  • (movimientos n) es la lista de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,
λ> movimientos 1
[(1,A,C)]
λ> movimientos 2
[(1,A,B),(2,A,C),(1,B,C)]
λ> movimientos 3
[(1,A,C),(2,A,B),(1,C,B),(3,A,C),(1,B,A),(2,B,C),(1,A,C)]
  • (hanoi n) escribe los mensajes de los movimientos para resolver el problema de las torres de hanoi con n discos. Por ejemplo,
λ> hanoi 3
Mueve el disco 1 de A a C
Mueve el disco 2 de A a B
Mueve el disco 1 de C a B
Mueve el disco 3 de A a C
Mueve el disco 1 de B a A
Mueve el disco 2 de B a C
Mueve el disco 1 de A a C

Leer más…

Número de descomposiciones en sumas de cuatro cuadrados

Misceláneas

Definir la función

nDescomposiciones       :: Int -> Int
graficaDescomposiciones :: Int -> IO ()

tales que

  • (nDescomposiciones x) es el número de listas de los cuadrados de cuatro números enteros positivos cuya suma es x. Por ejemplo.
nDescomposiciones 4      ==  1
nDescomposiciones 5      ==  0
nDescomposiciones 7      ==  4
nDescomposiciones 10     ==  6
nDescomposiciones 15     ==  12
nDescomposiciones 50000  ==  5682
  • (graficaDescomposiciones n) dibuja la gráfica del número de descomposiciones de los n primeros números naturales. Por ejemplo, (graficaDescomposiciones 500) dibuja

Número de descomposiciones en sumas de cuatro cuadrados

Leer más…