Menu Close

Polinomios de Fibonacci

La sucesión de polinomios de Fibonacci se define por

   p(0) = 0
   p(1) = 1
   p(n) = x*p(n-1) + p(n-2)

Los primeros términos de la sucesión son

   p(2) = x
   p(3) = x^2 + 1
   p(4) = x^3 + 2*x
   p(5) = x^4 + 3*x^2 + 1

Definir la lista

   sucPolFib :: [Polinomio Integer]

tal que sus elementos son los polinomios de Fibonacci. Por ejemplo,

   λ> take 7 sucPolFib
   [0,1,1*x,x^2 + 1,x^3 + 2*x,x^4 + 3*x^2 + 1,x^5 + 4*x^3 + 3*x]
   λ> sum (map grado (take 3000 sucPolFib2))
   4495501

Comprobar con QuickCheck que el valor del n-ésimo término de sucPolFib para x=1 es el n-ésimo término de la sucesión de Fibonacci 0, 1, 1, 2, 3, 5, 8, …

Nota. Limitar la búsqueda a ejemplos pequeños usando

   quickCheckWith (stdArgs {maxSize=5}) prop_polFib

Soluciones


import Data.List (genericIndex)
import I1M.PolOperaciones
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
sucPolFib :: [Polinomio Integer]
sucPolFib = [polFibR n | n <- [0..]]
 
polFibR :: Integer -> Polinomio Integer
polFibR 0 = polCero
polFibR 1 = polUnidad
polFibR n = 
  sumaPol (multPol (consPol 1 1 polCero) (polFibR (n-1)))
          (polFibR (n-2))
 
-- 2ª definición (dinámica)
-- ========================
 
sucPolFib2 :: [Polinomio Integer]
sucPolFib2 = 
  polCero : polUnidad : zipWith f (tail sucPolFib2) sucPolFib2
  where f p = sumaPol (multPol (consPol 1 1 polCero) p)
 
-- La propiedad es
prop_polFib :: Integer -> Property
prop_polFib n = 
    n >= 0 ==> valor (polFib n) 1 == fib n
    where polFib n = sucPolFib2 `genericIndex` n
          fib n    = fibs `genericIndex` n
 
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 
-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=5}) prop_polFib
--    +++ OK, passed 100 tests.

6 soluciones de “Polinomios de Fibonacci

  1. albcercid
     
    import I1M.PolOperaciones
    import Test.QuickCheck
     
    sucPolFib :: [Polinomio Integer]
    sucPolFib = aux polCero (creaTermino 0 1)
           where aux a b = a:aux b (sumaPol a (multPorTerm (creaTermino 1 1) b))
     
    prop :: Int -> Bool
    prop n = fibs!!t == valor (sucPolFib!!t) 1
         where t = abs n
               fibs = aux 0 1
               aux a b = a:aux b (a+b)
  2. enrnarbej
    import I1M.PolOperaciones
    import Data.List
    import Test.QuickCheck
     
    sucPolFib :: [Polinomio Integer]
    sucPolFib = polCero : scanl' f polUnidad sucPolFib
              where
               x = consPol 1 1 polCero 
               f p2 p1 = (sumaPol p1 . multPol x) p2
     
    fib :: [Integer]
    fib = 0 : scanl' (+) 1 fib
     
    prop_polFib :: (Positive Int) -> Bool
    prop_polFib (Positive n) = fib !! n == valor (sucPolFib !! n) 1 
     
    -- *Main> quickCheckWith (stdArgs {maxSize=5}) prop_polFib
    -- +++ OK, passed 100 tests.
    -- (0.02 secs, 1,545,984 bytes)
  3. Cescarde
    import I1M.PolOperaciones
    import Test.QuickCheck
     
    sucPolFib :: [Polinomio Integer]
    sucPolFib = c : scanl (a b -> sumaPol (multPol x a) b) u sucPolFib
              where x = creaTermino 1 1
                    c = polCero
                    u = polUnidad
     
    prop_polFib :: Int -> Bool
    prop_polFib n = fibs!!x == valor (sucPolFib!!x) 1
              where x = abs n
                    fibs = 0 : scanl (+) 1 fibs
  4. marlobrip
    sucPolFib :: [Polinomio Integer]
    sucPolFib = map p [0..]
     
    p :: (Eq a, Eq a1, Num a, Num a1) => a1 -> Polinomio a
    p 0 = polCero
    p 1 = polUnidad
    p n = sumaPol (multPol c (p(n-1))) (p(n-2))
        where c = creaTermino 1 1
     
    fib :: Integer -> Integer
    fib 0 = 0
    fib 1 = 1
    fib n = fib (n-1) + fib (n-2)
     
    prop_fibonnaci :: Int -> Bool
    prop_fibonnaci n = fib(abs n) == valor (p (abs n)) 1
  5. alvfercen
    import I1M.PolOperaciones
    import Test.QuickCheck
     
    sucPolFib :: [Polinomio Integer]
    sucPolFib = [p(n) |n <- [0..]]
     
    p n |n == 0    = polCero
        |n == 1    = polUnidad
        |otherwise = sumaPol (multPol x (p(n-1))) (p(n-2))
        where x = creaTermino 1 1
     
    prop_polFib :: Integer -> Bool
    prop_polFib n = fib(abs n) == valor (p (abs n)) 1
     
    --λ> quickCheckWith (stdArgs {maxSize=5}) prop_polFib
    --+++ OK, passed 100 tests
     
    fib :: Integer -> Integer
    fib 0 = 0
    fib 1 = 1
    fib n = fib (n-1) + fib (n-2)
  6. eliguivil
    import I1M.PolOperaciones
    import Test.QuickCheck
     
    fibs :: [Integer]
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
     
    sucPolFib :: [Polinomio Integer]
    sucPolFib = polCero : p(1) : zipWith f sucPolFib (tail sucPolFib)
      where p(1) = consPol 0 1 polCero
            f p q = p `sumaPol` (multPorTerm x q)
            x = consPol 1 1 polCero
     
    prop :: Int -> Bool
    prop n = valor p 1 == fromIntegral (fibs!!n')
      where n' = abs n
            p  = sucPolFib!!n'
     
    -- λ> quickCheck prop
    -- +++ OK, passed 100 tests.
    -- (0.01 secs, 0 bytes)

Escribe tu solución

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