Ir al contenido principal

Números construibles como sumas de dos dados

Un número x es construible a partir de a y b si se puede escribir como una suma cuyos sumandos son a o b (donde se supone que a y be son números enteros mayores que 0). Por ejemplo, 7 y 9 son construibles a partir de 2 y 3 ya que 7 = 2+2+3 y 9 = 3+3+3.

Definir las funciones

construibles  :: Integer -> Integer -> [Integer]
esConstruible :: Integer -> Integer -> Integer -> Bool

tales que

  • (construibles a b) es la lista de los números construibles a partir de a y b. Por ejemplo,
take 5 (construibles 2 9)  ==  [2,4,6,8,9]
take 5 (construibles 6 4)  ==  [4,6,8,10,12]
take 5 (construibles 9 7)  ==  [7,9,14,16,18]
  • (esConstruible a b x) se verifica si x es construible a partir de a y b. Por ejemplo,
esConstruible 2 3 7   ==  True
esConstruible 9 7 15  ==  False

Soluciones

import Data.List (nub)

construibles :: Integer -> Integer -> [Integer]
construibles a b = tail aux
  where aux = 0 : mezcla [a + x | x <- aux]
                         [b + x | x <- aux]

mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla p@(x:xs) q@(y:ys) | x < y     = x : mezcla xs q
                         | x > y     = y : mezcla p  ys
                         | otherwise = x : mezcla xs ys
mezcla []       ys                   = ys
mezcla xs       []                   = xs

esConstruible :: Integer -> Integer -> Integer -> Bool
esConstruible a b x = x == y
  where (y:_) = dropWhile (<x) (construibles a b)