Ir al contenido principal

Suma con redondeos

Misceláneas

Definir las funciones

sumaRedondeos       :: Integer -> [Integer]
limiteSumaRedondeos :: Integer -> Integer

tales que

  • (sumaRedondeos n) es la sucesión cuyo k-ésimo término es
redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k)

Por ejemplo,

take 5 (sumaRedondeos 1000)  ==  [500,750,875,937,968]
  • (limiteSumaRedondeos n) es la suma de la serie
redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ...

Por ejemplo,

limiteSumaRedondeos1 2000                    ==  1999
limiteSumaRedondeos1 2016                    ==  2016
limiteSumaRedondeos5 (10^308) `mod` (10^10)  ==  123839487

Leer más…

Elementos óptimos

Misceláneas

Definir la función

optimos :: Eq b => (b -> b -> Bool) -> (a -> b) -> [a] -> [a]

tal que (optimos r f xs) es la lista de los elementos de xs donde la función f alcanza sus valores óptimos respecto de la relación r. Por ejemplo,

optimos (<) length ["ab","c","de","f"]  ==  ["c","f"]
optimos (>) length ["ab","c","de","f"]  ==  ["ab","de"]

Leer más…

Elementos maximales

Misceláneas

Definir la función

maximales :: Eq a => (a -> a -> Bool) -> [a] -> [a]

tal que (maximales r xs) es la lista de los elementos de xs para los que no hay ningún otro elemento de xs mayor según la relación r. Por ejemplo,

maximales (>) [2,3,4,6]                     ==  [6]
maximales (<) [2,3,4,6]                     ==  [2]
maximales (\x y -> mod x y == 0) [2,3,4,6]  ==  [4,6]
maximales (\x y -> mod y x == 0) [2,3,4,6]  ==  [2,3]

Leer más…

Reconocimiento de anterior

Misceláneas

Definir la función

esAnterior :: Eq a => [a] -> a -> a -> Bool

tal que (esAnterior xs y z) se verifica si y ocurre en xs antes que z (que puede no pertenecer a xs). Por ejemplo,

esAnterior [1,3,7,2] 3 2  ==  True
esAnterior [1,3,7,2] 3 1  ==  False
esAnterior [1,3,7,2] 3 5  ==  True
esAnterior [1,3,7,2] 5 3  ==  False

Leer más…

Operación sobre todos los pares

Misceláneas

Definir la función

todosPares :: (a -> b -> c) -> [a] -> [b] -> [c]

tal que (todosPares f xs ys) es el resultado de aplicar la operación f a todos los pares de xs e ys. Por ejemplo,

todosPares (*) [2,3,5] [7,11]            == [14,22,21,33,35,55]
todosPares (\x y -> x:show y) "ab" [7,5] == ["a7","a5","b7","b5"]

Leer más…

Inserciones por posición

Misceláneas

Definir la función

inserta :: [a] -> [[a]] -> [[a]]

tal que (inserta xs yss) es la lista obtenida insertando

  • el primer elemento de xs como primero en la primera lista de yss,
  • el segundo elemento de xs como segundo en la segunda lista de yss (si la segunda lista de yss tiene al menos un elemento),
  • el tercer elemento de xs como tercero en la tercera lista de yss (si la tercera lista de yss tiene al menos dos elementos),

y así sucesivamente. Por ejemplo,

inserta [1,2,3] [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,3,8]]
inserta [1,2,3] [[4,7],[] ,[9,5,8]]  ==  [[1,4,7],[],   [9,5,3,8]]
inserta [1,2]   [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,8]]
inserta [1,2,3] [[4,7],[6]]          ==  [[1,4,7],[6,2]]
inserta "tad"   ["odo","pra","naa"]  ==  ["todo","para","nada"]

Leer más…

Árbol de Navidad

Misceláneas

Definir el procedimiento

arbol :: Int -> IO ()

tal que (arbol n) dibuja el árbol de Navidad con una copa de altura n y un tronco de altura la mitad de n. Por ejemplo,

λ> arbol 5

     X
    XXX
   XXXXX
  XXXXXXX
 XXXXXXXXX
     X
     X

λ> arbol 6

      X
     XXX
    XXXXX
   XXXXXXX
  XXXXXXXXX
 XXXXXXXXXXX
      X
      X
      X

λ> arbol 7

       X
      XXX
     XXXXX
    XXXXXXX
   XXXXXXXXX
  XXXXXXXXXXX
 XXXXXXXXXXXXX
       X
       X
       X

Leer más…

Siembra de listas

Misceláneas

Definir la función

siembra :: [Int] -> [Int]

tal que (siembra xs) es la lista ys obtenida al repartir cada elemento x de la lista xs poniendo un 1 en las x siguientes posiciones de la lista ys. Por ejemplo,

siembra [4]      ==  [0,1,1,1,1]
siembra [0,2]    ==  [0,0,1,1]
siembra [4,2]    ==  [0,1,2,2,1]

El tercer ejemplo se obtiene sumando la siembra de 4 en la posición 0 (como el ejemplo 1) y el 2 en la posición 1 (como el ejemplo 2). Otros ejemplos son

siembra [0,4,2]          ==  [0,0,1,2,2,1]
siembra [3]              ==  [0,1,1,1]
siembra [3,4,2]          ==  [0,1,2,3,2,1]
siembra [3,2,1]          ==  [0,1,2,3]
sum $ siembra [1..2500]  ==  3126250

Comprobar con QuickCheck que la suma de los elementos de (siembra xs) es igual que la suma de los de xs.

Nota: Se supone que el argumento es una lista de números no negativos y que se puede ampliar tanto como sea necesario para repartir los elementos.

Leer más…

Producto infinito

Misceláneas

Definir la función

productoInfinito :: [Int] -> [Int]

tal que (productoInfinito xs) es la lista infinita que en la posición N tiene el producto de los N primeros elementos de la lista infinita xs. Por ejemplo,

take 5 (productoInfinito [1..])    ==  [1,2,6,24,120]
take 5 (productoInfinito [2,4..])  ==  [2,8,48,384,3840]
take 5 (productoInfinito [1,3..])  ==  [1,3,15,105,945]

Nota: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.

Leer más…

Listas hermanadas

Misceláneas

Una lista hermanada es una lista de números estrictamente positivos en la que cada elemento tiene algún factor primo en común con el siguiente, en caso de que exista, o alguno de los dos es un 1. Por ejemplo,

  • [2,6,3,9,1,5] es una lista hermanada pues 2 y 6 tienen un factor en común (2); 6 y 3 tienen un factor en común (3); 3 y 9 tienen un factor en común (3); de 9 y 1 uno es el número 1; y de 1 y 5 uno es el número 1.
  • [2,3,5] no es una lista hermanada pues 2 y 3 no tienen ningún factor primo en común.

Definir la función

hermanada :: [Int] -> Bool

tal que (hermanada xs) se verifica si la lista xs es hermanada según la definición anterior. Por ejemplo,

hermanada [2,6,3,9,1,5]   ==  True
hermanada [2,3,5]         ==  False
hermanada [2,4..1000000]  ==  True

Nota: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.

Leer más…

Potencias perfectas

Misceláneas

Un número natural n es una potencia perfecta si existen dos números naturales m > 1 y k > 1 tales que n = m^k. Las primeras potencias perfectas son

4 = 2², 8 = 2³, 9 = 3², 16 = 2⁴, 25 = 5², 27 = 3³, 32 = 2⁵,
36 = 6², 49 = 7², 64 = 2⁶, ...

Definir la sucesión

potenciasPerfectas :: [Integer]

cuyos términos son las potencias perfectas. Por ejemplo,

take 10 potenciasPerfectas  ==  [4,8,9,16,25,27,32,36,49,64]
potenciasPerfectas !! 100   ==  6724

Definir el procedimiento

grafica :: Int -> IO ()

tal que (grafica n) es la representación gráfica de las n primeras potencias perfectas. Por ejemplo, para (grafica 30) dibuja

!Potencias perfectas](/images/Potencias_perfectas.png)

Leer más…

Factorizable respecto de una lista

Misceláneas

Definir la función

factorizable :: Integer -> [Integer] -> Bool

tal que (factorizable x ys) se verifica si x se puede escribir como producto de potencias de elementos de ys. Por ejemplo,

factorizable 1  [2,5,6]                           ==  True
factorizable 12 [2,5,3]                           ==  True
factorizable 12 [2,5,6]                           ==  True
factorizable 12 [7,5,12]                          ==  True
factorizable 12 [2,3,1]                           ==  True
factorizable 12 [2,3,0]                           ==  True
factorizable 24 [12,4,6]                          ==  True
factorizable 0  [2,3,0]                           ==  True
factorizable 12 [5,6]                             ==  False
factorizable 12 [2,5,1]                           ==  False
factorizable 0  [2,3,5]                           ==  False
factorizable (product [1..3000])     [1..100000]  ==  True
factorizable (1 + product [1..3000]) [1..100000]  ==  False

Leer más…

Año cúbico

Misceláneas

El año 2016 será un año cúbico porque se puede escribir como la suma de los cubos de 7 números consecutivos; en efecto,

2016 = 3³+ 4³ +...+ 9³

Definir la función

esCubico :: Integer -> Bool

tal que (esCubico x) se verifica si x se puede escribir como la suma de los cubos de 7 números consecutivos. Por ejemplo,

esCubico 2016                ==  True
esCubico 2017                ==  False
esCubico 189005670081900441  ==  True
esCubico 189005670081900442  ==  False

Leer más…

Primos con cubos

Misceláneas

Un primo con cubo es un número primo p para el que existe algún entero positivo n tal que la expresión n³ + n²p es un cubo perfecto. Por ejemplo, 19 es un primo con cubo ya que 8³ + 8²×19 = 12³.

Definir la sucesión

primosConCubos :: [Integer]

tal que sus elementos son los primos con cubo. Por ejemplo,

λ> take 6 primosConCubos
[7,19,37,61,127,271]
λ> length (takeWhile (< 1000000) primosConCubos)
173

Leer más…

Primos cubanos

Misceláneas

Un primo cubano es un número primo que se puede escribir como diferencia de dos cubos consecutivos. Por ejemplo, el 61 es un primo cubano porque es primo y 61 = 5³-4³.

