Ceros con los n primeros números
Los números del 1 al 3 se pueden escribir de dos formas, con el signo más o menos entre ellos, tales que su suma sea 0:
|
1 2 |
1+2-3 = 0 -1-2+3 = 0 |
Definir la función
|
1 |
ceros :: Int -> [[Int]] |
tal que (ceros n) son las posibles formas de obtener cero sumando los números del 1 al n, con el signo más o menos entre ellos. Por ejemplo,
|
1 2 3 4 5 |
ceros 3 == [[1,2,-3],[-1,-2,3]] ceros 4 == [[1,-2,-3,4],[-1,2,3,-4]] ceros 5 == [] length (ceros 7) == 8 take 3 (ceros 7) == [[1,2,-3,4,-5,-6,7],[1,2,-3,-4,5,6,-7],[1,-2,3,4,-5,6,-7]] |
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 |
-- 1ª solución -- =========== ceros :: Int -> [[Int]] ceros n = [xs | xs <- candidatos n, sum xs == 0] -- (candidatos n) es la lista de los números del 1 al n con los signos -- más o menos. Por ejemplo, -- λ> candidatos 1 -- [[1],[-1]] -- λ> candidatos 2 -- [[1,2],[1,-2],[-1,2],[-1,-2]] -- λ> candidatos 3 -- [[1,2,3],[1,2,-3],[1,-2,3],[1,-2,-3],[-1,2,3],[-1,2,-3],[-1,-2,3],[-1,-2,-3]] candidatos :: Int -> [[Int]] candidatos n = productoCartesiano [[i,-i] | i <- [1..n]] -- (productoCartesiano xss) es el producto cartesiano de los conjuntos -- xss. Por ejemplo, -- λ> productoCartesiano [[1,3],[2,5],[6,4]] -- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] productoCartesiano :: [[a]] -> [[a]] productoCartesiano [] = [[]] productoCartesiano (xs:xss) = [x:ys | x <- xs, ys <- productoCartesiano xss] -- 2ª solución -- =========== ceros2 :: Int -> [[Int]] ceros2 n = [xs | xs <- candidatos2 n, sum xs == 0] candidatos2 :: Int -> [[Int]] candidatos2 n = mapM (\i -> [i,-i]) [1..n] -- 3ª solución -- =========== ceros3 :: Int -> [[Int]] ceros3 n = [xs | xs <- mapM (\i -> [i,-i]) [1..n], sum xs == 0] -- 4ª solución -- =========== ceros4 :: Integer -> [[Integer]] ceros4 = map fst . filter ((==0) . snd) . sumas -- (sumas n) es la lista de las candidatos con los n primeros números y -- sus sumas. Por ejemplo, -- λ> sumas 2 -- [([1,2],3),([-1,2],1),([1,-2],-1),([-1,-2],-3)] -- λ> sumas 3 -- [([1,2,3],6),([-1,2,3],4),([1,-2,3],2),([-1,-2,3],0),([1,2,-3],0), -- ([-1,2,-3],-2),([1,-2,-3],-4),([-1,-2,-3],-6)] sumas :: Integer -> [([Integer],Integer)] sumas = foldr aux [([], 0)] . enumFromTo 1 where aux n = concatMap (\(ns', s') -> [(n : ns', s' + n), (-n : ns', s' - n)]) -- Comparación de eficiencia -- ========================= -- λ> length (ceros 18) -- 0 -- (4.14 secs, 1,094,854,776 bytes) -- λ> length (ceros2 18) -- 0 -- (1.16 secs, 375,541,680 bytes) -- λ> length (ceros3 18) -- 0 -- (1.13 secs, 375,540,192 bytes) -- λ> length (ceros4 18) -- 0 -- (0.69 secs, 157,316,688 bytes) |