Número de descomposiciones en sumas de cuatro cuadrados
Definir la función
|
1 2 |
nDescomposiciones :: Int -> Int graficaDescomposiciones :: Int -> IO () |
tales que
- (nDescomposiciones x) es el número de listas de los cuadrados de cuatro números enteros positivos cuya suma es x. Por ejemplo.
|
1 2 3 4 5 6 |
nDescomposiciones 4 == 1 nDescomposiciones 5 == 0 nDescomposiciones 7 == 4 nDescomposiciones 10 == 6 nDescomposiciones 15 == 12 nDescomposiciones 50000 == 5682 |
- (graficaDescomposiciones n) dibuja la gráfica del número de descomposiciones de los n primeros números naturales. Por ejemplo, (graficaDescomposiciones 500) dibuja
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 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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 |
import Data.Array import Graphics.Gnuplot.Simple import Test.QuickCheck -- 1ª solución -- =========== nDescomposiciones :: Int -> Int nDescomposiciones = length . descomposiciones -- (descomposiciones x) es la lista de las listas de los cuadrados de -- cuatro números enteros positivos cuya suma es x. Por ejemplo. -- λ> descomposiciones 4 -- [[1,1,1,1]] -- λ> descomposiciones 5 -- [] -- λ> descomposiciones 7 -- [[1,1,1,4],[1,1,4,1],[1,4,1,1],[4,1,1,1]] -- λ> descomposiciones 10 -- [[1,1,4,4],[1,4,1,4],[1,4,4,1],[4,1,1,4],[4,1,4,1],[4,4,1,1]] -- λ> descomposiciones 15 -- [[1,1,4,9],[1,1,9,4],[1,4,1,9],[1,4,9,1],[1,9,1,4],[1,9,4,1], -- [4,1,1,9],[4,1,9,1],[4,9,1,1],[9,1,1,4],[9,1,4,1],[9,4,1,1]] descomposiciones :: Int -> [[Int]] descomposiciones x = aux x 4 where aux 0 1 = [] aux 1 1 = [[1]] aux 2 1 = [] aux 3 1 = [] aux y 1 | esCuadrado y = [[y]] | otherwise = [] aux y n = [x^2 : zs | x <- [1..raizEntera y] , zs <- aux (y - x^2) (n-1)] -- (esCuadrado x) se verifica si x es un número al cuadrado. Por -- ejemplo, -- esCuadrado 25 == True -- esCuadrado 26 == False esCuadrado :: Int -> Bool esCuadrado x = (raizEntera x)^2 == x -- (raizEntera n) es el mayor entero cuya raíz cuadrada es menor o igual -- que n. Por ejemplo, -- raizEntera 15 == 3 -- raizEntera 16 == 4 -- raizEntera 17 == 4 raizEntera :: Int -> Int raizEntera = floor . sqrt . fromIntegral -- 2ª solución -- ============= nDescomposiciones2 :: Int -> Int nDescomposiciones2 = length . descomposiciones2 descomposiciones2 :: Int -> [[Int]] descomposiciones2 x = a ! (x,4) where a = array ((0,1),(x,4)) [((i,j), f i j) | i <- [0..x], j <- [1..4]] f 0 1 = [] f 1 1 = [[1]] f 2 1 = [] f 3 1 = [] f i 1 | esCuadrado i = [[i]] | otherwise = [] f i j = [x^2 : zs | x <- [1..raizEntera i] , zs <- a ! (i - x^2,j-1)] -- 3ª solución -- =========== nDescomposiciones3 :: Int -> Int nDescomposiciones3 x = aux x 4 where aux 0 1 = 0 aux 1 1 = 1 aux 2 1 = 0 aux 3 1 = 0 aux y 1 | esCuadrado y = 1 | otherwise = 0 aux y n = sum [aux (y - x^2) (n-1) | x <- [1..raizEntera y]] -- 4ª solución -- =========== nDescomposiciones4 :: Int -> Int nDescomposiciones4 x = a ! (x,4) where a = array ((0,1),(x,4)) [((i,j), f i j) | i <- [0..x], j <- [1..4]] f 0 1 = 0 f 1 1 = 1 f 2 1 = 0 f 3 1 = 0 f i 1 | esCuadrado i = 1 | otherwise = 0 f i j = sum [a ! (i- x^2,j-1) | x <- [1..raizEntera i]] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_nDescomposiciones :: Positive Int -> Bool prop_nDescomposiciones (Positive x) = all (== nDescomposiciones x) [f x | f <- [ nDescomposiciones2 , nDescomposiciones3 , nDescomposiciones4]] -- La comprobación es -- λ> quickCheck prop_nDescomposiciones -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- λ> nDescomposiciones 20000 -- 1068 -- (3.69 secs, 3,307,250,128 bytes) -- λ> nDescomposiciones2 20000 -- 1068 -- (0.72 secs, 678,419,328 bytes) -- λ> nDescomposiciones3 20000 -- 1068 -- (3.94 secs, 3,485,725,552 bytes) -- λ> nDescomposiciones4 20000 -- 1068 -- (0.74 secs, 716,022,456 bytes) -- -- λ> nDescomposiciones2 50000 -- 5682 -- (2.64 secs, 2,444,206,000 bytes) -- λ> nDescomposiciones4 50000 -- 5682 -- (2.77 secs, 2,582,443,448 bytes) -- Definición de graficaDescomposiciones -- ===================================== graficaDescomposiciones :: Int -> IO () graficaDescomposiciones n = plotList [ Key Nothing , PNG ("Numero_de_descomposiciones_en_sumas_de_cuadrados.png") ] (map nDescomposiciones3 [0..n]) |
Pensamiento
Ya habrá cigüeñas al sol,
mirando la tarde roja,
entre Moncayo y Urbión.Antonio Machado