Definir la sucesión

cubanos :: [Integer]

tal que sus elementos son los números cubanos. Por ejemplo,

λ> take 15 cubanos
[7,19,37,61,127,271,331,397,547,631,919,1657,1801,1951,2269]

Leer más…

Clausura transitiva de una relación binaria

Misceláneas

La clausura transitiva de una relación binaria R es la menor relación transitiva que contiene a R. Se puede calcular usando la composición de relaciones. Veamos un ejemplo, en el que (R ∘ S) representa la composición de R y S (definida en el ejercicio del lunes): sea

R = [(1,2),(2,5),(5,6)]

la relación R no es transitiva ya que (1,2) y (1,5) pertenecen a R pero (1,5) no pertenece; sea

R1 = R ∪ (R ∘ R)
= [(1,2),(2,5),(5,6),(1,5),(2,6)]

la relación R1 tampoco es transitiva ya que (1,2) y (2,6) pertenecen a R pero (1,6) no pertenece; sea

R2 = R1 ∪ (R1 ∘ R1)
= [(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]

La relación R2 es transitiva y contiene a R. Además, R2 es la clausura transitiva de R.

Definir la función

clausuraTransitiva :: Eq a => Rel a -> Rel a

tal que (clausuraTransitiva r) es la clausura transitiva de r. Por ejemplo,

λ> clausuraTransitiva [(1,2),(2,5),(5,6)]
[(1,2),(2,5),(5,6),(1,5),(2,6),(1,6)]
λ> clausuraTransitiva [(1,2),(2,5),(5,6),(6,3)]
[(1,2),(2,5),(5,6),(6,3),(1,5),(2,6),(5,3),(1,6),(2,3),(1,3)]

Leer más…

Transitividad de una relación

Misceláneas

Una relación binaria R sobre un conjunto A es transitiva cuando se cumple que siempre que un elemento se relaciona con otro y éste último con un tercero, entonces el primero se relaciona con el

Definir la función

transitiva :: Eq a => [(a,a)] -> Bool

tal que (transitiva r) se verifica si la relación r es transitiva. Por ejemplo,

transitiva [(1,1),(1,3),(3,1),(3,3),(5,5)]  ==  True
transitiva [(1,1),(1,3),(3,1),(5,5)]        ==  False

Leer más…

Composición de relaciones binarias

Misceláneas

Las relaciones binarias en un conjunto A se pueden representar mediante conjuntos de pares de elementos de A. Por ejemplo, la relación de divisibilidad en el conjunto {1,2,3,6} se representa por

[(1,1),(1,2),(1,3),(1,6),(2,2),(2,6),(3,3),(3,6),(6,6)]

La composición de dos relaciones binarias R y S en el conjunto A es la relación binaria formada por los pares (x,y) para los que existe un z tal que (x,z) ∈ R y (z,y) ∈ S.

Definir la función

composicion :: Eq a => [(a,a)] -> [(a,a)] -> [(a,a)]

tal que (composicion r s) es la composición de las relaciones binarias r y s. Por ejemplo,

λ> composicion [(1,2)] [(2,3),(2,4)]
[(1,3),(1,4)]
λ> composicion [(1,2),(5,2)] [(2,3),(2,4)]
[(1,3),(1,4),(5,3),(5,4)]
λ> composicion [(1,2),(1,4),(1,5)] [(2,3),(4,3)]
[(1,3)]
λ> composicion [(0,1)] [(2,3)]
[]

Nota: Se supone que las relaciones binarias son listas sin elementos repetidos.

Leer más…

Los números de Smith

Misceláneas

Un número de Smith es un número natural compuesto que cumple que la suma de sus dígitos es igual a la suma de los dígitos de todos sus factores primos (si tenemos algún factor primo repetido lo sumamos tantas veces como aparezca). Por ejemplo, el 22 es un número de Smith ya que

22  = 2*11 y
2+2 = 2+(1+1)

y el 4937775 también lo es ya que

4937775       = 3*5*5*65837 y
4+9+3+7+7+7+5 = 3+5+5+(6+5+8+3+7)

Definir las funciones

esSmith :: Integer -> Bool
smith :: [Integer]

tales que

  • (esSmith x) se verifica si x es un número de Smith. Por ejemplo,
esSmith 22          ==  True
esSmith 29          ==  False
esSmith 2015        ==  False
esSmith 4937775     ==  True
esSmith 4567597056  ==  True
  • smith es la lista cuyos elementos son los números de Smith. Por ejemplo,
λ> take 17 smith
[4,22,27,58,85,94,121,166,202,265,274,319,346,355,378,382,391]
λ> smith !! 2000
62158

Leer más…

Números de Armstrong

Misceláneas

Un número de n dígitos es un número de Armstrong si es igual a la suma de las n-ésimas potencias de sus dígitos. Por ejemplo, 371, 8208 y 4210818 son números de Armstrong ya que

    371 = 3^3 + 7^3 + 1^3
   8208 = 8^4 + 2^4 + 0^4 + 8^4
4210818 = 4^7 + 2^7 + 1^7 + 0^7 + 8^7 + 1^7 + 8^7

Definir las funciones

esArmstrong :: Integer -> Bool
armstrong :: [Integer]

tales que

  • (esArmstrong x) se verifica si x es un número de Armstrong. Por ejemplo,
esArmstrong 371                                      ==  True
esArmstrong 8208                                     ==  True
esArmstrong 4210818                                  ==  True
esArmstrong 2015                                     ==  False
esArmstrong 115132219018763992565095597973971522401  ==  True
esArmstrong 115132219018763992565095597973971522402  ==  False
  • armstrong es la lista cuyos elementos son los números de Armstrong. Por ejemplo,
λ> take 18 armstrong
[1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727]

Comprobar con QuickCheck que los números mayores que 115132219018763992565095597973971522401 no son números de Armstrong.

Leer más…

Raíces enteras de los números primos

Misceláneas

Definir la sucesión

raicesEnterasDePrimos :: [Integer]

cuyos elementos son las partes enteras de las raíces cuadradas de los números primos. Por ejemplo,

λ> take 30 raicesEnterasDePrimos
[1,1,2,2,3,3,4,4,4,5,5,6,6,6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,10,10]
λ> raicesEnterasDePrimos !!  9963
322
λ> raicesEnterasDePrimos !!  9964
323

Comprobar con QuickCheck que la diferencia entre dos términos consecutivos de la sucesión es como máximo igual a 1.

Leer más…

Paridad de un árbol

Misceláneas

Los árboles binarios con valores en las hojas y en los nodos se definen por

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

Por ejemplo, el árbol

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

se puede representar por

N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8))

Decimos que un árbol binario es par si la mayoría de sus nodos son pares e impar en caso contrario.

Para representar la paridad se define el tipo Paridad

data Paridad = Par | Impar deriving (Eq, Show)

Definir la función

paridad :: Arbol3 Int -> Paridad

tal que (paridad a) es la paridad del árbol a. Por ejemplo,

paridad (N 8 (N 6 (H 3) (H 4)) (H 5))  ==  Par
paridad (N 8 (N 9 (H 3) (H 4)) (H 5))  ==  Impar

Leer más…

Separación y mezcla de listas

Misceláneas

Definir las funciones

separacion :: [a] -> ([a],[a])
mezcla     :: ([a],[a]) -> [a]

tales que (separacion xs) es el par formado eligiendo alternativamente elementos de xs mientras que mezcla intercala los elementos de las dos listas. Por ejemplo,

separacion [1..5]                   ==  ([1,3,5],[2,4])
mezcla ([1,3,5],[2,4])              ==  [1,2,3,4,5]
separacion "Telescopio"             ==  ("Tlsoi","eecpo")
mezcla ("Tlsoi","eecpo")            ==  "Telescopio"
take 5 (fst (separacion [2,4..]))   ==  [2,6,10,14,18]
take 6 (mezcla ([2,4..],[7,14..]))  ==  [2,7,4,14,6,21]

Comprobar con QuickCheck que

mezcla (separacion xs) == xs

Leer más…

Particiones en k subconjuntos

Misceláneas

Definir la función

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

tal que (particiones xs k) es la lista de las particiones de xs en k subconjuntos disjuntos. Por ejemplo,

λ> particiones [2,3,6] 2
[[[2],[3,6]],[[2,3],[6]],[[3],[2,6]]]
λ> particiones [2,3,6] 3
[[[2],[3],[6]]]
λ> particiones [4,2,3,6] 3
[[[4],[2],[3,6]],[[4],[2,3],[6]],[[4],[3],[2,6]],
 [[4,2],[3],[6]],[[2],[4,3],[6]],[[2],[3],[4,6]]]
λ> particiones [4,2,3,6] 1
[[[4,2,3,6]]]
λ> particiones [4,2,3,6] 4
[[[4],[2],[3],[6]]]

Leer más…

Repeticiones según la posición

Misceláneas

Definir la función

transformada :: [a] -> [a]

tal que (transformada xs) es la lista obtenida repitiendo cada elemento tantas veces como indica su posición en la lista. Por ejemplo,

transformada [7,2,5] == [7,2,2,5,5,5]
transformada "eco"   == "eccooo"

Comprobar con QuickCheck si la transformada de una lista de n números enteros, con n >= 2, tiene menos de n^3 elementos.

Leer más…

Mayor semiprimo menor que n

Misceláneas

Un número semiprimo es un número natural que es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque ' 26 = 2*13' ) y 49 también lo es (porque 49 = 7*7).

Definir la función

mayorSemiprimoMenor :: Integer -> Integer

tal que (mayorSemiprimoMenor n) es el mayor semiprimo menor que n (suponiendo que n > 4). Por ejemplo,

mayorSemiprimoMenor 27      ==  26
mayorSemiprimoMenor 50      ==  49
mayorSemiprimoMenor 49      ==  46
mayorSemiprimoMenor (10^6)  ==  999997

Leer más…

Ganadores de las elecciones

Misceláneas

Los resultados de las votaciones a delegado en un grupo de clase se recogen mediante listas de asociación. Por ejemplo,

votos :: [(String,Int)]
votos = [("Ana Perez",10),("Juan Lopez",7), ("Julia Rus", 27),
         ("Pedro Val",1), ("Pedro Ruiz",27),("Berta Gomez",11)]

