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
[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″]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
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]
Se puede imprimir o compartir con