Menu Close

Árbol de computación de Fibonacci

La sucesión de Fibonacci es

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

cuyos dos primeros términos son 0 y 1 y los restantentes se obtienen sumando los dos anteriores.

El árbol de computación de su 5º término es

                 5
                / \
               /   \
              /     \
             /       \
            /         \
           3           2  
          / \         / \ 
         /   \       1   1
        2     1     / \   
       / \   / \   1   0  
      1   1 1   0
     / \ 
    1   0

que, usando los árboles definidos por

   data Arbol = H Int
              | N Int Arbol Arbol
     deriving (Eq, Show)

se puede representar por

   N 5              
     (N 3           
        (N 2        
           (N 1 (H 1) (H 0))
           (H 1))   
        (N 1 (H 1) (H 0)))  
     (N 2           
        (N 1 (H 1) (H 0))   
        (H 1))

Definir las funciones

   arbolFib           :: Int -> Arbol
   nElementosArbolFib :: Int -> Int

tales que

  • (arbolFib n) es el árbol de computación del n-ésimo término de la sucesión de Fibonacci. Por ejemplo,
     λ> arbolFib 5
     N 5              
       (N 3           
          (N 2        
             (N 1 (H 1) (H 0))
             (H 1))   
          (N 1 (H 1) (H 0)))  
       (N 2           
          (N 1 (H 1) (H 0))   
          (H 1))
     λ> arbolFib 6
     N 8
       (N 5
          (N 3
             (N 2
                (N 1 (H 1) (H 0))
                (H 1))
             (N 1 (H 1) (H 0)))
          (N 2
             (N 1 (H 1) (H 0))
             (H 1)))
       (N 3
          (N 2
             (N 1 (H 1) (H 0)) (H 1))
          (N 1 (H 1) (H 0)))
  • (nElementosArbolFib n) es el número de elementos en el árbol de computación del n-ésimo término de la sucesión de Fibonacci. Por ejemplo,
     nElementosArbolFib 5   ==  15
     nElementosArbolFib 6   ==  25
     nElementosArbolFib 30  ==  2692537

Soluciones

data Arbol = H Int
           | N Int Arbol Arbol
  deriving (Eq, Show)
 
-- 1ª definición
-- =============
 
arbolFib :: Int -> Arbol
arbolFib 0 = H 0
arbolFib 1 = H 1
arbolFib n = N (fib n) (arbolFib (n-1)) (arbolFib (n-2))
 
-- (fib n) es el n-ésimo elemento de la sucesión de Fibonacci. Por
-- ejemplo,
--    fib 5  ==  5
--    fib 6  ==  8
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
 
-- 2ª definición
-- =============
 
arbolFib2 :: Int -> Arbol
arbolFib2 0 = H 0
arbolFib2 1 = H 1
arbolFib2 2 = N 1 (H 1) (H 0)
arbolFib2 3 = N 2 (N 1 (H 1) (H 0)) (H 1)
arbolFib2 n = N (a1 + a2) (N a1 i1 d1) (N a2 i2 d2)
  where (N a1 i1 d1) = arbolFib2 (n-1)
        (N a2 i2 d2) = arbolFib2 (n-2)
 
-- 3ª definición
-- =============
 
arbolFib3 :: Int -> Arbol
arbolFib3 0 = H 0
arbolFib3 1 = H 1
arbolFib3 2 = N 1 (H 1) (H 0)
arbolFib3 3 = N 2 (N 1 (H 1) (H 0)) (H 1)
arbolFib3 n = N (a + b) i d
  where i@(N a _ _) = arbolFib3 (n-1)
        d@(N b _ _) = arbolFib3 (n-2)
 
-- 1ª definición de nElementosArbolFib
-- ===================================
 
nElementosArbolFib :: Int -> Int
nElementosArbolFib = length . elementos . arbolFib3
 
-- (elementos a) es la lista de elementos del árbol a. Por ejemplo,
--    λ> elementos (arbolFib 5)
--    [5,3,2,1,1,0,1,1,1,0,2,1,1,0,1]
--    λ> elementos (arbolFib 6)
--    [8,5,3,2,1,1,0,1,1,1,0,2,1,1,0,1,3,2,1,1,0,1,1,1,0]
elementos :: Arbol -> [Int]
elementos (H x)     = [x]
elementos (N x i d) = x : elementos i ++ elementos d
 