Definir la función

ganadores :: [(String,Int)] -> [String]

tal que (ganadores xs) es la lista de los estudiantes con mayor número de votos en xs. Por ejemplo,

ganadores votos == ["Julia Rus","Pedro Ruiz"]

Leer más…

Listas de igual longitud

Misceláneas

Definir la función

mismaLongitud :: [[a]] -> Bool

tal que (mismaLongitud xss) se verifica si todas las listas de la lista de listas xss tienen la misma longitud. Por ejemplo,

mismaLongitud [[1,2],[6,4],[0,0],[7,4]] == True
mismaLongitud [[1,2],[6,4,5],[0,0]]     == False

Leer más…

Ternas con suma acotada

Misceláneas

Definir la función

ternasAcotadas :: [Int] -> Int -> [(Int,Int,Int)]

tal que (ternasAcotadas xs n) es el conjunto de ternas de números naturales de xs cuya suma es menor que n. Por ejemplo,

ternasAcotadas [5,1,3,4,7] 12      ==  [(1,3,4),(1,3,5),(1,3,7),(1,4,5)]
ternasAcotadas [5,1,3,4,7] 11      ==  [(1,3,4),(1,3,5),(1,4,5)]
ternasAcotadas [5,1,3,4,7] 10      ==  [(1,3,4),(1,3,5)]
ternasAcotadas [5,1,3,4,7]  9      ==  [(1,3,4)]
ternasAcotadas [5,1,3,4,7]  8      ==  []
ternasAcotadas [1..10^6] 8         ==  [(1,2,3),(1,2,4)]
ternasAcotadas [10^6,10^6-1..1] 8  ==  [(1,2,3),(1,2,4)]

Leer más…

Subárboles monovalorados

Misceláneas

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

data Arbol = H Int
           | N Int Arbol Arbol
           deriving Show

Por ejemplo, el árbol

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

se puede representar por

N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))

Un árbol es monovalorado si todos sus elementos son iguales. Por ejemplo, de los siguientes árboles sólo son monovalorados los dos primeros

  5          9           5          9
 / \        / \         / \        / \
5   5      9   9       5   6      9   7
              / \                    / \
             9   9                  9   9

Definir la función

monovalorados :: Arbol -> [Arbol]

tal que (monovalorados a) es la lista de los subárboles monovalorados de a. Por ejemplo,

λ> monovalorados (N 5 (H 5) (H 5))
[N 5 (H 5) (H 5),H 5,H 5]
λ> monovalorados (N 5 (H 5) (H 6))
[H 5,H 6]
λ> monovalorados (N 9 (H 9) (N 9 (H 9) (H 9)))
[N 9 (H 9) (N 9 (H 9) (H 9)),H 9,N 9 (H 9) (H 9),H 9,H 9]
λ> monovalorados (N 9 (H 9) (N 7 (H 9) (H 9)))
[H 9,H 9,H 9]
λ> monovalorados (N 9 (H 9) (N 9 (H 7) (H 9)))
[H 9,H 7,H 9]

Leer más…

Intersecciones parciales

Misceláneas

Definir la función

interseccionParcial :: Eq a => Int -> [[a]] -> [a]

tal que (interseccionParcial n xss) es la lista de los elementos que pertenecen al menos a n conjuntos de xss. Por ejemplo,

interseccionParcial 1 [[3,4],[4,5,9],[5,4,7]]  == [3,4,5,9,7]
interseccionParcial 2 [[3,4],[4,5,9],[5,4,7]]  == [4,5]
interseccionParcial 3 [[3,4],[4,5,9],[5,4,7]]  == [4]
interseccionParcial 4 [[3,4],[4,5,9],[5,4,7]]  == []

Leer más…

Productos de N números consecutivos

Misceláneas

La semana pasada se planteó en Twitter el siguiente problema

Se observa que

1x2x3x4 = 2x3x4 2x3x4x5 = 4x5x6

¿Existen ejemplos de otros productos de cuatro enteros consecutivos iguales a un producto de tres enteros consecutivos?

Definir la función

esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer

tal que (esProductoDeNconsecutivos n x) es (Just m) si x es el producto de n enteros consecutivos a partir de m y es Nothing si x no es el producto de n enteros consecutivos. Por ejemplo,

esProductoDeNconsecutivos 3   6  == Just 1
esProductoDeNconsecutivos 4   6  == Nothing
esProductoDeNconsecutivos 4  24  == Just 1
esProductoDeNconsecutivos 3  24  == Just 2
esProductoDeNconsecutivos 3 120  == Just 4
esProductoDeNconsecutivos 4 120  == Just 2

Para ejemplos mayores,

λ> esProductoDeNconsecutivos 3 (product [10^20..2+10^20])
Just 100000000000000000000
λ> esProductoDeNconsecutivos2 4 (product [10^20..2+10^20])
Nothing
λ> esProductoDeNconsecutivos2 4 (product [10^20..3+10^20])
Just 100000000000000000000

Usando la función esProductoDeNconsecutivos resolver el problema.

Leer más…

Dígitos visibles y ocultos

Misceláneas

Una cadena clave es una cadena que contiene dígitos visibles y ocultos. Los dígitos se ocultan mediante las primeras letras minúsculas: la 'a' oculta el '0', la 'b' el '1' y así sucesivamente hasta la 'j' que oculta el '9'. Los restantes símbolos de la cadena no tienen significado y se pueden ignorar.

Definir la función

numeroOculto :: String -> Maybe Integer

tal que (numeroOculto cs) es justo el número formado por los dígitos visibles u ocultos de la cadena clave cs, si cs tiene dígitos y Nothing en caso contrario. Por ejemplo,

numeroOculto "jihgfedcba"      ==  Just 9876543210
numeroOculto "JIHGFEDCBA"      ==  Nothing
numeroOculto "el 23 de Enero"  ==  Just 423344
numeroOculto "El 23 de Enero"  ==  Just 23344
numeroOculto "El 23 de enero"  ==  Just 233444
numeroOculto "Todo para nada"  ==  Just 300030

Leer más…

Números muy pares

Misceláneas

Un entero positivo x es muy par si tanto x como x² sólo contienen cifras pares. Por ejemplo, 200 es muy par porque todas las cifras de 200 y 200² = 40000 son pares; pero 26 no lo es porque 26² = 767 tiene cifras impares.

Definir la función

siguienteMuyPar :: Integer -> Integer

tal que (siguienteMuyPar x) es menor número mayor que x que es muy par. Por ejemplo,

siguienteMuyPar 300           ==  668
siguienteMuyPar 668           ==  680
siguienteMuyPar 828268400000  ==  828268460602

Leer más…

Unión e intersección general de conjuntos.

Misceláneas

Definir las funciones

unionGeneral        :: Eq a => [[a]] -> [a]
interseccionGeneral :: Eq a => [[a]] -> [a]

tales que + (unionGeneral xs) es la unión de los conjuntos de la lista de conjuntos xs (es decir, el conjunto de los elementos que pertenecen a alguno de los elementos de xs). Por ejemplo,

unionGeneral []                    ==  []
unionGeneral [[1]]                 ==  [1]
unionGeneral [[1],[1,2],[2,3]]     ==  [1,2,3]
unionGeneral ([[x] | x <- [1..9]]) ==  [1,2,3,4,5,6,7,8,9]
  • (interseccionGeneral xs) es la intersección de los conjuntos de la lista de conjuntos xs (es decir, el conjunto de los elementos que pertenecen a todos los elementos de xs). Por ejemplo,
interseccionGeneral [[1]]                      ==  [1]
interseccionGeneral [[2],[1,2],[2,3]]          ==  [2]
interseccionGeneral [[2,7,5],[1,5,2],[5,2,3]]  ==  [2,5]
interseccionGeneral ([[x] | x <- [1..9]])      ==  []

Leer más…

Ceros finales del factorial

Misceláneas

Definir la función

cerosDelFactorial :: Integer -> Integer

tal que (cerosDelFactorial n) es el número de ceros en que termina el factorial de n. Por ejemplo,

cerosDelFactorial 24                           ==  4
cerosDelFactorial 25                           ==  6
length (show (cerosDelFactorial (1234^5678)))  ==  17552

Leer más…

Listas decrecientes

Misceláneas

Definir la función

listasDecrecientesDesde :: Int -> [[Int]]

tal que (listasDecrecientesDesde n) es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es n. Por ejemplo,

λ> listasDecrecientesDesde 2
[[2],[2,1],[2,1,0],[2,0]]
λ> listasDecrecientesDesde 3
[[3],[3,2],[3,2,1],[3,2,1,0],[3,2,0],[3,1],[3,1,0],[3,0]]

Leer más…

Números autodescriptivos

Misceláneas

Un número n es autodescriptivo cuando para cada posición k de n (empezando a contar las posiciones a partir de 0), el dígito en la posición k es igual al número de veces que ocurre k en n. Por ejemplo, 1210 es autodescriptivo porque tiene 1 dígito igual a "0", 2 dígitos iguales a "1", 1 dígito igual a "2" y ningún dígito igual a "3".

Definir la función

autodescriptivo :: Integer -> Bool

tal que (autodescriptivo n) se verifica si n es autodescriptivo. Por ejemplo,

λ> autodescriptivo 1210
True
λ> [x | x <- [1..100000], autodescriptivo x]
[1210,2020,21200]
λ> autodescriptivo 9210000001000
True

Leer más…

Primos gemelos próximos a múltiplos de 6

Misceláneas

Un par de números primos (p,q) es un par de números primos gemelos si su distancia de 2; es decir, si q = p+2. Por ejemplo, (17,19) es una par de números primos gemelos.

Se dice que un par de números (x,y) está próximo a un múltiplo de 6 si es de la forma (6n-1,6n+1). Por ejemplo, (17,19) está cerca de un múltiplo de 6 porque (17,19) = (6·3-1,6·3+1).

Definir las funciones

primosGemelos :: Integer -> [(Integer,Integer)]
primosGemelosNoProximosAmultiplosDe6 :: Integer -> [(Integer,Integer)]

tales que

  • (primosGemelos n) es la lista de los primos gemelos menores que n. Por ejemplo,
