Descomposición de N en K sumandos pares distintos

Definir las funciones

   sumas  :: Integer -> Integer -> [[Integer]]
   esSuma :: Integer -> Integer -> Bool

1 2	sumas :: Integer -> Integer -> [[Integer]] esSuma :: Integer -> Integer -> Bool

tales que

(sumas n k) es la lista de las descomposiones de n en k sumandos pares y distintos. Por ejemplo,

     sumas 16 3  ==  [[2,4,10],[2,6,8]]
     sumas 18 4  ==  []

1 2	sumas 16 3 == [[2,4,10],[2,6,8]] sumas 18 4 == []

(esSuma n k) se verifica si n se puede escribir como suma de k sumandos pares y distintos. Por ejemplo,

     esSuma 16 3  ==  True
     esSuma 18 4  ==  False
     esSuma (10^5000) (10^7)  ==  True
     esSuma (11^5000) (10^7)  ==  False

esSuma 16 3 == True

esSuma 18 4 == False

esSuma (10^5000) (10^7) == True

esSuma (11^5000) (10^7) == False

Soluciones

import Test.QuickCheck

sumas :: Integer -> Integer -> [[Integer]]
sumas n k = sumasLista n k [2,4..n]

-- (sumasLista n k xs) es la lista de las descomposiciones de n como k
-- elementos de xs (cada uno una vez como máximo). Por ejemplo,
--    sumasLista 16 3 [2,4..15]  ==  [[2,4,10],[2,6,8]]
--    sumasLista 18 4 [2,4..15]  ==  []
sumasLista :: Integer -> Integer -> [Integer] -> [[Integer]]
sumasLista _ _ [] = []
sumasLista n 1 xs
  | n `elem` xs = [[n]]
  | otherwise   = []
sumasLista n k (x:xs)
  | x > n     = []
  | otherwise = [x:ys | ys <- sumasLista (n-x) (k-1) xs] ++
                sumasLista n k xs

-- 1ª definición de esSuma
-- =======================

esSuma :: Integer -> Integer -> Bool
esSuma n k = not (null (sumas n k))

-- 2ª definición de esSuma
-- =======================

