Sumas con sumandos distintos o con sumandos impares
El número 6 se puede descomponer de 4 formas distintas como suma con sumandos distintos:
|
1 2 3 4 |
6 = 1 + 2 + 3 6 = 1 + 5 6 = 2 + 4 6 = 6 |
y también se puede descomponer de 4 formas distintas como suma con sumandos impares:
|
1 2 3 4 |
6 = 1 + 1 + 1 + 1 + 1 + 1 6 = 1 + 1 + 1 + 3 6 = 1 + 5 6 = 3 + 3 |
Definir las siguientes funciones
|
1 2 3 4 5 |
sumasSumandosDistintos :: Integer -> [[Integer]] nSumasSumandosDistintos :: Integer -> Int sumasSumandosImpares :: Integer -> [[Integer]] nSumasSumandosImpares :: Integer -> Int igualdadDeSumas :: Integer -> Bool |
tales que
- (sumasSumandosDistintos n) es la lista de las descomposiciones de n como sumas con sumandos distintos. Por ejemplo,
|
1 2 |
sumasSumandosDistintos 5 == [[1,4],[2,3],[5]] sumasSumandosDistintos 6 == [[1,2,3],[1,5],[2,4],[6]] |
- (nSumasSumandosDistintos n) es el número de descomposiciones de n como sumas con sumandos distintos. Por ejemplo,
|
1 2 |
nSumasSumandosDistintos 6 == 4 nSumasSumandosDistintos 7 == 5 |
- (sumasSumandosImpares n) es la lista de las descomposiones de n como sumas con sumandos impares. Por ejemplo,
|
1 2 |
sumasSumandosImpares 5 == [[1,1,1,1,1],[1,1,3],[5]] sumasSumandosImpares 6 == [[1,1,1,1,1,1],[1,1,1,3],[1,5],[3,3]] |
- (nSumasSumandosImpares n) es el número de descomposiciones de n como sumas con sumandos impares. Por ejemplo,
|
1 2 |
nSumasSumandosImpares 6 == 4 nSumasSumandosImpares 7 == 5 |
- (igualdadDeSumas n) se verifica si, para todo k entre 1 y n, las funciones nSumasSumandosDistintos y nSumasSumandosImpares son iguales. Por ejemplo,
|
1 |
igualdadDeSumas 40 == True |
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 93 94 95 96 97 98 99 100 |
import Data.List (delete, nub) -- Definiciones de sumasSumandosDistintos -- ====================================== -- 1ª definición sumasSumandosDistintos sumasSumandosDistintos :: Integer -> [[Integer]] sumasSumandosDistintos n = aux n [1..n] where aux 0 _ = [[]] aux _ [] = [] aux x ys@(y:_) | x < y = [] | x == y = [[x]] | otherwise = [z : zs | z <- ys , zs <- aux (x - z) (dropWhile (<=z) ys)] -- 2ª definición de sumasSumandosDistintos sumasSumandosDistintos2 :: Integer ->[[Integer]] sumasSumandosDistintos2 = aux 0 where aux i z | z < 0 = [] | z == 0 = [[]] | z > 0 = concat [map (j:) (aux j (z-j)) | j <- [i+1..z]] -- Definición de nSumasSumandosDistintos -- ===================================== nSumasSumandosDistintos :: Integer -> Int nSumasSumandosDistintos = length . sumasSumandosDistintos -- Definiciones de sumasSumandosImpares -- ==================================== -- 1ª definición de sumasSumandosImpares sumasSumandosImpares :: Integer -> [[Integer]] sumasSumandosImpares n = aux n [1,3..n] where aux n _ | n < 0 = [] aux 0 _ = [[]] aux _ [] = [] aux x zs@(y:ys) = [y:zs | zs <- aux (x-y) zs] ++ aux x ys -- 2ª definición de sumasSumandosImpares sumasSumandosImpares2 :: Integer ->[[Integer]] sumasSumandosImpares2 = aux 1 where aux i z | z < 0 = [] | z == 0 = [[]] | z > 0 = concat [map (j:) (aux j (z-j)) | j <-[i,i+2..z]] -- Definición de nSumasSumandosImpares -- =================================== nSumasSumandosImpares :: Integer -> Int nSumasSumandosImpares = length . sumasSumandosImpares -- Definición conjunta (de josejuan) -- ================================= -- podemos definir una gran familia de generadores de la siguiente forma sumas :: Integer ->Integer ->Integer ->Integer ->Integer ->[[Integer]] sumas u a b k n = s u n where s i z | z < 0 = [] | z == 0 = [[]] | z > 0 = concat [map (j:) (s j (z - j)) | j <-[k*i+a,k*i+b..z]] -- así, si queremos los distintos sumasSumandosDistintos3 :: Integer ->[[Integer]] sumasSumandosDistintos3 = sumas 0 1 2 1 -- o queremos los impares repetidos sumasSumandosImpares3 :: Integer ->[[Integer]] sumasSumandosImpares3 = sumas 1 0 2 1 -- Igualdad de las sumas -- ===================== igualdadDeSumas :: Integer -> Bool igualdadDeSumas n = and [nSumasSumandosDistintos k == nSumasSumandosImpares k | k <- [1..n]] -- Comparación de eficiencia -- ========================= -- λ> length (sumasSumandosDistintos2 70) -- 29927 -- (0.57 secs, 374,604,848 bytes) -- λ> length (sumasSumandosDistintos3 70) -- 29927 -- (0.57 secs, 352,658,200 bytes) -- λ> length (sumasSumandosImpares 70) -- 29927 -- (8.87 secs, 5,221,638,688 bytes) -- λ> length (sumasSumandosImpares2 70) -- 29927 -- (0.61 secs, 422,132,696 bytes) -- λ> length (sumasSumandosImpares3 70) -- 29927 -- (0.56 secs, 412,289,336 bytes) |
5 Comentarios