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.

3 soluciones de “Polinomios de Fibonacci

  1. angruicam1
    import Data.Array (array, (!))
    import Test.QuickCheck
    import I1M.PolOperaciones
     
    sucPolFib :: [Polinomio Integer]
    sucPolFib = aux polCero polUnidad
      where aux a b = a : aux b (sumaPol a (multPol b (creaTermino 1 1)))
     
    -- Propiedad
    -- =========
     
    -- La propiedad es
    prop_polFib :: (NonNegative Int) -> Bool
    prop_polFib (NonNegative n) = valor (sucPolFib !! n) 1 == fib ! n
      where fib = array (0,n) [(i,f i) | i <- [0..n]]
            f 0 = 0
            f 1 = 1
            f n = fib!(n-1) + fib!(n-2)
     
    -- La comprobación es
    --    λ> quickCheckWith (stdArgs{maxSize=5}) prop_polFib
    --    +++ OK, passed 100 tests.
  2. alerodrod5

    una solución alternativa a sucPolFib

     
    import I1M.PolOperaciones
     
     
    sucPolFib :: [Polinomio Integer]
    sucPolFib = polCero : polUnidad : [f x y | (x,y)<- zip sucPolFib (tail sucPolFib)]
      where f x y =sumaPol ( multPol y (creaTermino 1 1))  x
  3. albcarcas1

    Otra solución para la sucesión de polinomios, parecida a la de alerodrod

    import I1M.PolOperaciones
     
    sucPolFib :: [Polinomio Integer]
    sucPolFib = (polCero):(polUnidad):(zipWith (f) sucPolFib (tail sucPolFib))
      where f x y =sumaPol(multPol y (creaTermino 1 1)) x

Escribe tu solución

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