primosGemelos 50  == [(3,5),(5,7),(11,13),(17,19),(29,31),(41,43)]
primosGemelos 43  == [(3,5),(5,7),(11,13),(17,19),(29,31)]
  • (primosGemelosNoProximosAmultiplosDe6 n) es la lista de los primos gemelos menores que n que no están próximos a un múltiplo de 6. Por ejemplo,
primosGemelosNoProximosAmultiplosDe6 50               == [(3,5)]
length (primosGemelosNoProximosAmultiplosDe6' (10^9)) == 1

Leer más…

Capicúas productos de dos números de dos dígitos

Misceláneas

El número 9009 es capicúa y es producto de dos números de dos dígitos, pues 9009 = 91*99.

Definir la lista

capicuasP2N2D :: [Int]

cuyos elementos son los números capicúas que son producto de 2 números de dos dígitos. Por ejemplo,

take 5  capicuasP2N2D  ==  [121,242,252,272,323]
length  capicuasP2N2D  ==  74
drop 70 capicuasP2N2D  ==  [8008,8118,8448,9009]

Leer más…

Números muy divisibles por 3

Misceláneas

Se dice que un número n es muy divisible por 3 si es divisible por 3 y sigue siendo divisible por 3 si vamos quitando dígitos por la derecha. Por ejemplo, 96060 es muy divisible por 3 porque 96060, 9606, 960, 96 y 9 son todos divisibles por 3.

Definir las funciones

muyDivPor3             :: Integer -> Bool
numeroMuyDivPor3Cifras :: Integer -> Integer

tales que

  • (muyDivPor3 n) se verifica si n es muy divisible por 3. Por ejemplo,
muyDivPor3 96060 == True
muyDivPor3 90616 == False
  • (numeroMuyDivPor3CifrasC k) es la cantidad de números de k cifras muy divisibles por 3. Por ejemplo,
numeroMuyDivPor3Cifras 5                    == 768
numeroMuyDivPor3Cifras 7                    == 12288
numeroMuyDivPor3Cifras (10^6) `rem` (10^6)  ==  332032

Leer más…

Números libres de cuadrados

Misceláneas

Un número es libre de cuadrados si no es divisible el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.

Definir la función

libreDeCuadrados :: Integer -> Bool

tal que (libreDeCuadrados x) se verifica si x es libre de cuadrados. Por ejemplo,

libreDeCuadrados 70                    ==  True
libreDeCuadrados 40                    ==  False
libreDeCuadrados 510510                ==  True
libreDeCuadrados (((10^10)^10)^10)     ==  False

Leer más…

Aproximación del número pi

Misceláneas

Una forma de aproximar el número π es usando la siguiente igualdad: \[ \frac{\pi}{2} = 1 + \frac{1}{3} + \frac{1 \cdot 2}{3 \cdot 5} + \frac{1 \cdot 2 \cdot 3}{3 \cdot 5 \cdot 7} + \frac{1 \cdot 2 \cdot 3 \cdot 4}{3 \cdot 5 \cdot 7 \cdot 9} + \cdots \] Es decir, la serie cuyo término general n-ésimo es el cociente entre el producto de los primeros n números y los primeros n números impares: \[s(n) = \frac{\prod_{i=1}^{n} i}{\prod_{i=1}^{n} (2i + 1)}\]

Definir la función

aproximaPi :: Double -> Double

tal que (aproximaPi n) es la aproximación del número π calculada con la serie anterior hasta el término n-ésimo. Por ejemplo,

aproximaPi 10   ==  3.141106021601377
aproximaPi 30   ==  3.1415926533011587
aproximaPi 50   ==  3.1415926535897922

Leer más…

Factoriales iguales a su número de dígitos

Misceláneas

Se dice que un número n tiene un factorial especial si el número de dígitos de n! es igual a n. Por ejemplo, 22 tiene factorial especial porque 22! es 1124000727777607680000 que tiene 22 dígitos.

Definir la función

factorialesEspeciales :: [Integer]

tal que su valor es la lista de los números que tienen factoriales especiales. Por ejemplo,

take 2 factorialesEspeciales  ==  [1,22]

Nota: Si factorialesEspeciales es una lista finita, argumentar porqué no puede tener más elementos.

Leer más…

Próximos a múltiplos de 6

Misceláneas

Se dice que un par de números (x,y) está próximo a un múltiplo de 6 si es de la forma (6*n-1,6*n+1). Por ejemplo, (17,19) está cerca de un múltiplo de 6 porque (17,19) = (6*3-1,6*3+1).

Definir la función

proximosAmultiplosDe6 :: (Integer,Integer) -> Bool

tal que (proximosAmultiplosDe6 (x,y)) se verifica si el par (x,y) está próximo a un múltiplo de 6. Por ejemplo,

proximosAmultiplosDe6 (17,19)                          ==  True
proximosAmultiplosDe6 (18,20)                          ==  False
proximosAmultiplosDe6 (5,19)                           ==  False
proximosAmultiplosDe6 (1,3)                            ==  False
proximosAmultiplosDe6 (74074073407403,74074073407405)  ==  True
proximosAmultiplosDe6 (86419752308637,86419752308639)  ==  False

Leer más…

Diferencia simétrica

Misceláneas

La diferencia simétrica de dos conjuntos es el conjunto cuyos elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin pertenecer a ambos a la vez. Por ejemplo, la diferencia simétrica de {2,5,3} y {4,2,3,7} es {5,4,7}.

Definir la función

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

tal que (diferenciaSimetrica xs ys) es la diferencia simétrica de xs e ys. Por ejemplo,

diferenciaSimetrica [2,5,3] [4,2,3,7]    ==  [5,4,7]
diferenciaSimetrica [2,5,3] [5,2,3]      ==  []
diferenciaSimetrica [2,5,2] [4,2,3,7]    ==  [5,4,3,7]
diferenciaSimetrica [2,5,2] [4,2,4,7]    ==  [5,4,4,7]
diferenciaSimetrica [2,5,2,4] [4,2,4,7]  ==  [5,

Leer más…

Lista con repeticiones

Misceláneas

Definir la función

tieneRepeticiones :: Eq a => [a] -> Bool

tal que (tieneRepeticiones xs) se verifica si xs tiene algún elemento repetido. Por ejemplo,

tieneRepeticiones [3,2,5,2,7]          ==  True
tieneRepeticiones [3,2,5,4,7]          ==  False
tieneRepeticiones (5:[1..2000000000])  ==  True
tieneRepeticiones [1..20000]           ==  False

Leer más…

Mayor resto

Misceláneas

El resultado de dividir un número n por un divisor d es un cociente q y un resto r.

Definir la función

mayorResto :: Int -> Int -> (Int,[Int])

tal que (mayorResto n d) es el par (m,xs) tal que m es el mayor resto de dividir n entre x (con 1 ≤ x < d) y xs es la lista de números x menores que d tales que el resto de n entre x es m. Por ejemplo,

mayorResto 20 10  ==  (6,[7])
mayorResto 50 8   ==  (2,[3,4,6])

Nota: Se supone que d > 1.

Leer más…

Entero positivo con ciertas propiedades

Misceláneas

El 6 de octubre, se propuso en el blog Gaussianos el siguiente problema

Demostrar que para todo entero positivo n, existe otro entero positivo que tiene las siguientes propiedades:

  1. Tiene exactamente n dígitos.
  2. Ninguno de sus dígitos es 0.
  3. Es divisible por la suma de sus dígitos.

Definir la función

especiales :: Integer -> [Integer]

tal que (especiales n) es la lista de los números enteros que cumplen las 3 propiedades anteriores para n. Por ejemplo,

take 3 (especiales 2)  ==  [12,18,21]
take 3 (especiales 3)  ==  [111,112,114]
head (especiales 30)   ==  111111111111111111111111111125
length (especiales 3)  ==  108
null (especiales 1000) ==  False

En el primer ejemplo, 12 es un número especial para 2 ya que tiene exactamente 2 dígitos, ninguno de sus dígitos es 0 y 12 es divisible por la suma de sus dígitos.

Leer más…

Centro de masas

Misceláneas

El centro de masas de un sistema discreto es el punto geométrico que dinámicamente se comporta como si en él estuviera aplicada la resultante de las fuerzas externas al sistema.

Representamos un conjunto de n masas en el plano mediante una lista de n pares de la forma ((a(i),b(i)),m(i)) donde (a(i),b(i)) es la posición y m(i) la masa puntual. Las coordenadas del centro de masas (a,b) se calculan por

a = (a(1)·m(1) + a(2)·m(2) + ... + a(n)·m(n)) / (m(1) + m(2) +...+ m(n))
b = (b(1)·m(1) + b(2)·m(2) + ... + b(n)·m(n)) / (m(1) + m(2) +...+ m(n))

Definir la función

centrodeMasas :: [((Float,Float),Float)] -> (Float,Float)

tal que (centrodeMasas xs) es las coordenadas del centro de masas del sistema discreto xs. Por ejemplo:

centrodeMasas [((-1,3),2),((0,0),5),((1,3),3)] == (0.1,1.5)

Leer más…

Refinamiento de listas

Misceláneas

Definir la función

refinada :: [Float] -> [Float]

tal que (refinada xs) es la lista obtenida intercalando entre cada dos elementos consecutivos de xs su media aritmética. Por ejemplo,

refinada [2,7,1,8]  ==  [2.0,4.5,7.0,4.0,1.0,4.5,8.0]
refinada [2]        ==  [2.0]
refinada []         ==  []

Leer más…

Pandigitales tridivibles

Misceláneas

El número 4106357289 tiene la siguientes dos propiedades:

  • es pandigital, porque tiene todos los dígitos del 0 al 9 exactamente una vez y
  • es tridivisible, porque los sucesivos subnúmeros de tres dígitos (a partir del segundo) son divisibles por los sucesivos números primos; es decir, representado por d(i) el i-ésimo dígito, se tiene
d(2)d(3)d(4)  = 106 es divisible por 2
d(3)d(4)d(5)  = 063 es divisible por 3
d(4)d(5)d(6)  = 635 es divisible por 5
d(5)d(6)d(7)  = 357 es divisible por 7
d(6)d(7)d(8)  = 572 es divisible por 11
d(7)d(8)d(9)  = 728 es divisible por 13
d(8)d(9)d(10) = 289 es divisible por 17

Definir la constante

pandigitalesTridivisibles :: [Integer]

cuyos elementos son los números pandigitales tridivisibles. Por ejemplo,

head pandigitalesTridivisibles  ==  4106357289
sum pandigitalesTridivisibles   ==  16695334890

Leer más…

Pandigitales primos

Misceláneas

Un número con n dígitos es pandigital si contiene todos los dígitos del 1 a n exactamente una vez. Por ejemplo, 2143 es un pandigital con 4 dígitos y, además, es primo.

Definir la constante

pandigitalesPrimos :: [Int]

tal que sus elementos son los números pandigitales, ordenados de mayor a menor. Por ejemplo,

take 3 pandigitalesPrimos       ==  [7652413,7642513,7641253]
2143 `elem` pandigitalesPrimos  ==  True
length pandigitalesPrimos       ==  538

Leer más…

Codificación de Fibonacci

Misceláneas

La codificación de Fibonacci de un número n es una cadena d = d(0)d(1)...d(k-1)d(k) de ceros y unos tal que

n = d(0)·F(2) + d(1)·F(3) +...+ d(k-1)·F(k+1)
d(k-1) = d(k) = 1

donde F(i) es el i-ésimo término de la sucesión de Fibonacci.

0,1,1,2,3,5,8,13,21,34,...

Por ejemplo. La codificación de Fibonacci de 4 es "1011" ya que los dos últimos elementos son iguales a 1 y

1·F(2) + 0·F(3) + 1·F(4) = 1·1 + 0·2 + 1·3 = 4

La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla

 1  = 1     = F(2)           ≡       11
 2  = 2     = F(3)           ≡      011
 3  = 3     = F(4)           ≡     0011
 4  = 1+3   = F(2)+F(4)      ≡     1011
 5  = 5     = F(5)           ≡    00011
 6  = 1+5   = F(2)+F(5)      ≡    10011
 7  = 2+5   = F(3)+F(5)      ≡    01011
 8  = 8     = F(6)           ≡   000011
 9  = 1+8   = F(2)+F(6)      ≡   100011
10  = 2+8   = F(3)+F(6)      ≡   010011
11  = 3+8   = F(4)+F(6)      ≡   001011
12  = 1+3+8 = F(2)+F(4)+F(6) ≡   101011
13  = 13    = F(7)           ≡  0000011
14  = 1+13  = F(2)+F(7)      ≡  1000011

Definir la función

codigoFib :: Integer -> String

tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,

λ> codigoFib 65
"0100100011"
λ> [codigoFib n | n <- [1..7]]
["11","011","0011","1011","00011","10011","01011"]

Leer más…

Partición por longitudes

Misceláneas

Definir la función

particion :: [a] -> [Int] -> [[a]]

tal que (particion xs ns) es la partición de xs donde la longitud de cada parte está determinada por los elementos de ns. Por ejemplo,

particion [1..10] [2,5,0,3]  ==  [[1,2],[3,4,5,6,7],[],[8,9,10]]
particion [1..10] [1,4,2,3]  ==  [[1],[2,3,4,5],[6,7],[8,9,10]]

Leer más…

Máximos de una lista

Misceláneas

Definir la función

maximos :: Ord a => [a] -> [a]

tal que (maximos xs) es la lista de los elementos de xs que son mayores que todos sus anteriores. Por ejemplo,

maximos [1,-3,5,2,3,4,7,6,7]                         ==  [1,5,7]
maximos "bafcdegag"                                  ==  "bfg"
maximos (concat (replicate (10^6) "adxbcde")++"yz")  ==  "adxyz"
length (maximos [1..10^6])                           ==  1000000

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]

Nota: La relación entre la sucesión y el funcionamiento del reloj se puede ver en The Mathematics Behind Prague's Horloge Introduction.

Leer más…

Menor n tal que el primo n-ésimo cumple una propiedad

Misceláneas

Sea p(n) el n-ésimo primo y sea r el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2. Por ejemplo,

si n = 3, entonces p(3) =  5 y r = ( 4^3 +  6^3) mod  (5^2) =   5
si n = 7, entonces p(7) = 17 y r = (16^7 + 18^7) mod (17^2) = 238

Definir la función

menorPR :: Integer -> Integer

tal que (menorPR x) es el menor n tal que el resto de dividir (p(n)-1)^n + (p(n)+1)^n por p(n)^2 es mayor que x. Por ejemplo,

menorPR 100     == 5
menorPR 345     == 9
menorPR 1000    == 13
menorPR (10^9)  == 7037
menorPR (10^10) == 21035
menorPR (10^12) == 191041

Leer más…

Polinomio cromático de un grafo

Misceláneas

El polinomio cromático de un grafo calcula el número de maneras en las cuales puede ser coloreado el grafo usando un número de colores dado, de forma que dos vértices adyacentes no tengan el mismo color.

En el caso del grafo completo de n vértices, su polinomio cromático es

P(n,x) = x(x-1)(x-2) ... (x-(n-1))

Por ejemplo,

P(3,x) = x(x-1)(x-2)      = x^3 - 3·x^2 + 2·x
P(4,x) = x(x-1)(x-2)(x-3) = x^4 - 6·x^3 + 11·x^2 - 6·x

Lo que significa que P(4)(x) es el número de formas de colorear el grafo completo de 4 vértices con x colores. Por tanto,

P(4,2) =  0 (no se puede colorear con 2 colores)
P(4,4) = 24 (hay 24 formas de colorearlo con 4 colores)

Definir la función

polGC:: Int -> Polinomio Int

tal que (polGC n) es el polinomio cromático del grafo completo de n vértices. Por ejemplo,

polGC 4  ==  x^4 + -6*x^3 + 11*x^2 + -6*x
polGC 5  ==  x^5 + -10*x^4 + 35*x^3 + -50*x^2 + 24*x

Comprobar con QuickCheck que si el número de colores (x) coincide con el número de vértices del grafo (n), el número de maneras de colorear el grafo es n!.

Nota 1. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación

λ> quickCheckWith (stdArgs {maxSize=7}) prop_polGC
+++ OK, passed 100 tests.

Nota 2: Este ejercicio debe realizarse usando únicamente las funciones de la librería de polinomios (I1M.PolOperaciones) que aquí.

Leer más…

Suma de posteriores

Misceláneas

Definir la función

sumaPosteriores :: [Int] -> [Int]

tal que (sumaPosteriores xs) es la lista obtenida sustituyendo cada elemento de xs por la suma de los elementos posteriores. Por ejemplo,

sumaPosteriores [1..8]        == [35,33,30,26,21,15,8,0]
sumaPosteriores [1,-3,2,5,-8] == [-4,-1,-3,-8,0]

Comprobar con QuickCheck que el último elemento de la lista (sumaPosteriores xs) siempre es 0.

Leer más…

Algoritmo de bajada para resolver un sistema triangular inferior

Misceláneas

Un sistema de ecuaciones lineales Ax = b es triangular inferior si todos los elementos de la matriz A que están por encima de la diagonal principal son nulos; es decir, es de la forma

a(1,1)·x(1)                                               = b(1)
a(2,1)·x(1) + a(2,2)·x(2)                                 = b(2)
a(3,1)·x(1) + a(3,2)·x(2) + a(3,3)·x(3)                   = b(3)
...
a(n,1)·x(1) + a(n,2)·x(2) + a(n,3)·x(3) +...+ a(x,x)·x(n) = b(n)

El sistema es compatible si, y sólo si, el producto de los elementos de la diagonal principal es distinto de cero. En este caso, la solución se puede calcular mediante el algoritmo de bajada:

x(1) = b(1) / a(1,1)
x(2) = (b(2) - a(2,1)·x(1)) / a(2,2)
x(3) = (b(3) - a(3,1)·x(1) - a(3,2)·x(2)) / a(3,3)
...
x(n) = (b(n) - a(n,1)·x(1) - a(n,2)·x(2) -...- a(n,n-1)·x(n-1)) / a(n,n)

Definir la función

bajada :: Matrix Double -> Matrix Double -> Matrix Double

tal que (bajada a b) es la solución, mediante el algoritmo de bajada, del sistema compatible triangular superior ax = b. Por ejemplo,

λ> let a = fromLists [[2,0,0],[3,1,0],[4,2,5.0]]
λ> let b = fromLists [[3],[6.5],[10]]
λ> bajada a b
( 1.5 )
( 2.0 )
( 0.0 )

Es decir, la solución del sistema

2x            = 3
3x + y        = 6.5
4x + 2y + 5 z = 10

es x=1.5, y=2 y z=0.

Leer más…

Mayor producto de n números adyacentes en una matriz

Misceláneas

Definir la función

mayorProductoAdyacentes :: (Num a, Ord a) => Int -> Matriz a -> [[a]]

tal que (mayorProductoAdyacentes n p) es la lista de los segmentos formados por n elementos adyacentes en la misma fila, columna o diagonal de la matriz p cuyo productos son máximo. Por ejemplo,

λ> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1..12])
[[10,11,12]]
λ> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1])
[[3,7,9]]
λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,3,4, 0,3,2])
[[3,4],[4,3]]
λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,0,3])
[[2,3],[2,3]]
λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,2,1, 3,4,3])
[[3,4],[4,3]]
λ> mayorProductoAdyacentes 2 (listArray ((1,1),(2,3)) [1,5,1, 3,4,3])
[[5,4]]
λ> mayorProductoAdyacentes 3 (listArray ((1,1),(3,4)) [1,3,4,5, 0,7,2,1, 3,9,2,1])
[[3,7,9]]

