Á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,...

1	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

/ \

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)

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))

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

1 2	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)))

λ> 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

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)

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

5 Comentarios

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

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

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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)

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)

Responder

Árbol de computación de Fibonacci

Soluciones

Pensamiento

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Pensamiento

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico