Triángulo de Bell
El triágulo de Bell es el triángulo numérico, cuya primera fila es [1] y en cada fila, el primer elemento es el último de la fila anterior y el elemento en la posición j se obtiene sumando el elemento anterior de su misma fila y de la fila anterior. Sus primeras filas son
|
1 2 3 4 5 6 |
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 52 67 87 114 151 203 |
Definir la función
|
1 |
trianguloDeBell :: [[Integer]] |
tal que trianguloDeBell es la lista con las filas de dicho triángulo. Por ejemplo
|
1 2 |
λ> take 5 trianguloDeBell [[1],[1,2],[2,3,5],[5,7,10,15],[15,20,27,37,52]] |
Comprobar con QuickCheck que los números que aparecen en la primera columna del triángulo coinciden con los números de Bell; es decir, el primer elemento de la n-ésima fila es el n-ésimo número de Bell.
Soluciones
|
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 39 40 |
import Data.List (genericIndex, genericLength) import Test.QuickCheck trianguloDeBell :: [[Integer]] trianguloDeBell = iterate siguiente [1] -- (siguiente xs) es la fila siguiente de xs en el triángulo de -- Bell. Por ejemplo, -- siguiente [1] == [1,2] -- siguiente [1,2] == [2,3,5] -- siguiente [2,3,5] == [5,7,10,15] siguiente :: [Integer] -> [Integer] siguiente xs = last xs : zipWith (+) xs (siguiente xs) -- Propiedad -- ========= -- La propiedad es prop_TrianguloDeBell :: Integer -> Property prop_TrianguloDeBell n = n > 0 ==> head (trianguloDeBell `genericIndex` n) == bell n -- (bell n) es el n-ésimo número de Bell definido en el ejercicio -- anterior. bell :: Integer -> Integer bell n = genericLength (particiones [1..n]) particiones :: [a] -> [[[a]]] particiones [] = [[]] particiones (x:xs) = concat [([x] : yss) : inserta x yss | yss <- ysss] where ysss = particiones xs inserta :: a -> [[a]] -> [[[a]]] inserta _ [] = [] inserta x (ys:yss) = ((x:ys):yss) : [ys : zs | zs <- inserta x yss] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=10}) prop_TrianguloDeBell -- +++ OK, passed 100 tests. |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
Pensamiento
«La ciencia es lo que entendemos lo suficientemente bien como para explicarle a una computadora. El arte es todo lo demás.»
Un comentario