El número 6 se puede descomponer de 4 formas distintas como suma con sumandos distintos:
6 = 1 + 2 + 3
6 = 1 + 5
6 = 2 + 4
6 = 6 |
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:
6 = 1 + 1 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 3
6 = 1 + 5
6 = 3 + 3 |
6 = 1 + 1 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 3
6 = 1 + 5
6 = 3 + 3
Definir las siguientes funciones
sumasSumandosDistintos :: Integer -> [[Integer]]
nSumasSumandosDistintos :: Integer -> Int
sumasSumandosImpares :: Integer -> [[Integer]]
nSumasSumandosImpares :: Integer -> Int
igualdadDeSumas :: Integer -> Bool |
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,
sumasSumandosDistintos 5 == [[1,4],[2,3],[5]]
sumasSumandosDistintos 6 == [[1,2,3],[1,5],[2,4],[6]] |
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,
nSumasSumandosDistintos 6 == 4
nSumasSumandosDistintos 7 == 5 |
nSumasSumandosDistintos 6 == 4
nSumasSumandosDistintos 7 == 5
- (sumasSumandosImpares n) es la lista de las descomposiones de n como sumas con sumandos impares. Por ejemplo,
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]] |
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,
nSumasSumandosImpares 6 == 4
nSumasSumandosImpares 7 == 5 |
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,
igualdadDeSumas 40 == True |
igualdadDeSumas 40 == True
Soluciones
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) |
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)
Se puede imprimir o compartir con
5 soluciones de “Sumas con sumandos distintos o con sumandos impares”