Sumas de tres capicúas
Definir la función
|
1 |
sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)] |
tales que (sumas3Capicuas x) es la lista de las descomposiciones de x como suma de tres capicúas (con los sumandos no decrecientes). Por ejemplo,
|
1 2 3 4 5 6 7 8 |
sumas3Capicuas 0 == [(0,0,0)] sumas3Capicuas 1 == [(0,0,1)] sumas3Capicuas 2 == [(0,0,2),(0,1,1)] sumas3Capicuas 3 == [(0,0,3),(0,1,2),(1,1,1)] sumas3Capicuas 4 == [(0,0,4),(0,1,3),(0,2,2),(1,1,2)] length (sumas3Capicuas 17) == 17 length (sumas3Capicuas 2017) == 47 length (sumas3Capicuas 999999) == 15266 |
Comprobar con QuickCheck que todo número natural se puede escribir como suma de tres capicúas.
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 |
import Test.QuickCheck sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)] sumas3Capicuas x = [(a,b,c) | a <- as , b <- dropWhile (< a) as , let c = x - a - b , b <= c , esCapicua c] where as = takeWhile (<= x) capicuas -- capicuas es la sucesión de los números capicúas. Por ejemplo, -- λ> take 45 capicuas -- [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131, -- 141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292, -- 303,313,323,333,343,353] -- Se usará la 2ª definición del ejercicio "Sucesión de capicúas". capicuas :: [Integer] capicuas = capicuasImpares `mezcla` capicuasPares -- capicuasPares es la sucesión del cero y las capicúas con un número -- par de dígitos. Por ejemplo, -- λ> take 17 capicuasPares -- [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661] capicuasPares :: [Integer] capicuasPares = [read (ns ++ reverse ns) | n <- [0..] , let ns = show n] -- capicuasImpares es la sucesión de las capicúas con un número -- impar de dígitos a partir de 1. Por ejemplo, -- λ> take 20 capicuasImpares -- [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202] capicuasImpares :: [Integer] capicuasImpares = [1..9] ++ [read (ns ++ [z] ++ reverse ns) | n <- [1..] , let ns = show n , z <- "0123456789"] -- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas -- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos -- distintos. Por ejemplo, -- take 10 (mezcla [2,12..] [5,15..]) == [2,5,12,15,22,25,32,35,42,45] -- take 10 (mezcla [2,22..] [5,15..]) == [2,5,15,22,25,35,42,45,55,62] mezcla :: Ord a => [a] -> [a] -> [a] mezcla us@(x:xs) vs@(y:ys) | x < y = x : mezcla xs vs | otherwise = y : mezcla us ys -- (esCapicua x) se verifica si x es capicúa. Por ejemplo, -- esCapicua 353 == True -- esCapicua 3553 == True -- esCapicua 3535 == False esCapicua :: Integer -> Bool esCapicua x = xs == reverse xs where xs = show x -- La propiedad es prop_sumas3Capicuas :: Integer -> Property prop_sumas3Capicuas x = x >= 0 ==> not (null (sumas3Capicuas x)) -- La comprobación es -- λ> quickCheck prop_sumas3Capicuas -- +++ OK, passed 100 tests. |