Menu Close

Números tetranacci

José A. Alonso,

Los números tetranacci son una generalización de los números de Fibonacci definidos por

   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

   0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208

Definir las funciones

   tetranacci        :: Int -> Integer
   graficaTetranacci :: Int -> IO ()

tales que

  • (tetranacci n) es el n-ésimo número tetranacci. Por ejemplo,
     λ> 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
    Numeros_tetranacci_200

Soluciones

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]
Inicial
, , , , , , , , , , ,

3 soluciones de “Números tetranacci”

  1. Responder
    alerodrod5 
     
import Data.Array
 
tetranacci :: Integer -> Integer
tetranacci n = (vectorTetra n) ! n
 
vectorTetra :: Integer -> Array Integer Integer
vectorTetra n = v where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 0
  f 1 = 1
  f 2 = 1
  f 3 = 2
  f n = v!(n-1) + v!(n-2) + v!(n-3) + v!(n-4)
  2. Responder
    anadebla 
     
Es la traducción literal del enunciado, aunque no es muy eficiente.
 
import Graphics.Gnuplot.Simple
 
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)
 
listaTetranacci = [tetranacci x | x <- [1..]]
 
 
graficaTetranacci :: Int -> IO ()
graficaTetranacci n =
  plotList
  [Key Nothing, Title "graficaTetranacci"]
  (take n (listaTetranacci))
  3. Responder
    angruicam1 
    import Data.Array              (listArray, (!))
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, Title))
 
tetranacci :: Int -> Integer
tetranacci n = v ! n
  where v = listArray (0,n) ([0,1,1,2,4]
                             ++ [2*v!(i-1)-v!(i-5) | i <- [5..n]])
 
graficaTetranacci :: Int -> IO ()
graficaTetranacci n =
  plotList
  [Key Nothing, Title "Tasa de crecimiento de los numeros tetranacci"]
  (zipWith (/) (tail tetr) tetr)
  where tetr :: [Double]
        tetr = map (fromIntegral . tetranacci) [1..n]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.