Leer más…

Método de bisección para encontrar raíces de funciones

Misceláneas

El método de bisección para calcular un cero de una función en el intervalo [a,b] se basa en el teorema de Bolzano:

Si f(x) es una función continua en el intervalo [a, b], y si, además, en los extremos del intervalo la función f(x) toma valores de signo opuesto (f(a) * f(b) < 0), entonces existe al menos un valor c en (a, b) para el que f(c) = 0".

El método para calcular un cero de la función f en el intervalo [a,b] con un error menor que e consiste en tomar el punto medio del intervalo c = (a+b)/2 y considerar los siguientes casos:

  • Si |f(c)| < e, hemos encontrado una aproximación del punto que anula f en el intervalo con un error aceptable.
  • Si f(c) tiene signo distinto de f(a), repetir el proceso en el intervalo [a,c].
  • Si no, repetir el proceso en el intervalo [c,b].

Definir la función

biseccion :: (Double -> Double) -> Double -> Double -> Double -> Double

tal que (biseccion f a b e) es una aproximación del punto del intervalo [a,b] en el que se anula la función f, con un error menor que e, calculada mediante el método de la bisección. Por ejemplo,

biseccion (\x -> x^2 - 3) 0 5 0.01             ==  1.7333984375
biseccion (\x -> x^3 - x - 2) 0 4 0.01         ==  1.521484375
biseccion cos 0 2 0.01                         ==  1.5625
biseccion (\x -> log (50-x) - 4) (-10) 3 0.01  ==  -5.125

