Números tetranacci
Los números tetranacci son una generalización de los números de Fibonacci definidos por
|
1 2 3 4 5 |
T(0) = 0, T(1) = 1, T(2) = 1, T(3) = 2, T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4), para n > 3. |
Los primeros números tetranacci son
|
1 |
0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208 |
Definir las funciones
|
1 2 |
tetranacci :: Int -> Integer graficaTetranacci :: Int -> IO () |
tales que
- (tetranacci n) es el n-ésimo número tetranacci. Por ejemplo,
|
1 2 3 4 5 6 |
λ> tetranacci 10 208 λ> map tetranacci [0..10] [0,1,1,2,4,8,15,29,56,108,208] λ> length (show (tetranacci5 (10^5))) 28501 |
- (graficaTetranacci n) dibuja la gráfica de los cocientes de n primeros pares de número tetranacci. Por ejemplo, (graficaTetranacci 300) dibuja
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
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] |