Triángulo de Pascal binario
Los triángulos binarios de Pascal se formas a partir de una lista de ceros y unos usando las reglas del triángulo de Pascal, donde cada uno de los números es suma módulo dos de los dos situados en diagonal por encima suyo. Por ejemplo, los triángulos binarios de Pascal correspondientes a [1,0,1,1,1] y [1,0,1,1,0] son
|
1 2 3 4 5 |
1 0 1 1 1 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 1 |
Sus finales, desde el extremo inferior al extremos superior derecho, son [0,1,0,0,1] y [1,0,1,1,0], respectivamente.
Una lista es Pascal capicúa si es igual a los finales de su triángulo binario de Pascal. Por ejemplo, [1,0,1,1,0] es Pascal capicúa.
Definir las funciones
|
1 2 3 |
trianguloPascalBinario :: [Int] -> [[Int]] pascalCapicuas :: Int -> [[Int]] nPascalCapicuas :: Int -> Integer |
tales que
- (trianguloPascalBinario xs) es el triágulo binario de Pascal correspondiente a la lista xs. Por ejemplo,
|
1 2 3 4 |
λ> trianguloPascalBinario [1,0,1,1,1] [[1,0,1,1,1],[1,1,0,0],[0,1,0],[1,1],[0]] λ> trianguloPascalBinario [1,0,1,1,0] [[1,0,1,1,0],[1,1,0,1],[0,1,1],[1,0],[1]] |
- (pascalCapicuas n) es la lista de listas de Pascal capicúas de n elementos. Por ejemplo,
|
1 2 3 4 5 6 |
λ> pascalCapicuas 2 [[0,0],[1,0]] λ> pascalCapicuas 3 [[0,0,0],[0,1,0],[1,0,0],[1,1,0]] λ> pascalCapicuas 4 [[0,0,0,0],[0,1,1,0],[1,0,0,0],[1,1,1,0]] |
- (nPascalCapicuas n) es el número de listas de Pascal capicúas de n elementos. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
λ> nPascalCapicuas 2 2 λ> nPascalCapicuas 3 4 λ> nPascalCapicuas 4 4 λ> nPascalCapicuas 400 1606938044258990275541962092341162602522202993782792835301376 λ> length (show (nPascalCapicuas (10^5))) 15052 λ> length (show (nPascalCapicuas (10^6))) 150515 λ> length (show (nPascalCapicuas (10^7))) 1505150 |
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
import Data.List (genericLength, unfoldr) -- Definición de trianguloPascalBinario -- ==================================== trianguloPascalBinario :: [Int] -> [[Int]] trianguloPascalBinario xs = takeWhile (not . null) (iterate siguiente xs) -- (siguiente xs) es la línea siguiente a la xs en el triángulo binario -- de Pascal. Por ejemplo, -- λ> siguiente [1,0,1,1,1] -- [1,1,0,0] -- λ> siguiente it -- [0,1,0] -- λ> siguiente it -- [1,1] -- λ> siguiente it -- [0] -- λ> siguiente it -- [] -- λ> siguiente it -- [] siguiente :: [Int] -> [Int] siguiente xs = [(x + y) `mod` 2 | (x,y) <- zip xs (tail xs)] -- 2ª definición de trianguloPascalBinario -- ======================================= trianguloPascalBinario2 :: [Int] -> [[Int]] trianguloPascalBinario2 = unfoldr f where f [] = Nothing f xs = Just (xs, siguiente xs) -- Definición de pascalCapicuas -- ============================ pascalCapicuas :: Int -> [[Int]] pascalCapicuas n = [xs | xs <- inicios n , esPascalCapicua xs] -- (inicios n) es la lista de longitud n formadas por ceros y unos. Por -- ejemplo, -- λ> inicios 0 -- [[]] -- λ> inicios 1 -- [[0],[1]] -- λ> inicios 2 -- [[0,0],[0,1],[1,0],[1,1]] -- λ> inicios 3 -- [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]] inicios :: Int -> [[Int]] inicios 0 = [[]] inicios n = map (0:) xss ++ map (1:) xss where xss = inicios (n-1) -- Otra forma de definir inicios es inicios2 :: Int -> [[Int]] inicios2 n = sucInicios !! n where sucInicios = iterate siguiente [[]] siguiente xss = map (0:) xss ++ map (1:) xss -- (esPascalCapicua xs) se verifica si xs es una lista de Pascal -- capicúa. Por ejemplo, -- esPascalCapicua [1,0,1,1,0] == True -- esPascalCapicua [1,0,1,1,1] == False esPascalCapicua :: [Int] -> Bool esPascalCapicua xs = xs == finalesTrianguloPascalBinario xs -- (finalesTrianguloPascalBinario xs) es la inversa de la lista de los -- finales del triángulo binarios de xs. Por ejemplo, -- λ> finalesTrianguloPascalBinario [1,0,1,1,1] -- [0,1,0,0,1] finalesTrianguloPascalBinario :: [Int] -> [Int] finalesTrianguloPascalBinario = reverse . map last . trianguloPascalBinario -- 1ª definición de nPascalCapicuas -- ================================ nPascalCapicuas :: Int -> Integer nPascalCapicuas = genericLength . pascalCapicuas -- 2ª definición de nPascalCapicuas -- ================================ nPascalCapicuas2 :: Int -> Integer nPascalCapicuas2 n = 2 ^ ((n + 1) `div` 2) |
Pensamiento
La envidia de la virtud
hizo a Caín criminal.
¡Gloria a Caín! Hoy el vicio
es lo que se envidia más.Antonio Machado
4 Comentarios