Leer más…

Números para los que mcm de 1,2,...n-1 coincide con el de 1,2,...,n

Misceláneas

Un número n es especial si mcm(1,2,...,n-1) = mcm(1,2,...,n). Por ejemplo, el 6 es especial ya que

mcm(1,2,3,4,5) = 60 = mcm(1,2,3,4,5,6)

Definir la sucesión

especiales :: [Integer]

cuyos términos son los números especiales. Por ejemplo,

take 10 especiales     ==  [1,6,10,12,14,15,18,20,21,22]
especiales !! 50       ==  84
especiales !! 500      ==  638
especiales !! 5000     ==  5806
especiales !! 50000    ==  55746

Leer más…

Cálculo aproximado de integrales definidas

Misceláneas

La integral definida de una función f entre los límites a y b puede calcularse mediante la regla del rectángulo usando la fórmula \[ h \cdot \left( f\left(a + \frac{h}{2}\right) + f\left(a + h + \frac{h}{2}\right) + f\left(a + 2h + \frac{h}{2}\right) + \dots + f\left(a + nh + \frac{h}{2}\right) \right) \] con \[ a + n h + \frac{h}{2} \leq b < a + (n+1) h + \frac{h}{2} \] y usando valores pequeños para \(h\).

Definir la función

integral :: (Fractional a, Ord a) => a -> a -> (a -> a) -> a -> a

tal que (integral a b f h) es el valor de dicha expresión. Por ejemplo, el cálculo de la integral de f(x) = x^3 entre 0 y 1, con paso 0.01, es

integral 0 1 (^3) 0.01  ==  0.24998750000000042

Otros ejemplos son

integral 0 1 (^4) 0.01                   ==  0.19998333362500048
integral 0 1 (\x -> 3*x^2 + 4*x^3) 0.01  ==  1.9999250000000026
log 2 - integral 1 2 (\x -> 1/x) 0.01         ==  3.124931644782336e-6
pi - 4 * integral 0 1 (\x -> 1/(x^2+1)) 0.01  ==  -8.333333331389525e-6

Leer más…

Menor número con una cantidad de divisores dada

Misceláneas

El menor número con 2¹ divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) sólo tiene 1 divisor (el 1).

El menor número con 2² divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).

El menor número con 2³ divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.

El menor número con 2⁴ divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.

El menor número, módulo 100, con 2⁴ divisores es el 20, ya que el menor número con 16 divisores es el 120 y 120 módulo 100 es 20.

Definir la función

menor :: Integer -> Integer -> Integer

tal que (menor n m) es el menor número, módulo m, con 2^n divisores; es decir, es el resto de dividir entre m el menor número con 2^n divisores. Por ejemplo,

menor 4 1000                    ==  120
menor 4 100                     ==  20
[menor n (10^9) | n <- [1..8]]  ==  [2,6,24,120,840,7560,83160,1081080]
menor 500500 500500506          ==  8728302

Leer más…

Distancia esperada entre dos puntos de un cuadrado unitario

Misceláneas

Definir, por simulación, la función

distanciaEsperada :: Int -> Double

tal que (distanciaEsperada n) es la distancia esperada entre n puntos del cuadrado unitario de vértices opuestos (0,0) y (1,1), elegidos aleatoriamente. Por ejemplo,

distanciaEsperada 10    ==  0.4815946544198219
distanciaEsperada 10    ==  0.5558438642543654
distanciaEsperada 100   ==  0.5699663553203216
distanciaEsperada 100   ==  0.5085629461572269
distanciaEsperada 1000  ==  0.5376963424746385
distanciaEsperada 1000  ==  0.523432374720393

Nota. El valor exacto de la distancia esperada es

(sqrt(2) + 2 + 5*log(1+sqrt(2)))/15 = 0.5214054331647207

Leer más…

Caminos en un grafo

Misceláneas

Definir las funciones

