Descomposiciones triangulares
Los números triangulares se forman como sigue
|
1 2 3 4 |
* * * * * * * * * * 1 3 6 |
La sucesión de los números triangulares se obtiene sumando los números naturales. Así, los 5 primeros números triangulares son
|
1 2 3 4 5 |
1 = 1 3 = 1 + 2 6 = 1 + 2 + 3 10 = 1 + 2 + 3 + 4 15 = 1 + 2 + 3 + 4 + 5 |
Definir la función
|
1 |
descomposicionesTriangulares :: Int -> [(Int, Int, Int)] |
tal que (descomposicionesTriangulares n) es la lista de las ternas correspondientes a las descomposiciones de n en tres sumandos formados por números triangulares. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
descomposicionesTriangulares 4 == [] descomposicionesTriangulares 5 == [(1,1,3)] descomposicionesTriangulares 12 == [(1,1,10),(3,3,6)] descomposicionesTriangulares 30 == [(1,1,28),(3,6,21),(10,10,10)] descomposicionesTriangulares 61 == [(1,15,45),(3,3,55),(6,10,45),(10,15,36)] descomposicionesTriangulares 52 == [(1,6,45),(1,15,36),(3,21,28),(6,10,36),(10,21,21)] descomposicionesTriangulares 82 == [(1,3,78),(1,15,66),(1,36,45),(6,10,66),(6,21,55),(10,36,36)] length (descomposicionesTriangulares (5*10^5)) == 124 |
Soluciones
[schedule expon=’2022-04-20′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
[/schedule]
[schedule on=’2022-04-20′ at=»06:00″]
|
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 |
import Test.QuickCheck -- 1ª solución -- =========== descomposicionesTriangulares1 :: Int -> [(Int, Int, Int)] descomposicionesTriangulares1 n = [(x,y,z) | x <- xs, y <- xs, z <- xs, x <= y && y <= z, x + y + z == n] where xs = takeWhile (<=n) triangulares -- triangulares es la lista de los números triangulares. Por ejemplo, -- take 9 triangulares == [1,3,6,10,15,21,28,36,45] triangulares :: [Int] triangulares = scanl (+) 1 [2..] -- 2ª solución -- =========== descomposicionesTriangulares2 :: Int -> [(Int, Int, Int)] descomposicionesTriangulares2 n = [(x,y,z) | x <- xs, y <- xs, x <= y, z <- xs, y <= z, x + y + z == n] where xs = takeWhile (<=n) triangulares -- 3ª solución -- =========== descomposicionesTriangulares3 :: Int -> [(Int, Int, Int)] descomposicionesTriangulares3 n = [(x,y,z) | x <- xs, y <- xs, x <= y, let z = n - x - y, y <= z, z `elem` xs] where xs = takeWhile (<=n) triangulares -- 4ª solución -- =========== descomposicionesTriangulares4 :: Int -> [(Int, Int, Int)] descomposicionesTriangulares4 n = [(x,y,n-x-y) | x <- xs, y <- dropWhile (<x) xs, let z = n - x - y, y <= z, z `elem` xs] where xs = takeWhile (<=n) triangulares -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_descomposicionesTriangulares :: Positive Int -> Bool prop_descomposicionesTriangulares (Positive n) = all (== descomposicionesTriangulares1 n) [descomposicionesTriangulares2 n, descomposicionesTriangulares3 n, descomposicionesTriangulares4 n] -- La comprobación es -- λ> quickCheck prop_descomposicionesTriangulares -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> last (descomposicionesTriangulares1 (2*10^4)) -- (5671,6328,8001) -- (3.34 secs, 1,469,517,168 bytes) -- λ> last (descomposicionesTriangulares2 (2*10^4)) -- (5671,6328,8001) -- (1.29 secs, 461,433,928 bytes) -- λ> last (descomposicionesTriangulares3 (2*10^4)) -- (5671,6328,8001) -- (0.08 secs, 6,574,056 bytes) -- -- λ> last (descomposicionesTriangulares3 (5*10^5)) -- (140185,148240,211575) -- (2.12 secs, 151,137,280 bytes) -- λ> last (descomposicionesTriangulares4 (5*10^5)) -- (140185,148240,211575) -- (2.30 secs, 103,280,216 bytes) |
El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Descomposiciones_triangulares.hs).
La elaboración de las soluciones se describe en el siguiente vídeo
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>
[/schedule]