Definir la función
raizEnt :: Integer -> Integer -> Integer
tal que raizEnt x n es la raíz entera n-ésima de x; es decir, el mayor número entero y tal que \(y^n \leq x\). Por ejemplo,
raizEnt 8 3 == 2 raizEnt 9 3 == 2 raizEnt 26 3 == 2 raizEnt 27 3 == 3 raizEnt (10^50) 2 == 10000000000000000000000000
Comprobar con QuickCheck que para todo número natural n,
raizEnt (10^(2*n)) 2 == 10^n
El método de bisección para calcular una raíz 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\) 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 una raíz 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 = \frac{a+b}{2}\) y considerar los siguientes casos:
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
Definir la función
limite :: (Double -> Double) -> Double -> Double
tal que limite f a es el valor de f en el primer término x tal que, para todo y entre x+1 y x+100, el valor absoluto de la diferencia entre f(y) y f(x) es menor que a. Por ejemplo,
limite (\n -> (2*n+1)/(n+5)) 0.001 == 1.9900110987791344 limite (\n -> (1+1/n)**n) 0.001 == 2.714072874546881
Definir, usando puntoCero, la función
inversa :: (Double -> Double) -> Double -> Double
tal que inversa g x es el valor de la inversa de g en x. Por ejemplo,
inversa (^2) 9 == 3.000000002941184
Definir, usando inversa, las funciones raizCuadrada, raizCubica, arcoseno y arcocoseno que calculen la raíz cuadrada, la raíz cúbica, el arco seno y el arco coseno, respectivamente. Por ejemplo,
raizCuadrada 9 == 3.000000002941184 raizCubica 27 == 3.0000000000196048 arcoseno 1 == 1.5665489428306574 arcocoseno 0 == 1.5707963267949576
Los ceros de una función pueden calcularse mediante el método de Newton basándose en las siguientes propiedades:
Definir la función
puntoCero :: (Double -> Double) -> Double
tal que puntoCero f es un cero de la función f calculado usando la propiedad anterior. Por ejemplo,
puntoCero cos == 1.5707963267949576
El método de Herón para calcular la raíz cuadrada de un número se basa en las siguientes propiedades:
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
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
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
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
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)]