grafo   :: [(Int,Int)] -> Grafo Int Int
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

  • (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,
λ> grafo [(2,4),(4,5)]
G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])
  • (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
[[1,3,5,7],[1,3,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
[[2,5,3,7],[2,5,7]]
λ> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
[[1,3,5,2],[1,3,7,5,2]]
λ> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
[]
λ> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
109601

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo).

Leer más…

Problema de las bolas de Dijkstra

Misceláneas

En el juego de las bolas de Dijkstra se dispone de una bolsa con bolas blancas y negras. El juego consiste en elegir al azar dos bolas de la bolsa y añadir una bola negra si las dos bolas elegidas son del mismo color o una bola blanca en caso contrario. El juego termina cuando queda sólo una bola en la bolsa.

Vamos a representar las bolas blancas por 0, las negras por 1 y la bolsa la representaremos por una lista cuyos elementos son 0 ó 1.

Definir las funciones

juego  :: [Int] -> [[Int]]
ultima :: [Int] -> Int

tales que

  • (juego xs) es la lista de los pasos aleatorios de un juego de Dijkstra a partir de la lista xs. Por ejemplo,
juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[1,1,0,0],[1,1,1],[1,1],[1]]
juego [1,1,0,0,1]  ==  [[1,1,0,0,1],[0,1,1,0],[0,0,1],[1,1],[1]]
juego [1,0,0,0,1]  ==  [[1,0,0,0,1],[0,0,0,1],[0,1,1],[1,0],[0]]
juego [1,0,1,1,1]  ==  [[1,0,1,1,1],[1,1,0,1],[1,0,1],[0,1],[0]]
  • (ultima xs) es la bola que queda en la bolsa al final del juego de Dijkstra a partir de xs. Por ejemplo,
ultima [1,1,0,0,1]  ==  1
ultima [1,0,0,0,1]  ==  0
ultima [1,0,1,1,1]  ==  0

Comprobar con QuickCheck que la bola que queda en la bolsa al final del juego de Dijkstra es blanca si, y sólo si, el número de bolas blancas en la bolsa inicial es impar.

Leer más…

Matrices latinas

Misceláneas

Una matriz latina de orden n es una matriz cuadrada de orden n tal que todos sus elementos son cero salvo los de su fila y columna central, si n es impar; o los de sus dos filas y columnas centrales, si n es par.

Definir la función

latina :: Int -> Array (Int,Int) Int

tal que (latina n) es la siguiente matriz latina de orden n:

  • Para n impar:
| 0  0... 0 1   0 ... 0   0|
| 0  0... 0 2   0 ... 0   0|
| 0  0... 0 3   0 ... 0   0|
| .........................|
| 1  2..............n-1   n|
| .........................|
| 0  0... 0 n-2 0 ... 0   0|
| 0  0... 0 n-1 0 ... 0   0|
| 0  0... 0 n   0 ... 0   0|
  • Para n par:
| 0  0... 0 1   n    0 ...   0   0|
| 0  0... 0 2   n-1  0 ...   0   0|
| 0  0... 0 3   n-2  0 ...   0   0|
| ................................|
| 1  2.....................n-1   n|
| n n-1 .................... 2   1|
| ................................|
| 0  0... 0 n-2  3   0 ...   0   0|
| 0  0... 0 n-1  2   0 ...   0   0|
| 0  0... 0 n    1   0 ...   0   0|

Por ejemplo,

λ> elems (latina 5)
[0,0,1,0,0,
 0,0,2,0,0,
 1,2,3,4,5,
 0,0,4,0,0,
 0,0,5,0,0]
λ> elems (latina 6)
[0,0,1,6,0,0,
 0,0,2,5,0,0,
 1,2,3,4,5,6,
 6,5,4,3,2,1,
 0,0,5,2,0,0,
 0,0,6,1,0,0]

Leer más…

Refinamiento de montículos

Misceláneas

Definir la función

refina :: Ord a => Monticulo a -> [a -> Bool] -> Monticulo a

tal que (refina m ps) es el montículo formado por los elementos del montículo m que cumplen todos los predicados de la lista ps. Por ejemplo,

λ> refina (foldr inserta vacio [1..22]) [(<7), even]
M 2 1 (M 4 1 (M 6 1 Vacio Vacio) Vacio) Vacio
λ> refina (foldr inserta vacio [1..22]) [(<1), even]
Vacio

Leer más…

Cálculo de aprobados

Misceláneas

La notas de un examen se pueden representar mediante un vector en el que los valores son los pares formados por los nombres de los alumnos y sus notas.

Definir la función

aprobados :: (Num a, Ord a) => Array Int (String,a) -> Maybe [String]

tal que (aprobados p) es la lista de los nombres de los alumnos que han aprobado y Nothing si todos están suspensos. Por ejemplo,

λ> aprobados (listArray (1,3) [("Ana",5),("Pedro",3),("Lucia",6)])
Just ["Ana","Lucia"]
λ> aprobados (listArray (1,3) [("Ana",4),("Pedro",3),("Lucia",4.9)])
Nothing

Leer más…

Reparto de escaños por la ley d'Hont

Misceláneas

El sistema D'Hondt es una fórmula electoral, creada por Victor d'Hondt, que permite obtener el número de cargos electos asignados a las candidaturas, en proporción a los votos conseguidos.

Tras el recuento de los votos, se calcula una serie de divisores para cada partido. La fórmula de los divisores es V/N, donde V representa el número total de votos recibidos por el partido, y N representa cada uno de los números enteros desde 1 hasta el número de cargos electos de la circunscripción objeto de escrutinio. Una vez realizadas las divisiones de los votos de cada partido por cada uno de los divisores desde 1 hasta N, la asignación de cargos electos se hace ordenando los cocientes de las divisiones de mayor a menor y asignando a cada uno un escaño hasta que éstos se agoten

Definir la función

reparto :: Int -> [Int] -> [(Int,Int)]

tal que (reparto n vs) es la lista de los pares formados por los números de los partidos y el número de escaño que les corresponden al repartir n escaños en función de la lista de sus votos. Por ejemplo,

λ> reparto 7 [340000,280000,160000,60000,15000]
[(1,3),(2,3),(3,1)]
λ> reparto 21 [391000,311000,184000,73000,27000,12000,2000]
[(1,9),(2,7),(3,4),(4,1)]

es decir, en el primer ejemplo,

  • al 1º partido (que obtuvo 340000 votos) le corresponden 3 escaños,
  • al 2º partido (que obtuvo 280000 votos) le corresponden 3 escaños,
  • al 3º partido (que obtuvo 160000 votos) le corresponden 1 escaño.

Leer más…

Inversiones de un número

Misceláneas

Un número tiene una inversión cuando existe un dígito x a la derecha de otro dígito de forma que x es menor que y. Por ejemplo, en el número 1745 hay dos inversiones ya que 4 es menor que 7 y 5 es menor que 7 y están a la derecha de 7.

Definir la función

nInversiones :: Integer -> Int

tal que (nInversiones n) es el número de inversiones de n. Por ejemplo,

nInversiones 1745  ==  2

Leer más…

Números comenzando con un dígito dado

Misceláneas

Definir la función

comienzanCon :: [Int] -> Int -> [Int]

tal que (comienzanCon xs d) es la lista de los elementos de xs que empiezan por el dígito d. Por ejemplo,

comienzanCon [123,51,11,711,52] 1 == [123,11]
comienzanCon [123,51,11,711,52] 5 == [51,52]
comienzanCon [123,51,11,711,52] 6 == []

Leer más…

Matrices marco y transiciones

Misceláneas

Las posiciones frontera de una matriz de orden mxn son aquellas que están en la fila 1 o la fila m o la columna 1 o la columna n. El resto se dirán posiciones interiores. Observa que cada elemento en una posición interior tiene exactamente 8 vecinos en la matriz.

Dada una matriz, un paso de transición genera una nueva matriz de la misma dimensión pero en la que se ha sustituido cada elemento interior por la suma de sus 8 vecinos. Los elementos frontera no varían.

Definir las funciones

marco      :: Int -> Int -> Integer -> Matrix Integer
paso       :: Matrix Integer -> Matrix Integer
itPasos    :: Int -> Matrix Integer -> Matrix Integer
pasosHasta :: Integer -> Int

tales que

  • (marco m n z) genera la matriz de dimensión mxn que contiene el entero z en las posiciones frontera y 0 en las posiciones interiores. Por ejemplo,
λ> marco 5 5 1
( 1 1 1 1 1 )
( 1 0 0 0 1 )
( 1 0 0 0 1 )
( 1 0 0 0 1 )
( 1 1 1 1 1 )
  • (paso t) calcula la matriz generada tras aplicar un paso de transición a la matriz t. Por ejemplo,
λ> paso (marco 5 5 1)
( 1 1 1 1 1 )
( 1 5 3 5 1 )
( 1 3 0 3 1 )
( 1 5 3 5 1 )
( 1 1 1 1 1 )
  • (itPasos k t) es la matriz obtenida tras aplicar k pasos de transición a partir de la matriz t. Por ejemplo,
λ> itPasos 10 (marco 5 5 1)
(       1       1       1       1       1 )
(       1 4156075 5878783 4156075       1 )
(       1 5878783 8315560 5878783       1 )
(       1 4156075 5878783 4156075       1 )
(       1       1       1       1       1 )
  • (pasosHasta k) es el número de pasos de transición a partir de la matriz (marco 5 5 1) necesarios para que en la matriz resultante aparezca un elemento mayor que k. Por ejemplo,
pasosHasta 4         ==  1
pasosHasta 6         ==  2
pasosHasta (2^2015)  ==  887

Leer más…

Parte par de un polinomio

Misceláneas

La parte par de un polinomio de coeficientes enteros es el polinomio formado por sus monomios cuyos coeficientes son números pares. Por ejemplo, la parte par de 4x^3+x^2-7x+6 es 4x^3+6.

Definir la función

partePar :: Integral a => Polinomio a -> Polinomio a

tal que (partePar p) es la parte par de p. Por ejemplo,

λ> partePar (consPol 3 4 (consPol 2 1 (consPol 0 6 polCero)))
4*x^3 + 6

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería I1M.Pol que se encuentra aquí y se describe aquí.

Leer más…

Aplicación de funciones a nodos y hojas

Misceláneas

Representamos los árboles binarios con elementos en las hojas y en los nodos mediante el tipo de dato

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

Definir la función

aplica :: (a -> a) -> (a -> a) -> Arbol a -> Arbol a

tal que (aplica f g a) devuelve el árbol obtenido al aplicar la función f a las hojas del árbol a y la función g a los nodos interiores. Por ejemplo,

λ> aplica (+1)(*2) (N 5 (N 2 (H 1) (H 2)) (N 3 (H 4) (H 2)))
N 10 (N 4 (H 2) (H 3)) (N 6 (H 5) (H 3))

Leer más…

Ciclos de un grafo

Misceláneas

Un ciclo en un grafo G es una secuencia [v(1),v(2),v(3),...,v(n)] de nodos de G tal que:

  • (v(1),v(2)), (v(2),v(3)), (v(3),v(4)), ..., (v(n-1),v(n)) son aristas de G,
  • v(1) = v(n), y
  • salvo v(1) = v(n), todos los v(i) son distintos entre sí.

Definir la función

ciclos :: Grafo Int Int -> [[Int]]

tal que (ciclos g) es la lista de ciclos de g. Por ejemplo, si g1 y g2 son los grafos definidos por

g1, g2 :: Grafo Int Int
g1 = creaGrafo D (1,4) [(1,2,0),(2,3,0),(2,4,0),(4,1,0)]
g2 = creaGrafo D (1,4) [(1,2,0),(2,1,0),(2,4,0),(4,1,0)]

entonces

ciclos g1  ==  [[1,2,4,1],[2,4,1,2],[4,1,2,4]]
ciclos g2  ==  [[1,2,1],[1,2,4,1],[2,1,2],[2,4,1,2],[4,1,2,4]]

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Leer más…

Números alternados

Misceláneas

Decimos que un número es alternado si no tiene dos cifras consecutivas iguales ni tres cifras consecutivas en orden creciente no estricto o decreciente no estricto. Por ejemplo, los números 132425 y 92745 son alternados, pero los números 12325 y 29778 no. Las tres primeras cifras de 12325 están en orden creciente y 29778 tiene dos cifras iguales consecutivas.

Definir la constante

alternados :: [Integer]

cuyo valor es la lista infinita de los números alternados. Por ejemplo,

take 10 alternados                      ==  [0,1,2,3,4,5,6,7,8,9]
length (takeWhile (< 1000) alternados)  ==  616
alternados !! 1234567                   ==  19390804

Leer más…

Visibilidad de listas y matrices

Misceláneas

La visibilidad de una lista es el número de elementos que son estrictamente mayores que todos los anteriores. Por ejemplo, la visibilidad de la lista [1,2,5,2,3,6] es 4.

La visibilidad de una matriz P es el par formado por las visibilidades de las filas de P y las visibilidades de las columnas de P. Por ejemplo, dada la matriz

    ( 4 2 1 )
Q = ( 3 2 5 )
    ( 6 1 8 )

la visibilidad de Q es ([1,2,2],[2,1,3]).

Definir las funciones

visibilidadLista  :: [Int] -> Int
visibilidadMatriz :: Matrix Int -> ([Int],[Int])

tales que

  • (visibilidadLista xs) es la visibilidad de la lista xs. Por ejemplo,
visibilidadLista [1,2,5,2,3,6]   ==  4
visibilidadLista [0,-2,5,1,6,6]  ==  3
+ (visibilidadMatriz p) es la visibilidad de la matriz p. Por ejemplo,
~~~haskell
λ> visibilidadMatriz (fromLists [[4,2,1],[3,2,5],[6,1,8]])
([1,2,2],[2,1,3])
λ> visibilidadMatriz (fromLists [[0,2,1],[0,2,5],[6,1,8]])
([2,3,2],[2,1,3])

Leer más…

Reconocimiento de camino en un grafo

Misceláneas

Dado un grafo no dirigido G, un camino en G es una secuencia de nodos [v(1),v(2),v(3),...,v(n)] tal que para todo i entre 1 y n-1, (v(i),v(i+1)) es una arista de G. Por ejemplo, dados los grafos

g1, g2 :: Grafo Int Int
g1 = creaGrafo ND (1,3) [(1,2,0),(1,3,0),(2,3,0)]
g2 = creaGrafo ND (1,4) [(1,2,0),(1,3,0),(1,4,0),(2,4,0),(3,4,0)]

la lista [1,2,3] es un camino en g1, pero no es un camino en g2 puesto que la arista (2,3) no existe en g2.

Definir la función

camino :: Grafo Int Int -> [Int] -> Bool

tal que (camino g vs) se verifica si la lista de nodos vs es un camino en el grafo g. Por ejemplo,

camino g1 [1,2,3]  ==  True
camino g2 [1,2,3]  ==  False

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de grafos (I1M.Grafo) que se describe aquí y se encuentra aquí.

Leer más…

El teorema de Midy

Misceláneas

El ejercicio de hoy tiene como objetivo comprobar la veracidad del Teorema de Midy:

Sea a/p una fracción, donde a < p y p > 5 es un número primo. Si esta fracción tiene una expansión decimal periódica, donde la cantidad de dígitos en el período es par, entonces podemos partir el período en dos mitades, cuya suma es un número formado únicamente por nueves.

Por ejemplo, 2/7 = 0'285714285714... El período es 285714, cuya longitud es par (6). Lo partimos por la mitad y las sumamos: 285+714 = 999.

Definir la función

teoremaMidy :: Integer -> Bool

tal que (teoremaMidy n) se verifica si para todo todo número primo p menor que n y mayor que 5 y todo número natural menor que p tales que la cantidad de dígitos en el período de a/p es par, entonces podemos partir el período de a/p en dos mitades, cuya suma es un número formado únicamente por nueves. Por ejemplo,

teoremaMidy 200  ==  True

Además, comprobar el teorema de Midy usando QuickCheck.

Leer más…

Representación decimal de números racionales

Misceláneas

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

 6/2  = 3                  se representa por (3,[],[])
 1/2  = 0.5                se representa por (0,[5],[])
 1/3  = 0.333333...        se representa por (0,[],[3])
23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

type Decimal = (Integer,[Integer],[Integer])

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

type Racional = (Integer,Integer)

Definir las funciones

decimal  :: Racional -> Decimal
racional :: Decimal -> Racional

tales que

  • (decimal r) es la representación decimal del número racional r. Por ejemplo,
decimal (1,4)    ==  (0,[2,5],[])
decimal (1,3)    ==  (0,[],[3])
decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])
  • (racional d) es el número racional cuya representación decimal es d. Por ejemplo,
