import Data.List (zipWith4)
import Data.Array
import Graphics.Gnuplot.Simple
-- 1ª solución (por recursión)
-- ===========================
tetranacci :: Int -> Integer
tetranacci 0 = 0
tetranacci 1 = 1
tetranacci 2 = 1
tetranacci 3 = 2
tetranacci n =
tetranacci (n-1) + tetranacci (n-2) + tetranacci (n-3) + tetranacci (n-4)
-- 2ª solución (programación dinámica con zipWith4)
-- ================================================
tetranacci2 :: Int -> Integer
tetranacci2 n = tetranaccis2 !! n
tetranaccis2 :: [Integer]
tetranaccis2 =
0 : 1 : 1 : 2 : zipWith4 f (r 0) (r 1) (r 2) (r 3)
where f a b c d = a+b+c+d
r n = drop n tetranaccis2
-- 3ª solución (con acumuladores)
-- ==============================
tetranacci3 :: Int -> Integer
tetranacci3 n = tetranaccis3 !! n
tetranaccis3 :: [Integer]
tetranaccis3 = p (0, 1, 1, 2)
where p (a, b, c, d) = a : p (b, c, d, a + b + c + d)
-- 4ª solución
-- =============
tetranacci4 :: Int -> Integer
tetranacci4 n = tetranaccis4 !! n
tetranaccis4 :: [Integer]
tetranaccis4 = 0 : 1 : 1 : 2 : p tetranaccis4
where p (a:b:c:d:xs) = (a+b+c+d): p (b:c:d:xs)
-- 5ª solución (programación dinámica con vectores)
-- ================================================
tetranacci5 :: Int -> Integer
tetranacci5 n = v ! n where
v = array (0,n) [(i,f i) | i <- [0..n]]
f 0 = 0
f 1 = 1
f 2 = 1
f 3 = 2
f k = v!(k-1) + v!(k-2) + v!(k-3) + v!(k-4)
-- Comparación de eficiencia
-- =========================
-- λ> tetranacci 26
-- 7555935
-- (3.04 secs, 1,649,520,064 bytes)
-- λ> tetranacci2 26
-- 7555935
-- (0.00 secs, 148,064 bytes)
--
-- λ> length (show (tetranacci2 (10^5)))
-- 28501
-- (1.22 secs, 1,844,457,288 bytes)
-- λ> length (show (tetranacci3 (10^5)))
-- 28501
-- (0.88 secs, 1,860,453,968 bytes)
-- λ> length (show (tetranacci4 (10^5)))
-- 28501
-- (0.77 secs, 1,882,852,168 bytes)
-- λ> length (show (tetranacci5 (10^5)))
-- 28501
-- (0.72 secs, 1,905,707,408 bytes)
-- Gráfica
-- =======
graficaTetranacci :: Int -> IO ()
graficaTetranacci n =
plotList [ Key Nothing
, Title "Tasa de crecimiento de los numeros tetranacci"
, PNG ("Numeros_tetranacci_" ++ show n ++ ".png")
]
(take n (zipWith (/) (tail xs) xs))
where xs = (map fromIntegral tetranaccis4) :: [Double]