El método de Herón para calcular la raíz cuadrada de un número se basa en las siguientes propiedades:

• Si \(y\) es una aproximación de la raíz cuadrada de \(x\), entonces \[\frac{y+\frac{x}{y}}{2}\] es una aproximación mejor.
• El límite de la sucesión definida por \begin{align} x_{0} &= 1 \newline x_{n+1} &= \frac{x_n+\frac{x}{x_n}}{2} \end{align} es la raíz cuadrada de x.

Definir la función

   raiz :: Double -> Double

tal que raiz x es la raíz cuadrada de x calculada usando la propiedad anterior con una aproximación de 0.00001 y tomando como valor inicial 1. Por ejemplo,

   raiz 9  ==  3.000000001396984

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

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

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

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

La suma de los caminos son 37, 38, 39, 40, 34, 35, 36, 40, 41 y 32, respectivamente. El camino de máxima suma es el penúltimo (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 (caminoMaxSuma (fromList 500 500 [1..]))
   187001249

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

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

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

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

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

Definir la función

   maximaSuma :: Matrix Int -> Int

tal que maximaSuma m es el máximo de las sumas de los caminos 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 a derecha. Por ejemplo,

   λ> maximaSuma (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   41
   λ> maximaSuma (fromList 800 800 [1..])
   766721999

Leer más…

Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz

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

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

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

Definir la función

   caminos :: Matrix Int -> [[Int]]

tal que caminos m es la lista de los caminos en la matriz m desde extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia la derecha o abajo. Por ejemplo,

   λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]])
   [[1,6,11,2,8,9],
    [1,6,11,3,8,9],
    [1,6,12,3,8,9],
    [1,7,12,3,8,9],
    [1,6,11,3,4,9],
    [1,6,12,3,4,9],
    [1,7,12,3,4,9],
    [1,6,12,8,4,9],
    [1,7,12,8,4,9],
    [1,7, 3,8,4,9]]
   λ> length (caminos (fromList 12 12 [1..]))
   705432

Leer más…

Se considera una retícula con sus posiciones numeradas, desde el vértice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la retícula de dimensión 3x4 se numera como sigue:

   |-------+-------+-------+-------|
   | (1,1) | (1,2) | (1,3) | (1,4) |
   | (2,1) | (2,2) | (2,3) | (2,4) |
   | (3,1) | (3,2) | (3,3) | (3,4) |
   |-------+-------+-------+-------|

Definir la función

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

tal que caminos (m,n) es la lista de los caminos en la retícula de dimensión mxn desde (1,1) hasta (m,n). Por ejemplo,

   λ> caminos (2,3)
   [[(1,1),(1,2),(1,3),(2,3)],
    [(1,1),(1,2),(2,2),(2,3)],
    [(1,1),(2,1),(2,2),(2,3)]]
   λ> mapM_ print (caminos (3,4))
   [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)]
   [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)]
   [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)]
   [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)]
   [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)]
   [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)]
   [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)]
   [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)]
   [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)]
   [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)]

Leer más…

La distancia de Levenshtein (o distancia de edición) es el mínimo de operaciones requeridas para transformar una cadena de caracteres en otra. Las operaciones de edición que se pueden hacer son:

• insertar un carácter (por ejemplo, de "abc" a "abca")
• eliminar un carácter (por ejemplo, de "abc" a "ac")
• sustituir un carácter (por ejemplo, de "abc" a "adc")

Por ejemplo, la distancia de Levenshtein entre "casa" y "calle" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro:

   "casa"  --> "cala"  (sustitución de 's' por 'l')
   "cala"  --> "calla" (inserción de 'l' entre 'l' y 'a')
   "calla" --> "calle" (sustitución de 'a' por 'e')

Definir la función

   levenshtein :: String -> String -> Int

tal que levenshtein xs ys es la distancia de Levenshtein entre xs e ys. Por ejemplo,

   levenshtein "casa"  "calle"    ==  3
   levenshtein "calle" "casa"     ==  3
   levenshtein "casa"  "casa"     ==  0
   levenshtein "ana" "maria"      ==  3
   levenshtein "agua" "manantial" ==  7

Leer más…

Si a una secuencia X de elementos (pongamos por ejemplo, le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, "aaoa" es una subsecuencia de la secuencia "amapola".

El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).

Dadas dos secuencias X e Y, decimos que Z es una subsecuencia de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = "amapola" e Y = "matamoscas", la secuencia "aaoa" es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 "maoa" o "amoa".

Definir la función

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

tal que scm xs ys es una de las subsecuencias comunes de longitud máxima de xs e ys. Por ejemplo,

   scm "amapola" "matamoscas" == "amoa"
   scm "atamos" "matamoscas"  == "atamos"
   scm "aaa" "bbbb"           == ""

Leer más…

Si a una secuencia X de elementos (pongamos por ejemplo, caracteres) le quitamos algunos de ellos y dejamos los que quedan en el orden en el que aparecían originalmente tenemos lo que se llama una subsecuencia de X. Por ejemplo, "aaoa" es una subsecuencia de la secuencia "amapola".

El término también se aplica cuando quitamos todos los elementos (es decir, la secuencia vacía es siempre subsecuencia de cualquier secuencia) o cuando no quitamos ninguno (lo que significa que cualquier secuencia es siempre subsecuencia de sí misma).

Dadas dos secuencias X e Y, decimos que Z es una subsecuencia común de X e Y si Z es subsecuencia de X y de Y. Por ejemplo, si X = "amapola" e Y = "matamoscas", la secuencia "aaoa" es una de las subsecuencias comunes de X e Y más larga, con longitud 4, ya que no hay ninguna subsecuencia común a X e Y de longitud mayor que 4. También son subsecuencias comunes de longitud 4 "maoa" o "amoa".

Se desea encontrar la longitud de las subsecuencias comunes más largas de dos secuencias de caracteres dadas.

Definir la función

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

tal que longitudSCM xs ys es la longitud de la subsecuencia máxima de xs e ys. Por ejemplo,

   longitudSCM "amapola" "matamoscas" == 4
   longitudSCM "atamos" "matamoscas"  == 6
   longitudSCM "aaa" "bbbb"           == 0

Leer más…

El coeficiente binomial n sobre k es el número de subconjuntos de k elementos escogidos de un conjunto con n elementos.

Definir la función

   binomial :: Integer -> Integer -> Integer

tal que binomial n k es el coeficiente binomial n sobre k. Por ejemplo,

   binomial 6 3 == 20
   binomial 5 2 == 10
   binomial 5 3 == 10

Leer más…

Los primeros términos de la sucesión de Fibonacci son

   0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

Escribir dos definiciones (una recursiva y otra con programación dinámica) de la función

   fib :: Integer -> Integer

tal que fib n es el n-ésimo término de la sucesión de Fibonacci. Por ejemplo,

   fib 6 == 8

Comparar la eficiencia de las dos definiciones.

Leer más…