El tipo de los árboles binarios se define por

data Arbol = H Int
           | N Int Arbol Arbol

Por ejemplo, el árbol

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

se define por

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

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

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

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

Definir la función

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

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

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

Leer más…

Los polinomios pueden representarse mediante listas. Por ejemplo, el polinomio x^5+3x^4-5x^2+x-7 se representa por [1,3,0,-5,1,-7]. En dicha lista, obviando el cero, se producen tres cambios de signo: del 3 al -5, del -5 al 1 y del 1 al -7. Llamando C(p) al número de cambios de signo en la lista de coeficientes del polinomio p(x), tendríamos entonces que en este caso C(p)=3.

La regla de los signos de Descartes dice que el número de raíces reales positivas de una ecuación polinómica con coeficientes reales igualada a cero es, como mucho, igual al número de cambios de signo que se produzcan entre sus coeficientes (obviando los ceros). Por ejemplo, en el caso anterior la ecuación tendría como mucho tres soluciones reales positivas, ya que C(p)=3.

Además, si la cota C(p) no se alcanza, entonces el número de raíces positivas de la ecuación difiere de ella un múltiplo de dos. En el ejemplo anterior esto significa que la ecuación puede tener tres raíces positivas o tener solamente una, pero no podría ocurrir que tuviera dos o que no tuviera ninguna.

Definir las funciones

cambios :: [Int] -> [(Int,Int)]
nRaicesPositivas :: [Int] -> [Int]

tales que

• (cambios xs) es la lista de los pares de elementos de xs con signos distintos, obviando los ceros. Por ejemplo,

cambios [1,3,0,-5,1,-7]  ==  [(3,-5),(-5,1),(1,-7)]

• (nRaicesPositivas p) es la lista de los posibles números de raíces positivas del polinomio p (representado mediante una lista) según la regla de los signos de Descartes. Por ejemplo,

nRaicesPositivas [1,3,0,-5,1,-7]  ==  [3,1]

que significa que la ecuación x^5+3x^4-5x^2+x-7=0 puede tener 3 ó 1 raíz positiva.

Leer más…

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

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

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

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

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

Definir las funciones

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

tales que

• (valorE e n) es el valor de la expresión e cuando se sustituye su variable por n. Por ejemplo,

λ> valorE (Sum (Const 3) (Mul Var (Mul Var (Const 5)))) 2
23

• (expresion p) es una expresión aritmética equivalente al polinomio p. Por ejemplo,

λ> expresion [3,0,5]
Sum (Const 3) (Mul Var (Sum (Const 0) (Mul Var (Const 5))))

• (valorP p n) es el valor del polinomio p cuando se sustituye su variable por n. Por ejemplo,

λ> valorP [3,0,5] 2
23

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

valorP p n == valorE (expresion p) n

Leer más…

Leer más…

Leer más…

Dado un entero positivo n, consideremos la suma de los cuadrados de sus divisores. Por ejemplo,

f(10) = 1 + 4 + 25 + 100 = 130
f(42) = 1 + 4 +  9 +  36 + 49 + 196 + 441 + 1764 = 2500

Decimos que n es especial si f(n) es un cuadrado perfecto. En los ejemplos anteriores, 42 es especial y 10 no lo es.

Definir la función

especial:: Int -> Bool

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

especial 42  ==  True
especial 10  ==  False

Calcular todos los números especiales de tres cifras.

Nota: El ejercicio está basado en el Problema 211 del proyecto Euler.

Leer más…

Definir las funciones

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

tales que

• (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs de mayor longitud. Por ejemplo,

λ> mayoresCrecientes [3,2,6,4,5,1]
[[3,4,5],[2,4,5]]
λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]
[[10,22,33,50,60,80],[10,22,33,41,60,80]]
λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
[[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]
λ> length (head (mayoresCrecientes (show (2^70))))
5

• (longitudMayorSublistaCreciente xs) es 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

Leer más…

Definir la función

sinDobleCero :: Int -> [[Int]]

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

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

Leer más…

Un mínimo local de una lista es un elemento de la lista que es menor que su predecesor y que su sucesor en la lista. Por ejemplo, 1 es un mínimo local de [8,2,1,3,7,6,4,0,5] ya que es menor que 2 (su predecesor) y que 3 (su sucesor).

Análogamente se definen los máximos locales. Por ejemplo, 7 es un máximo local de [8,2,1,3,7,6,4,0,5] ya que es mayor que 7 (su predecesor) y que 6 (su sucesor).

Los extremos locales están formados por los mínimos y máximos locales. Por ejemplo, los extremos locales de [8,2,1,3,7,6,4,0,5] son el 1, el 7 y el 0.

Definir la función

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

tal que (extremos xs) es la lista de los extremos locales de la lista xs. Por ejemplo,

extremos [8,2,1,3,7,6,4,0,5]  ==  [1,7,0]
extremos [8,2,1,3,7,7,4,0,5]  ==  [1,7,0]

Leer más…

Las expresiones aritméticas pueden representarse usando el siguiente tipo de datos

data Expr = N Int | S Expr Expr | P Expr Expr
  deriving (Eq, Ord, Show)

Por ejemplo, la expresión 2*(3+7) se representa por

P (N 2) (S (N 3) (N 7))

Definir la función

subexpresiones :: Expr -> Set Expr

tal que (subexpresiones e) es el conjunto de las subexpresiones de e. Por ejemplo,

λ> subexpresiones (S (N 2) (N 3))
fromList [N 2,N 3,S (N 2) (N 3)]
λ> subexpresiones (P (S (N 2) (N 2)) (N 7))
fromList [N 2,N 7,S (N 2) (N 2),P (S (N 2) (N 2)) (N 7)]

Leer más…