-- Se observan las siguientes propiedades:
-- 1. Si n es impar, no se puede escribir como suma de pares.
-- 2. El menor número que se puede escribir como suma de k sumandos
--    impares distintos es 2 * sum [1..k] y su descomposición es
--    [2,4..2*k] (es decir, map (*2) [1..k]).
-- 3. Si n es un número par mayor o igual que (2 * sum [1..k])
--    entonces se puede escribir como suma de k sumandos pares distintos;
--    en efecto,
--       x = 2 + 4 + ··· + 2*(k-1) + (x - (2 + 4 + ··· + 2*(k-1))

esSuma2 :: Integer -> Integer -> Bool
esSuma2 n k
  | odd n               = False
  | 2 * sum [1..k] <= n = True
  | otherwise           = False

-- 3ª definición de esSuma
-- =======================

esSuma3 :: Integer -> Integer -> Bool
esSuma3 n k
  | odd n            = False
  | k * (k + 1) <= n = True
  | otherwise        = False

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_equiv_esSuma :: Integer -> Integer -> Property
prop_equiv_esSuma n k =
  n > 0 && k > 0 ==>
  all (== (esSuma3 n k)) [esSuma n k, esSuma2 n k]

-- La comprobación es
--    λ> quickCheck prop_equiv_esSuma
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> esSuma 200 20
--    False
--    (6.12 secs, 3,079,059,560 bytes)
--    λ> esSuma2 200 20
--    False
--    (0.00 secs, 102,800 bytes)
--    λ> esSuma3 200 20
--    False
--    (0.01 secs, 102,760 bytes)
--
--    λ> esSuma2 (10^5000) (10^7)
--    True
--    (2.55 secs, 1,612,412,664 bytes)
--    λ> esSuma3 (10^5000) (10^7)
--    True
--    (0.03 secs, 109,200 bytes)

import Test.QuickCheck

sumas :: Integer -> Integer -> [[Integer]]

sumas n k = sumasLista n k [2,4..n]

-- (sumasLista n k xs) es la lista de las descomposiciones de n como k

-- elementos de xs (cada uno una vez como máximo). Por ejemplo,

-- sumasLista 16 3 [2,4..15] == [[2,4,10],[2,6,8]]

-- sumasLista 18 4 [2,4..15] == []

sumasLista :: Integer -> Integer -> [Integer] -> [[Integer]]

sumasLista _ _ [] = []

sumasLista n 1 xs

| n `elem` xs = [[n]]

| otherwise = []

sumasLista n k (x:xs)

| x > n = []

| otherwise = [x:ys | ys <- sumasLista (n-x) (k-1) xs] ++

sumasLista n k xs

-- 1ª definición de esSuma

-- =======================

esSuma :: Integer -> Integer -> Bool

esSuma n k = not (null (sumas n k))

-- 2ª definición de esSuma

-- =======================

-- Se observan las siguientes propiedades:

-- 1. Si n es impar, no se puede escribir como suma de pares.

-- 2. El menor número que se puede escribir como suma de k sumandos

-- impares distintos es 2 * sum [1..k] y su descomposición es

-- [2,4..2*k] (es decir, map (*2) [1..k]).

-- 3. Si n es un número par mayor o igual que (2 * sum [1..k])

-- entonces se puede escribir como suma de k sumandos pares distintos;

-- en efecto,

-- x = 2 + 4 + ··· + 2*(k-1) + (x - (2 + 4 + ··· + 2*(k-1))

esSuma2 :: Integer -> Integer -> Bool

esSuma2 n k

| odd n = False

| 2 * sum [1..k] <= n = True

| otherwise = False

-- 3ª definición de esSuma

-- =======================

esSuma3 :: Integer -> Integer -> Bool

esSuma3 n k

| odd n = False

| k * (k + 1) <= n = True

| otherwise = False

-- Comprobación de equivalencia

-- ============================

-- La propiedad es

prop_equiv_esSuma :: Integer -> Integer -> Property

prop_equiv_esSuma n k =

n > 0 && k > 0 ==>

all (== (esSuma3 n k)) [esSuma n k, esSuma2 n k]

-- La comprobación es

-- λ> quickCheck prop_equiv_esSuma

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

-- =========================

-- La comparación es

-- λ> esSuma 200 20

-- False

-- (6.12 secs, 3,079,059,560 bytes)

-- λ> esSuma2 200 20

-- False

-- (0.00 secs, 102,800 bytes)

-- λ> esSuma3 200 20

-- False

-- (0.01 secs, 102,760 bytes)

-- λ> esSuma2 (10^5000) (10^7)

-- True

-- (2.55 secs, 1,612,412,664 bytes)

-- λ> esSuma3 (10^5000) (10^7)

-- True

-- (0.03 secs, 109,200 bytes)

Nuevas soluciones

En los comentarios se pueden escribir nuevas soluciones.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

3 Comentarios

import Data.List

sumas  :: Integer -> Integer -> [[Integer]]
sumas n k = sumlength n k (subsequences (listapares n))
           
-- La función "sumlength n k xs" nos devuelve una lista formada por listas cuya longitud
-- es k y cuya suma de elementos es n.

sumlength :: Integer -> Integer -> [[Integer]]-> [[Integer]]
sumlength n k [] = []
sumlength n k (xs:xss) |sum xs == n && length xs == (fromIntegral k) = xs: (sumlength n k xss)
                       |otherwise = sumlength n k xss
            
-- La función "listapares x" nos devuelve la lista de números pares del 1 hasta
-- el x.

listapares :: Integer -> [Integer]
listapares x = [y | y<- [1..x], mod y 2 == 0]

                  
esSuma :: Integer -> Integer -> Bool
esSuma n k  |(sumas n k) == [] = False
            |otherwise = True

import Data.List

sumas :: Integer -> Integer -> [[Integer]]

sumas n k = sumlength n k (subsequences (listapares n))

-- La función "sumlength n k xs" nos devuelve una lista formada por listas cuya longitud

-- es k y cuya suma de elementos es n.

sumlength :: Integer -> Integer -> [[Integer]]-> [[Integer]]

sumlength n k [] = []

sumlength n k (xs:xss) |sum xs == n && length xs == (fromIntegral k) = xs: (sumlength n k xss)

|otherwise = sumlength n k xss

-- La función "listapares x" nos devuelve la lista de números pares del 1 hasta

-- el x.

listapares :: Integer -> [Integer]

listapares x = [y | y<- [1..x], mod y 2 == 0]

esSuma :: Integer -> Integer -> Bool

esSuma n k |(sumas n k) == [] = False

|otherwise = True

Responder

-- Una solución más breve:

import Data.List

sumas  :: Integer -> Integer -> [[Integer]]
sumas n k = filter p (subsequences (listapares n))
             where p xs = length xs == (fromIntegral k) && sum xs == n
                   listapares x = [y | y<- [1..x], mod y 2 == 0]

                  
esSuma :: Integer -> Integer -> Bool
esSuma n k  |sumas n k == [] = False
            |otherwise = True

-- Una solución más breve:

import Data.List

sumas :: Integer -> Integer -> [[Integer]]

sumas n k = filter p (subsequences (listapares n))

where p xs = length xs == (fromIntegral k) && sum xs == n

listapares x = [y | y<- [1..x], mod y 2 == 0]

esSuma :: Integer -> Integer -> Bool

esSuma n k |sumas n k == [] = False

|otherwise = True

Responder

sumas :: Integer -> Integer -> [[Integer]]
sumas n k = aux n m m
  where m = fromIntegral k

-- aux n m k funciona al igual que sumas n k; sin embargo, al introducir el
-- factor m en esta función nos podemos asegurar de que si el elemento que
-- ocupa la posición i en una lista de k elementos con suma n es un determinado
-- número par, entonces el elemento de la posición (i+1) debe ser, como mínimo,
-- el número par siguiente al anterior.

aux :: Integer -> Int -> Int -> [[Integer]]
aux n m k
  | k <= 0 = [[]]
  | k == 1 = [[n]]
  | odd n  = [[]]
  | otherwise = filter creciente (concat
      [map (x:) (aux (n-x) m (k-1)) | x <- drop (m-k) [2,4..p]])
        where p = div n q - div q 2
              q = fromIntegral k

-- creciente xs se verifica si xs es estrictamente creciente. Con esta función
-- podemos eliminar las listas de k elementos con suma n que no son válidas de
-- acuerdo a la definición de sumas n k.

creciente :: [Integer] -> Bool
creciente []  = True
creciente [x] = True
creciente (x:y:zs) = x < y && creciente (y:zs)

esSuma :: Integer -> Integer -> Bool
esSuma n k = not (null (sumas n k))

sumas :: Integer -> Integer -> [[Integer]]

sumas n k = aux n m m

where m = fromIntegral k

-- aux n m k funciona al igual que sumas n k; sin embargo, al introducir el

-- factor m en esta función nos podemos asegurar de que si el elemento que

-- ocupa la posición i en una lista de k elementos con suma n es un determinado

-- número par, entonces el elemento de la posición (i+1) debe ser, como mínimo,

-- el número par siguiente al anterior.

aux :: Integer -> Int -> Int -> [[Integer]]

aux n m k

| k <= 0 = [[]]

| k == 1 = [[n]]

| odd n = [[]]

| otherwise = filter creciente (concat

[map (x:) (aux (n-x) m (k-1)) | x <- drop (m-k) [2,4..p]])

where p = div n q - div q 2

q = fromIntegral k

-- creciente xs se verifica si xs es estrictamente creciente. Con esta función

-- podemos eliminar las listas de k elementos con suma n que no son válidas de

-- acuerdo a la definición de sumas n k.

creciente :: [Integer] -> Bool

creciente [] = True

creciente [x] = True

creciente (x:y:zs) = x < y && creciente (y:zs)

esSuma :: Integer -> Integer -> Bool

esSuma n k = not (null (sumas n k))

Responder

Descomposición de N en K sumandos pares distintos

Soluciones

Nuevas soluciones

3 Comentarios

Leave a Reply to Mercedes Vega GalloCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Nuevas soluciones

Se puede imprimir o compartir con

3 Comentarios

Leave a Reply to Mercedes Vega GalloCancel reply

Entradas recientes

Buscar

Correo electrónico