Polinomios de Fibonacci

PorJosé A. Alonso 23-mayo-201726-marzo-2022

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)

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

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]

1	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

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

1	quickCheckWith (stdArgs {maxSize=5}) prop_polFib

Soluciones

[schedule expon=’2017-05-30′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 30 de mayo.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2017-05-30′ at=»06:00″]

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.

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.

[/schedule]

6 Comentarios

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)

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)

Responder

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)

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)

Responder

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

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

Responder

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

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

Responder

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)

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)

Responder

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)

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)

Responder

Polinomios de Fibonacci

Soluciones

6 Comentarios

Leave a Reply to alvfercenCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

6 Comentarios

Leave a Reply to alvfercenCancel reply

Entradas recientes

Buscar

Correo electrónico