Ir al contenido principal

Caminos desde la raíz en un árbol binario

Misceláneas

Los árboles binarios se pueden representar con el de tipo de dato algebraico

data Arbol = H
           | N Int Arbol Arbol
  deriving Show

Por ejemplo, los árboles

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

se representan por

ej1, ej2 :: Arbol
ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))

Definir la función

caminosDesdeRaiz :: Arbol -> [[Int]]

tal que (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la raíz de a hasta cualquiera de sus nodos. Por ejemplo.

λ> caminosDesdeRaiz ej1
[[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5]]
λ> caminosDesdeRaiz ej2
[[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]]

Leer más…

Prefijo con suma acotada

Misceláneas

Definir la función

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

tal que (prefijoAcotado x ys) es el mayor prefijo de ys cuya suma es menor que x. Por ejemplo,

prefijoAcotado 10 [3,2,5,7]  ==  [3,2]
prefijoAcotado 10 [1..]      ==  [1,2,3]

Leer más…

Aplicaciones de operaciones

Misceláneas

Definir la función

aplicaciones :: [a -> b -> c] -> [a] -> [b] -> [c]

tal que (aplicaciones os xs ys) es la lista obtenida aplicando las operaciones de os a los elementos de xs es ys. Por ejemplo,

λ> aplicaciones [(+),(*)] [1,2] [5,8]
[6,9,7,10,5,8,10,16]
λ> aplicaciones [(+),(*)] [1,2] [5]
[6,7,5,10]
λ> aplicaciones [(<),(>)] ["ab","c"] ["def","c"]
[True,True,True,False,False,False,False,False]
λ> import Data.List
λ> aplicaciones [(++),intersect] ["ab","c"] ["bd","cf"]
["abbd","abcf","cbd","ccf","b","","","c"]

Leer más…

Sucesión de Cantor de números innombrables

Misceláneas

Un número es innombrable si es divisible por 7 o alguno de sus dígitos es un 7. Un juego infantil consiste en contar saltándose los números innombrables:

1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

La sucesión de Cantor se obtiene llenando los huecos de la sucesión anterior como se indica a continuación:

1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41  (9) 43
44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
(2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
(25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
(30) 99 100

Definir la sucesión

sucCantor :: [Integer]

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

λ> take 100 sucCantor
[1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,
 22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,
 40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,
 13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,
 20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,
 6, 92,93,94,95,96, 29, 30 ,99,100]

λ> sucCantor2 !! (5+10^6)
544480

λ> sucCantor2 !! (6+10^6)
266086

Leer más…

Particiones de una lista

Misceláneas

Definir la función

particiones :: [a] -> [[[a]]]

tal que (particiones xs) es la lista de las particiones de xs en segmentos de elementos consecutivos. Por ejemplo,

λ> particiones [1..3]
[[[1],[2],[3]],[[1],[2,3]],[[1,2],[3]],[[1,2,3]]]
λ> mapM_ print (particiones "abcd")
["a","b","c","d"]
["a","b","cd"]
["a","bc","d"]
["a","bcd"]
["ab","c","d"]
["ab","cd"]
["abc","d"]
["abcd"]
λ> length (particiones [1..22])
2097152

Comprobar con QuickCheck que la concatenación de cada uno de los elementos de (particiones xs) es igual a xs.

Nota: En la comprobación usar ejemplos pequeños como se indica a continuación

quickCheckWith (stdArgs {maxSize=10}) prop_particiones

Leer más…

Subrayado de un carácter

Misceláneas

Definir el procedimiento

subraya :: String -> Char -> IO ()

tal que (subraya cs c) escribe la cadena cs y debajo otra subrayando las ocurrencias de c. Por ejemplo,

λ> subraya "Salamanca es castellana" 'a'
Salamanca es castellana
 ^ ^ ^  ^     ^     ^ ^
λ> subraya "Salamanca es castellana" 'n'
Salamanca es castellana
      ^              ^
λ> subraya "Salamanca es castellana" ' '
Salamanca es castellana
         ^  ^

Leer más…

Eliminación de triplicados

Misceláneas

Definir la función

sinTriplicados :: Eq a => [a] -> [a]

tal que (sinTriplicados xs) es la lista obtenida dejando en xs sólo las dos primeras ocurrencias de cada uno de sus elementos. Por ejemplo,

sinTriplicados "aaabcbccdbabdcd"  ==  "aabcbcdd"
sinTriplicados "xxxxx"            ==  "xx"
sinTriplicados "abcabc"           ==  "abcabc"
sinTriplicados "abcdabcaba"       ==  "abcdabc"
sinTriplicados "abacbadcba"       ==  "abacbdc"
sinTriplicados "aaabcbccdbabdcd"  ==  "aabcbcdd"
sinTriplicados (show (5^4^3))     ==  "54210108624757363989"
sinTriplicados (show (8^8^8))     ==  "60145207536139279488"

Leer más…

Máximo producto de pares en la lista.

Misceláneas

Definir la función

maximoProducto :: [Int] -> Maybe Int

tal que (maximoProducto xs) es el mayor elemento de xs que se puede escribir como producto de dos elementos distintos de xs o Nothing, en el caso de que ningún elemento de xs se pueda escribir como producto de dos elementos distintos de xs, donde xs es una lista de números mayores que 0. Por ejemplo,

maximoProducto [10, 3, 5, 30, 35]       ==  Just 30
maximoProducto [10, 2, 2, 4, 30, 35]    ==  Just 4
maximoProducto [17, 2, 1, 35, 30]       ==  Just 35
maximoProducto [2,4]                    ==  Nothing
maximoProducto [2, 5, 7, 8]             ==  Nothing
maximoProducto [10, 2, 4, 30, 35]       ==  Nothing
maximoProducto [1+2^n | n <- [1..10^6]] ==  Just 4611686018427387905

En el primer ejemplo, 30 es el producto de 10 y 3; en el segundo, 4 es el producto de 2 y 2 y en el tercero, 35 es el producto de 1 y 35.

Leer más…

Suma minimal de productos de pares de elementos consecutivos

Misceláneas

Al permutar los elementos de la lista [1,2,3,4] se obtienen los siguientes valores de la suma de pares de elementos consecutivos:

  • 10, por ejemplo con [1,4,2,3] ya que 1x4+2x3 = 10
  • 11, por ejemplo con [1,3,2,4] ya que 1x3+2x4 = 11
  • 14, por ejemplo con [1,2,3,4] ya que 1x2+3x4 = 14

Por tanto, la mínima suma de los productos de elementos consecutivos en las permutaciones de [1,2,3,4] es 10 y una permutación con dicha suma es [1,4,2,3].

Definir las funciones

minimaSumaProductos  :: (Num a, Ord a) => [a] -> a
permutacionMinimal   :: (Num a, Ord a) => [a] -> [a]

tales que

  • (minimaSumaProductos xs) es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,
minimaSumaProductos [1..4]             ==  10
minimaSumaProductos [3,2,5,7,1,6]      ==  34
minimaSumaProductos [9,2,8,4,5,7,6,0]  ==  74
minimaSumaProductos [1,2,1,4,0,5,6,0]  ==  6
  • (permutacionMinimal xs) es una permutación de xs cuya suma de productos de elementos consecutivos de xs es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,
permutacionMinimal [1..4]             ==  [1,4,3,2]
permutacionMinimal [3,2,5,7,1,6]      ==  [1,7,2,6,3,5]
permutacionMinimal [9,2,8,4,5,7,6,0]  ==  [0,9,2,8,4,7,5,6]
permutacionMinimal [1,2,1,4,0,5,6,0]  ==  [0,6,0,5,1,4,1,2]

Leer más…

Máxima potencia que divide al factorial

Misceláneas

La máxima potencia de 2 que divide al factorial de 5 es 3, ya que 5! = 120, 120 es divisible por 2^3 y no lo es por 2^4.

Definir la función

maxPotDivFact :: Integer -> Integer -> Integer

tal que (maxPotDivFact p n), para cada primo p, es el mayor k tal que p^k divide al factorial de n. Por ejemplo,

maxPotDivFact 2 5       ==  3
maxPotDivFact 3 6       ==  2
maxPotDivFact 2 10      ==  8
maxPotDivFact 3 10      ==  4
maxPotDivFact 2 (10^2)  ==  97
maxPotDivFact 2 (10^3)  ==  994
maxPotDivFact 2 (10^4)  ==  9995
maxPotDivFact 2 (10^5)  ==  99994
maxPotDivFact 2 (10^6)  ==  999993
maxPotDivFact 3 (10^5)  ==  49995
maxPotDivFact 3 (10^6)  ==  499993
maxPotDivFact 7 (10^5)  ==  16662
maxPotDivFact 7 (10^6)  ==  166664
length (show (maxPotDivFact 2 (10^20000)))  ==  20000

Leer más…