Menu Close

Etiqueta: Recursión

Definición por recursión

Caminos en un grafo

Definir las funciones

   grafo   :: [(Int,Int)] -> Grafo Int Int
   caminos :: Grafo Int Int -> Int -> Int -> [[Int]]

tales que

  • (grafo as) es el grafo no dirigido definido cuyas aristas son as. Por ejemplo,
     ghci> grafo [(2,4),(4,5)]
     G ND (array (2,5) [(2,[(4,0)]),(3,[]),(4,[(2,0),(5,0)]),(5,[(4,0)])])
  • (caminos g a b) es la lista los caminos en el grafo g desde a hasta b sin pasar dos veces por el mismo nodo. Por ejemplo,
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 7)
     [[1,3,5,7],[1,3,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 2 7)
     [[2,5,3,7],[2,5,7]]
     ghci> sort (caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 2)
     [[1,3,5,2],[1,3,7,5,2]]
     ghci> caminos (grafo [(1,3),(2,5),(3,5),(3,7),(5,7)]) 1 4
     []
     ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
     109601

Soluciones

import Data.List (sort)
import I1M.Grafo
import I1M.BusquedaEnEspaciosDeEstados
 
grafo :: [(Int,Int)] -> Grafo Int Int
grafo as = creaGrafo ND (m,n) [(x,y,0) | (x,y) <- as]
  where ns = map fst as ++ map snd as
        m  = minimum ns
        n  = maximum ns
 
-- 1ª solución
-- ===========
 
caminos :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos g a b = aux [[b]] where 
  aux [] = []
  aux ((x:xs):yss)
    | x == a    = (x:xs) : aux yss
    | otherwise = aux ([z:x:xs | z <- adyacentes g x
                               , z `notElem` (x:xs)] 
                       ++ yss) 
 
-- 2ª solución (mediante espacio de estados)
-- =========================================
 
caminos2 :: Grafo Int Int -> Int -> Int -> [[Int]]
caminos2 g a b = buscaEE sucesores esFinal inicial
  where inicial          = [b]
        sucesores (x:xs) = [z:x:xs | z <- adyacentes g x
                                   , z `notElem` (x:xs)] 
        esFinal (x:xs)   = x == a
 
-- Comparación de eficiencia
-- =========================
 
--    ghci> length (caminos (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.57 secs, 500533816 bytes)
--    ghci> length (caminos2 (grafo [(i,j) | i <- [1..10], j <- [i..10]]) 1 10)
--    109601
--    (3.53 secs, 470814096 bytes)

Sin ceros consecutivos

Definir la función

   sinDobleCero :: Int -> [[Int]]

tal que (sinDobleCero n) es la lista de las listas de longitud n formadas por el 0 y el 1 tales que no contiene dos ceros consecutivos. Por ejemplo,

   ghci> sinDobleCero 2
   [[1,0],[1,1],[0,1]]
   ghci> sinDobleCero 3
   [[1,1,0],[1,1,1],[1,0,1],[0,1,0],[0,1,1]]
   ghci> sinDobleCero 4
   [[1,1,1,0],[1,1,1,1],[1,1,0,1],[1,0,1,0],[1,0,1,1],
    [0,1,1,0],[0,1,1,1],[0,1,0,1]]

Soluciones

sinDobleCero :: Int -> [[Int]]
sinDobleCero 0 = [[]]
sinDobleCero 1 = [[0],[1]]
sinDobleCero n = [1:xs | xs <- sinDobleCero (n-1)] ++
                 [0:1:ys | ys <- sinDobleCero (n-2)]

Las sucesiones de Loomis

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

  • f(0) es x
  • f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

  • Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, …
  • Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
  • Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
  • Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, …
  • Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, …

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

  • la generada por 2 converge a 2
  • la generada por 3 converge a 26
  • la generada por 4 converge a 4
  • la generada por 5 converge a 26

Definir las siguientes funciones

   sucLoomis           :: Integer -> [Integer]
   convergencia        :: Integer -> Integer
   graficaConvergencia :: [Integer] -> IO ()

tales que

  • (sucLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,
     λ> take 15 (sucLoomis 1)
     [1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 2)
     [2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 3)
     [3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 4)
     [4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
     λ> take 15 (sucLoomis 5)
     [5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 20)
     [20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
     λ> take 15 (sucLoomis 100)
     [100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
     λ> sucLoomis 1 !! (2*10^5)
     235180736652
  • (convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,
     convergencia  2      ==  2
     convergencia  3      ==  26
     convergencia  4      ==  4
     convergencia 17      ==  38
     convergencia 19      ==  102
     convergencia 43      ==  162
     convergencia 27      ==  202
     convergencia 58      ==  474
     convergencia 63      ==  150056
     convergencia 81      ==  150056
     convergencia 89      ==  150056
     convergencia (10^12) ==  1000101125092
  • (graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja
    Las_sucesiones_de_Loomis_1
    y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja
    Las_sucesiones_de_Loomis_2

Soluciones

import Data.List               ((\\))
import Data.Char               (digitToInt)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, Title, XRange, PNG))
 
-- 1ª definición de sucLoomis
-- ==========================
 
sucLoomis :: Integer -> [Integer]
sucLoomis x = map (loomis x) [0..]
 
loomis :: Integer -> Integer -> Integer
loomis x 0 = x
loomis x n = y + productoDigitosNoNulos y
  where y = loomis x (n-1)
 
productoDigitosNoNulos :: Integer -> Integer
productoDigitosNoNulos = product . digitosNoNulos
 
digitosNoNulos :: Integer -> [Integer]
digitosNoNulos x =
  [read [c] | c <- show x, c /= '0']
 
-- 2ª definición de sucLoomis
-- ==========================
 
sucLoomis2 :: Integer -> [Integer]
sucLoomis2 = iterate siguienteLoomis 
 
siguienteLoomis :: Integer -> Integer
siguienteLoomis y = y + productoDigitosNoNulos y
 
-- 3ª definición de sucLoomis
-- ==========================
 
sucLoomis3 :: Integer -> [Integer]
sucLoomis3 =
  iterate ((+) <*> product .
           map (toInteger . digitToInt) .
           filter (/= '0') . show)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sucLoomis 1 !! 30000
--    6571272766
--    (2.45 secs, 987,955,944 bytes)
--    λ> sucLoomis2 1 !! 30000
--    6571272766
--    (2.26 secs, 979,543,328 bytes)
--    λ> sucLoomis3 1 !! 30000
--    6571272766
--    (0.31 secs, 88,323,832 bytes)
 
-- 1ª definición de convergencia
-- =============================
 
convergencia1 :: Integer -> Integer
convergencia1 x =
  head (dropWhile noEnSucLoomisDe1 (sucLoomis x))
 
noEnSucLoomisDe1 :: Integer -> Bool
noEnSucLoomisDe1 x = not (pertenece x sucLoomisDe1)
 
sucLoomisDe1 :: [Integer]
sucLoomisDe1 = sucLoomis 1
 
pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (<x) ys)
 
-- 2ª definición de convergencia
-- =============================
 
convergencia2 :: Integer -> Integer
convergencia2 = aux (sucLoomis3 1) . sucLoomis3
 where aux as@(x:xs) bs@(y:ys) | x == y    = x
                               | x < y     = aux xs bs
                               | otherwise = aux as ys
 
-- 3ª definición de convergencia
-- =============================
 
convergencia3 :: Integer -> Integer
convergencia3 = head . interseccion (sucLoomis3 1) . sucLoomis3
 
-- (interseccion xs ys) es la intersección entre las listas ordenadas xs
-- e ys. Por ejemplo,
--    λ> take 10 (interseccion (sucLoomis3 1) (sucLoomis3 2))
--    [2,4,8,16,22,26,38,62,74,102]
interseccion :: Ord a => [a] -> [a] -> [a]
interseccion = aux
  where aux as@(x:xs) bs@(y:ys) = case compare x y of
                                    LT ->     aux xs bs
                                    EQ -> x : aux xs ys
                                    GT ->     aux as ys
        aux _         _         = []                           
 
-- 4ª definición de convergencia
-- =============================
 
convergencia4 :: Integer -> Integer
convergencia4 x = perteneceA (sucLoomis3 x) 1
  where perteneceA (y:ys) n | y == c    = y
                            | otherwise = perteneceA ys c
          where c = head $ dropWhile (< y) $ sucLoomis3 n
 
-- Comparación de eficiencia
-- =========================
 
--    λ> convergencia1 (10^4)
--    150056
--    (2.94 secs, 1,260,809,808 bytes)
--    λ> convergencia2 (10^4)
--    150056
--    (0.03 secs, 700,240 bytes)
--    λ> convergencia3 (10^4)
--    150056
--    (0.03 secs, 1,165,496 bytes)
--    λ> convergencia4 (10^4)
--    150056
--    (0.02 secs, 1,119,648 bytes)
--    
--    λ> convergencia2 (10^12)
--    1000101125092
--    (1.81 secs, 714,901,080 bytes)
--    λ> convergencia3 (10^12)
--    1000101125092
--    (1.92 secs, 744,932,184 bytes)
--    λ> convergencia4 (10^12)
--    1000101125092
--    (1.82 secs, 941,053,328 bytes)
 
-- Definición de graficaConvergencia
-- ==================================
 
graficaConvergencia :: [Integer] -> IO ()
graficaConvergencia xs =
  plotList [ Key Nothing
           , Title "Convergencia de sucesiones de Loomis"
           , XRange (fromIntegral (minimum xs),fromIntegral (maximum xs))
           , PNG "Las_sucesiones_de_Loomis_2.png"
           ]
           [(x,convergencia2 x) | x <- xs]

Espacio de estados del problema de las N reinas

El problema de las N reinas consiste en colocar N reinas en tablero rectangular de dimensiones N por N de forma que no se encuentren más de una en la misma línea: horizontal, vertical o diagonal. Por ejemplo, una solución para el problema de las 4 reinas es

   |---|---|---|---|
   |   | R |   |   |
   |---|---|---|---|
   |   |   |   | R |
   |---|---|---|---|
   | R |   |   |   |
   |---|---|---|---|
   |   |   | R |   |
   |---|---|---|---|

Los estados del problema de las N reinas son los tableros con las reinas colocadas. Inicialmente el tablero está vacío y, en cda paso se coloca una reina en la primera columna en la que aún no hay ninguna reina.

Cada estado se representa por una lista de números que indican las filas donde se han colocado las reinas. Por ejemplo, el tablero anterior se representa por [2,4,1,3].

Usando la librería de árboles Data.Tree, definir las funciones

   arbolReinas :: Int -> Tree [Int]
   nEstados    :: Int -> Int
   soluciones  :: Int -> [[Int]]
   nSoluciones :: Int -> Int

tales que

  • (arbolReinas n) es el árbol de estados para el problema de las n reinas. Por ejemplo,
     λ> putStrLn (drawTree (fmap show (arbolReinas 4)))
     []
     |
     +- [1]
     |  |
     |  +- [3,1]
     |  |
     |  `- [4,1]
     |     |
     |     `- [2,4,1]
     |
     +- [2]
     |  |
     |  `- [4,2]
     |     |
     |     `- [1,4,2]
     |        |
     |        `- [3,1,4,2]
     |
     +- [3]
     |  |
     |  `- [1,3]
     |     |
     |     `- [4,1,3]
     |        |
     |        `- [2,4,1,3]
     |
     `- [4]
        |
        +- [1,4]
        |  |
        |  `- [3,1,4]
        |
        `- [2,4]
 
     λ> putStrLn (drawTree (fmap show (arbolReinas 5)))
     []
     |
     +- [1]
     |  |
     |  +- [3,1]
     |  |  |
     |  |  `- [5,3,1]
     |  |     |
     |  |     `- [2,5,3,1]
     |  |        |
     |  |        `- [4,2,5,3,1]
     |  |
     |  +- [4,1]
     |  |  |
     |  |  `- [2,4,1]
     |  |     |
     |  |     `- [5,2,4,1]
     |  |        |
     |  |        `- [3,5,2,4,1]
     |  |
     |  `- [5,1]
     |     |
     |     `- [2,5,1]
     |
     +- [2]
     |  |
     |  +- [4,2]
     |  |  |
     |  |  `- [1,4,2]
     |  |     |
     |  |     `- [3,1,4,2]
     |  |        |
     |  |        `- [5,3,1,4,2]
     |  |
     |  `- [5,2]
     |     |
     |     +- [1,5,2]
     |     |  |
     |     |  `- [4,1,5,2]
     |     |
     |     `- [3,5,2]
     |        |
     |        `- [1,3,5,2]
     |           |
     |           `- [4,1,3,5,2]
     |
     +- [3]
     |  |
     |  +- [1,3]
     |  |  |
     |  |  `- [4,1,3]
     |  |     |
     |  |     `- [2,4,1,3]
     |  |        |
     |  |        `- [5,2,4,1,3]
     |  |
     |  `- [5,3]
     |     |
     |     `- [2,5,3]
     |        |
     |        `- [4,2,5,3]
     |           |
     |           `- [1,4,2,5,3]
     |
     +- [4]
     |  |
     |  +- [1,4]
     |  |  |
     |  |  +- [3,1,4]
     |  |  |  |
     |  |  |  `- [5,3,1,4]
     |  |  |     |
     |  |  |     `- [2,5,3,1,4]
     |  |  |
     |  |  `- [5,1,4]
     |  |     |
     |  |     `- [2,5,1,4]
     |  |
     |  `- [2,4]
     |     |
     |     `- [5,2,4]
     |        |
     |        `- [3,5,2,4]
     |           |
     |           `- [1,3,5,2,4]
     |
     `- [5]
        |
        +- [1,5]
        |  |
        |  `- [4,1,5]
        |
        +- [2,5]
        |  |
        |  `- [4,2,5]
        |     |
        |     `- [1,4,2,5]
        |        |
        |        `- [3,1,4,2,5]
        |
        `- [3,5]
           |
           `- [1,3,5]
              |
              `- [4,1,3,5]
                 |
                 `- [2,4,1,3,5]
  • (nEstados n) es el número de estados en el problema de las n reinas. Por ejemplo,
     nEstados 4            ==  17
     nEstados 5            ==  54
     map nEstados [0..10]  ==  [1,2,3,6,17,54,153,552,2057,8394,35539]
  • (soluciones n) es la lista de estados que son soluciones del problema de las n reinas. Por ejemplo,
     λ> soluciones 4
     [[3,1,4,2],[2,4,1,3]]
     λ> soluciones 5
     [[4,2,5,3,1],[3,5,2,4,1],[5,3,1,4,2],[4,1,3,5,2],[5,2,4,1,3],
      [1,4,2,5,3],[2,5,3,1,4],[1,3,5,2,4],[3,1,4,2,5],[2,4,1,3,5]]
  • (nSoluciones n) es el número de soluciones del problema de las n reinas. Por ejemplo,
     nSoluciones 4            ==  2
     nSoluciones 5            ==  10
     map nSoluciones [0..10]  ==  [1,1,0,0,2,10,4,40,92,352,724]

Soluciones

import Data.List ((\\))
import Data.Tree
 
-- Definición de arbolReinas
-- =========================
 
arbolReinas :: Int -> Tree [Int]
arbolReinas n = expansion n []
  where
    expansion m xs = Node xs [expansion (m-1) ys | ys <- sucesores n xs]
 
-- (sucesores n xs) es la lista de los sucesores del estado xs en el
-- problema de las n reinas. Por ejemplo,
--    sucesores 4 []       ==  [[1],[2],[3],[4]]
--    sucesores 4 [1]      ==  [[3,1],[4,1]]
--    sucesores 4 [4,1]    ==  [[2,4,1]]
--    sucesores 4 [2,4,1]  ==  []
sucesores :: Int -> [Int] -> [[Int]]
sucesores n xs = [y:xs | y <- [1..n] \\ xs
                       , noAtaca y xs 1]
 
-- (noAtaca y xs d) se verifica si la reina en la fila y no ataca a las
-- colocadas en las filas xs donde d es el número de columnas desde la
-- de la posición de x a la primera de xs.
noAtaca :: Int -> [Int] -> Int -> Bool
noAtaca _ [] _ = True
noAtaca y (x:xs) distH = abs(y-x) /= distH &&
                         noAtaca y xs (distH + 1)               
 
-- Definición de nEstados
-- ======================
 
nEstados :: Int -> Int
nEstados = length . arbolReinas
 
-- Definición de solucionesReinas
-- ==============================
 
--    λ> soluciones 4
--    [[3,1,4,2],[2,4,1,3]]
--    λ> soluciones 5
--    [[4,2,5,3,1],[3,5,2,4,1],[5,3,1,4,2],[4,1,3,5,2],[5,2,4,1,3],
--     [1,4,2,5,3],[2,5,3,1,4],[1,3,5,2,4],[3,1,4,2,5],[2,4,1,3,5]]
soluciones :: Int -> [[Int]]
soluciones n =
  filter (\xs -> length xs == n) (estados n)
 
-- (estados n) es la lista de estados del problema de las n reinas. Por
-- ejemplo, 
--   λ> estados 4
--   [[],
--    [1],[2],[3],[4],
--    [3,1],[4,1],[4,2],[1,3],[1,4],[2,4],
--    [2,4,1],[1,4,2],[4,1,3],[3,1,4],
--    [3,1,4,2],[2,4,1,3]]
estados :: Int -> [[Int]]
estados = concat . levels . arbolReinas
 
-- Definición de nSoluciones
-- =========================
 
nSoluciones :: Int -> Int
nSoluciones = length . soluciones

Codificación de Fibonacci

La codificación de Fibonacci de un número n es una cadena d = d(0)d(1)…d(k-1)d(k) de ceros y unos tal que

   n = d(0)*F(2) + d(1)*F(3) +...+ d(k-1)*F(k+1) 
   d(k-1) = d(k) = 1

donde F(i) es el i-ésimo término de la sucesión de Fibonacci.

   0,1,1,2,3,5,8,13,21,34,...

Por ejemplo. La codificación de Fibonacci de 4 es “1011” ya que los dos últimos elementos son iguales a 1 y

   1*F(2) + 0*F(3) + 1*F(4) = 1*1 + 0*2 + 1*3 = 4

La codificación de Fibonacci de los primeros números se muestra en la siguiente tabla

    1  = 1     = F(2)           ≡       11
    2  = 2     = F(3)           ≡      011
    3  = 3     = F(4)           ≡     0011
    4  = 1+3   = F(2)+F(4)      ≡     1011
    5  = 5     = F(5)           ≡    00011
    6  = 1+5   = F(2)+F(5)      ≡    10011
    7  = 2+5   = F(3)+F(5)      ≡    01011
    8  = 8     = F(6)           ≡   000011
    9  = 1+8   = F(2)+F(6)      ≡   100011
   10  = 2+8   = F(3)+F(6)      ≡   010011
   11  = 3+8   = F(4)+F(6)      ≡   001011
   12  = 1+3+8 = F(2)+F(4)+F(6) ≡   101011
   13  = 13    = F(7)           ≡  0000011
   14  = 1+13  = F(2)+F(7)      ≡  1000011

Definir la función

   codigoFib :: Integer -> String

tal que (codigoFib n) es la codificación de Fibonacci del número n. Por ejemplo,

   λ> codigoFib 65
   "0100100011"
   λ> [codigoFib n | n <- [1..7]]
   ["11","011","0011","1011","00011","10011","01011"]

Soluciones

import Data.List
import Data.Array
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
codigoFib1 :: Integer -> String
codigoFib1 = (concatMap show) . codificaFibLista
 
-- (codificaFibLista n) es la lista correspondiente a la codificación de
-- Fibonacci del número n. Por ejemplo,
--    λ> codificaFibLista 65
--    [0,1,0,0,1,0,0,0,1,1]
--    λ> [codificaFibLista n | n <- [1..7]]
--    [[1,1],[0,1,1],[0,0,1,1],[1,0,1,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,0,1,1]]
codificaFibLista :: Integer -> [Integer]
codificaFibLista n = map f [2..head xs] ++ [1]
  where xs = map fst (descomposicion n)
        f i | elem i xs = 1
            | otherwise = 0
 
-- (descomposicion n) es la lista de pares (i,f) tales que f es el
-- i-ésimo número de Fibonacci y las segundas componentes es una
-- sucesión decreciente de números de Fibonacci cuya suma es n. Por
-- ejemplo, 
--    descomposicion 65  ==  [(10,55),(6,8),(3,2)]
--    descomposicion 66  ==  [(10,55),(6,8),(4,3)]
descomposicion :: Integer -> [(Integer, Integer)]
descomposicion 0 = []
descomposicion 1 = [(2,1)]
descomposicion n = (i,x) : descomposicion (n-x)
  where (i,x) = fibAnterior n
 
-- (fibAnterior n) es el mayor número de Fibonacci menor o igual que
-- n. Por ejemplo,
--    fibAnterior 33  ==  (8,21)
--    fibAnterior 34  ==  (9,34)
fibAnterior :: Integer -> (Integer, Integer)
fibAnterior n = last (takeWhile p fibsConIndice)
  where p (i,x) = x <= n
 
-- fibsConIndice es la sucesión de los números de Fibonacci junto con
-- sus índices. Por ejemplo,
--    λ> take 10 fibsConIndice
--    [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21),(9,34)]
fibsConIndice :: [(Integer, Integer)]
fibsConIndice = zip [0..] fibs
 
-- fibs es la sucesión de Fibonacci. Por ejemplo, 
--    take 10 fibs  ==  [0,1,1,2,3,5,8,13,21,34]
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 
--- 2ª solución
-- ============
 
codigoFib2 :: Integer -> String
codigoFib2 = (concatMap show) . elems . codificaFibVec
 
-- (codificaFibVec n) es el vector correspondiente a la codificación de
-- Fibonacci del número n. Por ejemplo,
--    λ> codificaFibVec 65
--    array (0,9) [(0,0),(1,1),(2,0),(3,0),(4,1),(5,0),(6,0),(7,0),(8,1),(9,1)]
--    λ> [elems (codificaFibVec n) | n <- [1..7]]
--    [[1,1],[0,1,1],[0,0,1,1],[1,0,1,1],[0,0,0,1,1],[1,0,0,1,1],[0,1,0,1,1]]
codificaFibVec :: Integer -> Array Integer Integer
codificaFibVec n = accumArray (+) 0 (0,a+1) ((a+1,1):is) 
  where is = [(i-2,1) | (i,x) <- descomposicion n]
        a  = fst (head is)
 
-- Comparación de eficiencia
-- =========================
--    λ> head [n | n <- [1..], length (codigoFib1 n) > 25]
--    121393
--    (14.37 secs, 3135674112 bytes)
--    λ> :r
--    Ok, modules loaded: Main.
--    λ> head [n | n <- [1..], length (codigoFib2 n) > 25]
--    121393
--    (12.04 secs, 2762190920 bytes)
 
-- Propiedades
-- ===========
 
-- Usaremos la 2ª definición
codigoFib :: Integer -> String
codigoFib = codigoFib2
 
-- Prop.: La función descomposicion es correcta:
propDescomposicionCorrecta :: Integer -> Property
propDescomposicionCorrecta n =
  n >= 0 ==> n == sum (map snd (descomposicion n))
 
-- La comprobación es
--    λ> quickCheck propDescomposicionCorrecta
--    +++ OK, passed 100 tests.
 
-- Prop.: Todo número natural se puede descomponer en suma de números de
-- la sucesión de Fibonacci.
propDescomposicion :: Integer -> Property
propDescomposicion n =
  n >= 0 ==> not (null (descomposicion n))
 
-- La comprobación es
--    λ> quickCheck propDescomposicion
--    +++ OK, passed 100 tests.
 
-- Prop.: Las codificaciones de Fibonacci tienen como mínimo 2 elementos.
prop1 :: Integer -> Property
prop1 n = n > 0 ==> length (codigoFib n) >= 2
 
-- La comprobación es
--    λ> quickCheck prop1
--    +++ OK, passed 100 tests.
 
-- Prop.: Los dos últimos elementos de las codificaciones de Fibonacci
-- son iguales a 1.
prop2 :: Integer -> Property
prop2 n = n > 0 ==> take 2 (reverse (codigoFib n)) == "11"
 
-- La comprobación es
--    λ> quickCheck prop2
--    +++ OK, passed 100 tests.
 
-- Prop.: En las codificaciones de Fibonacci, la cadena "11" sólo
-- aparece una vez y la única vez que aparece es al final.
prop3 :: Integer -> Property
prop3 n = 
  n > 0 ==> not (isInfixOf "11" (drop 2 (reverse (codigoFib n))))
 
-- La comprobación es
--    λ> quickCheck prop3
--    +++ OK, passed 100 tests.