racional (0,[2,5],[])           ==  (1,4)
racional (0,[],[3])             ==  (1,3)
racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

λ> let (_,_,p) = decimal (23,14) in concatMap show p
"428571"
λ> let (_,_,p) = decimal (1,47) in concatMap show p
"0212765957446808510638297872340425531914893617"
λ> let (_,_,p) = decimal (1,541) in length (concatMap show p)
540

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

Leer más…

Potencias de primos con exponentes potencias de dos

Misceláneas

Se llaman potencias de Fermi-Dirac a los números de la forma p^(2^k), donde p es un número primo y k es un número natural.

Definir la sucesión

potencias :: [Integer]

cuyos términos sean las potencias de Fermi-Dirac ordenadas de menor a mayor. Por ejemplo,

take 14 potencias    ==  [2,3,4,5,7,9,11,13,16,17,19,23,25,29]
potencias !! 60      ==  241
potencias !! (10^6)  ==  15476303

Leer más…

Múltiplos especiales

Misceláneas

Dado dos números n y m, decimos que m es un múltiplo especial de n si m es un múltiplo de n y m no tiene ningún factor primo que sea congruente con 1 módulo 3.

Definir la función

multiplosEspecialesCota :: Int -> Int -> [Int]

tal que (multiplosEspecialesCota n k) es la lista ordenada de todos los múltiplos especiales de n que son menores o iguales que k. Por ejemplo,

multiplosEspecialesCota 5 50  ==  [5,10,15,20,25,30,40,45,50]
multiplosEspecialesCota 7 50  ==  []

Leer más…

Mínimo y máximo de un montículo

Misceláneas

Definir la función

minMax :: Ord a => Monticulo a -> Maybe (a,a)

tal que (minMax m) es justamente el par formado por el menor y el mayor elemento de m, si el montículo m es no vacío. Por ejemplo,

minMax (foldr inserta vacio [4,8,2,1,5])  ==  Just (1,8)
minMax (foldr inserta vacio [4])          ==  Just (4,4)
minMax vacio                              ==  Nothing

Nota: Este ejercicio debe realizarse usando únicamente las funciones de la librería de montículo (I1M.Monticulo) que se encuentra aquí.

Leer más…

Representación matricial de relaciones binarias

Misceláneas

Dada una relación r sobre un conjunto de números enteros, la matriz asociada a r es una matriz booleana p (cuyos elementos son True o False), tal que p(i,j) = True si y sólo si i está relacionado con j mediante la relación r.

Las relaciones binarias homogéneas y las matrices booleanas se pueden representar por

type Relacion = ([Int],[(Int,Int)])
type Matriz = Array (Int,Int) Bool

Definir la función

matrizRB:: Relacion -> Matriz

tal que (matrizRB r) es la matriz booleana asociada a r. Por ejemplo,

λ> matrizRB ([1..3],[(1,1), (1,3), (3,1), (3,3)])
array ((1,1),(3,3)) [((1,1),True) ,((1,2),False),((1,3),True),
                     ((2,1),False),((2,2),False),((2,3),False),
                     ((3,1),True) ,((3,2),False),((3,3),True)]
λ> matrizRB ([1..3],[(1,3), (3,1)])
array ((1,1),(3,3)) [((1,1),False),((1,2),False),((1,3),True),
                     ((2,1),False),((2,2),False),((2,3),False),
                     ((3,1),True) ,((3,2),False),((3,3),False)]
λ> let n = 10^4 in matrizRB3 ([1..n],[(1,n),(n,1)]) ! (n,n)
False

Leer más…

Números cuyos dígitos coinciden con los de sus factores primos

Misceláneas

Un número n es especial si al unir los dígitos de sus factores primos, se obtienen exactamente los dígitos de n, aunque puede ser en otro orden. Por ejemplo, 1255 es especial, pues los factores primos de 1255 son 5 y 251.

Definir la función

esEspecial :: Integer -> Bool

tal que (esEspecial n) se verifica si un número n es especial. Por ejemplo,

esEspecial 1255 == True
esEspecial 125  == False

Comprobar con QuickCheck que todo número primo es especial.

Calcular los 5 primeros números especiales que no son primos.

Leer más…

Codificación de Gödel

Misceláneas

Dada una lista de números naturales xs, la codificación de Gödel de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los elementos de xs. Por ejemplo, si xs = [6,0,4], la codificación de xs es

2^6 * 3^0 * 5^4 = 64 * 1 * 625 = 40000.

Definir las funciones

codificaG   :: [Integer] -> Integer
decodificaG :: Integer -> [Integer]

tales que

  • (codificaG xs) es la codificación de Gödel de xs. Por ejemplo,
codificaG [6,0,4]           == 40000
codificaG [3,1,1]           == 120
codificaG [3,1,0,0,0,0,0,1] == 456
codificaG [1..6]            == 4199506113235182750
  • (decodificaG n) es la lista xs cuya codificación es n. Por ejemplo,
decodificaG 40000               == [6,0,4]
decodificaG 120                 == [3,1,1]
decodificaG 456                 == [3,1,0,0,0,0,0,1]
decodificaG 4199506113235182750 == [1,2,3,4,5,6]

Comprobar con QuickCheck que ambas funciones son inversas.

Leer más…

Agrupamiento de consecutivos iguales

Misceláneas

Definir las funciones

agrupa  :: Eq a => [a] -> [(a,Int)]
expande :: [(a,Int)] -> [a]

tales que

  • (agrupa xs) es la lista obtenida agrupando las ocurrencias consecutivas de elementos de xs junto con el número de dichas ocurrencias. Por ejemplo:
agrupa "aaabzzaa" == [('a',3),('b',1),('z',2),('a',2)]
  • (expande xs) es la lista expandida correspondiente a ps (es decir, es la lista xs tal que la comprimida de xs es ps. Por ejemplo,
expande [('a',2),('b',3),('a',1)] == "aabbba"

Comprobar con QuickCheck que dada una lista de enteros, si se la agrupa y después se expande se obtiene la lista inicial.

Leer más…

Colinealidad de una lista de puntos

Misceláneas

Una colección de puntos son colineales si esxiste una línea recta tal que todos están en dicha línea. Por ejemplo, los puntos (2,1), (5,7), (4,5) y (20,37) son colineales porque pertenecen a la línea y = 2*x-3.

Definir la función

colineales :: [(Int,Int)] -> Bool

tal que (colineales ps) se verifica si los puntos de la lista ps son colineales. Por ejemplo,

colineales [(2,1),(5,7),(4,5),(20,37)]  ==  True
colineales [(2,1),(5,7),(4,5),(21,37)]  ==  False

Leer más…

Distancia invierte y suma hasta capicúa

Misceláneas

Un número es capicúa si es igual leído de izquierda a derecha que de derecha a izquierda; por ejemplo, el 4884.

El transformado "invierte y suma" de un número x es la suma de x y su número invertido; es decir, el número resultante de la inversión del orden en el que aparecen sus dígitos. Por ejemplo, el transformado de 124 es 124 + 421 = 545.

Se aplica la transformación "invierte y suma" hasta obtener un capicúa. Por ejemplo, partiendo del número 87, el proceso es

  87 +   78 =  165
 165 +  561 =  726
 726 +  627 = 1353
1353 + 3531 = 4884

El número de pasos de dicho proceso es la distancia capicúa del número; por ejemplo, la distancia capicúa de 87 es 4.

Definir la función

distanciaIS :: Integer -> Integer

tal que (distanciaIS x) es la distancia capicúa de x. Por ejemplo,

distanciaIS 11                   ==    0
distanciaIS 10                   ==    1
distanciaIS 19                   ==    2
distanciaIS 59                   ==    3
distanciaIS 69                   ==    4
distanciaIS 166                  ==    5
distanciaIS 79                   ==    6
distanciaIS 89                   ==   24
distanciaIS 10911                ==   55
distanciaIS 1000000079994144385  ==  259

Leer más…

Primos circulares

Misceláneas

Un primo circular es un número tal que todas las rotaciones de sus dígitos producen números primos. Por ejemplo, 195 es un primo circular ya que las rotaciones de sus dígitos son 197, 971 y 719 y los tres números son primos.

Definir la constante

circulares :: [Integer]

cuyo valor es la lista de los números primos circulares. Por ejemplo,

take 12 circulares  ==  [2,3,5,7,11,13,17,31,37,71,73,79]
circulares !! 50    ==  939193

Leer más…

Diccionario de frecuencias

Misceláneas

Definir la función

frecuencias :: Ord a => [a] -> Map a Int

tal que (frecuencias xs) es el diccionario formado por los elementos de xs junto con el número de veces que aparecen en xs. Por ejemplo,

λ> frecuencias "sosos"
fromList [('o',2),('s',3)]
λ> frecuencias (show (10^100))
fromList [('0',100),('1',1)]
λ> frecuencias (take (10^6) (cycle "abc"))
fromList [('a',333334),('b',333333),('c',333333)]
λ> size (frecuencias (take (10^6) (cycle [1..10^6])))
1000000

Leer más…