-- 2ª definición de nElementosArbolFib
-- ===================================
 
nElementosArbolFib2 :: Int -> Int
nElementosArbolFib2 0 = 1
nElementosArbolFib2 1 = 1
nElementosArbolFib2 n = 1 + nElementosArbolFib2 (n-1)
                          + nElementosArbolFib2 (n-2)

Pensamiento

Toda visión requiere distancia.

Antonio Machado

Medio

5 soluciones de “Árbol de computación de Fibonacci

  1. luipromor
    arbolFib :: Int -> Arbol
    arbolFib 0 = H 0
    arbolFib 1 = H 1
    arbolFib x = N (last (fibonacci x)) (arbolFib (x-1)) (arbolFib (x-2))
      where fibo 0 = 0
            fibo 1 = 1
            fibo x = fibo(x-1) +  fibo(x-2)
            fibonacci n = [fibo x | x <- [0..n]]
     
    nElementosArbolFib :: Int -> Int
    nElementosArbolFib x = profundidad (arbolFib x)
      where profundidad (H _)     = 1
            profundidad (N _ i d) = 1 + profundidad i + profundidad d
  2. adogargon
    arbolFib :: Int -> Arbol
    arbolFib 0 = H 0
    arbolFib 1 = H 1
    arbolFib n = N (fib n) (arbolFib (n-1)) (arbolFib (n-2))
     
    fib :: Int -> Int
    fib 1 = 1
    fib 0 = 0
    fib n = fib (n-1) + fib (n-2)
     
    nElementosArbolFib :: Int -> Int
    nElementosArbolFib n = nNodos (arbolFib n ) + nHojas (arbolFib n)
     
    nNodos :: Arbol  -> Int
    nNodos (H _)     = 0
    nNodos (N _ i d) = 1 + nNodos i + nNodos d
     
    nHojas :: Arbol  -> Int
    nHojas (H _)     = 1
    nHojas (N _ i d) = nHojas i + nHojas d
  3. frahidzam
    arbolFib :: Int -> Arbol
    arbolFib 0 = H 0
    arbolFib 1 = H 1
    arbolFib n = N (fib n) (arbolFib (n-1)) (arbolFib (n-2))
     
    fib :: Int -> Int
    fib 1 = 1
    fib 0 = 0
    fib n = fib (n-1) + fib (n-2)
     
    nElementosArbolFib :: Int -> Int
    nElementosArbolFib n = length (aplana (arbolFib n))
     
    aplana :: Arbol -> [Int]
    aplana (H h)     = [h]
    aplana (N n i d) = [n] ++ aplana i ++ aplana d
  4. ireprirod
    arbolFib :: Int -> Arbol
    arbolFib 0 = H 0
    arbolFib 1 = H 1
    arbolFib 2 = N 1 (H 1) (H 0)
    arbolFib 3 = N 2        
                 (N 1 (H 1) (H 0))
                 (H 1) 
    arbolFib n = N (fibs !! n) (arbolFib (n-1)) (arbolFib (n-2))
     
    fibs :: [Int]
    fibs = [fib n | n <- [0..]]
      where fib 0 = 0
            fib 1 = 1
            fib n = fib (n-1) + fib (n-2)
     
    nElementosArbolFib :: Int -> Int
    nElementosArbolFib n = nElementosAux (arbolFib n)
      where nElementosAux (H _ )    = 1
            nElementosAux (N _ i d) = 1 + nElementosAux i + nElementosAux d
  5. javmarcha1
    arbolFib :: Int -> Arbol
    arbolFib 0 = H 0
    arbolFib 1 = H 1
    arbolFib n = N (last (fibonacci n)) (arbolFib (n-1)) (arbolFib (n-2)) 
     
    elefibonacci :: Int -> Int
    elefibonacci 0 = 0
    elefibonacci 1 = 1
    elefibonacci x = elefibonacci (x-1) + elefibonacci (x-2)
     
    fibonacci :: Int -> [Int]
    fibonacci x = [elefibonacci y | y <- [0..x]]
     
    nElementosArbolFib :: Int -> Int
    nElementosArbolFib n = length (aplana (arbolFib n))
     
    aplana :: Arbol -> [Int]
    aplana (H n)     = [n]
    aplana (N n i d) = (aplana i) ++ [n] ++ (aplana d)

Escribe tu solución

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