Descomposiciones de N como sumas de 1, 3 ó 4.
El número 5 se puede descomponer en 6 formas distintas como sumas cuyos sumandos sean 1, 3 ó 4:
|
1 2 3 4 5 6 |
5 = 1 + 1 + 1 + 1 + 1 5 = 1 + 1 + 3 5 = 1 + 3 + 1 5 = 3 + 1 + 1 5 = 1 + 4 5 = 4 + 1 |
Definir las funciones
|
1 2 |
descomposiciones :: Integer -> [[Integer]] nDescomposiciones :: Integer -> Integer |
tales que
- (descomposiciones n) es la lista de las descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
|
1 2 3 4 5 6 7 |
λ> descomposiciones1 4 [[4],[3,1],[1,3],[1,1,1,1]] λ> descomposiciones1 5 [[4,1],[1,4],[3,1,1],[1,3,1],[1,1,3],[1,1,1,1,1]] λ> descomposiciones1 6 [[3,3],[4,1,1],[1,4,1],[1,1,4],[3,1,1,1],[1,3,1,1],[1,1,3,1], [1,1,1,3],[1,1,1,1,1,1]] |
- (nDescomposiciones n) es el número de descomposiciones de n como sumas cuyos sumandos sean 1, 3 ó 4. Por ejemplo,
|
1 2 3 4 5 |
nDescomposiciones 5 == 6 nDescomposiciones 10 == 64 nDescomposiciones 20 == 7921 nDescomposiciones 30 == 974169 length (show (nDescomposiciones (10^5))) == 20899 |
Nota: Se puede usar programación dinámica.
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 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 |
import Data.List (genericLength) import Data.Array -- 1ª definición de descomposiciones (espacios de estado) -- ====================================================== descomposiciones1 :: Integer -> [[Integer]] descomposiciones1 n = busca [inicial] where busca [] = [] busca (e:es) | esFinal n e = e : busca es | otherwise = busca (es ++ sucesores n e) -- Un estado es la lista de monedas usadas hasta ahora. type Estado = [Integer] -- inicial es el estado inicial del problema; es decir, cuando no se -- ha usado ninguna moneda. inicial :: Estado inicial = [] -- (esFinal n e) es verifica si e es un estado final del problema n. Por -- ejemplo, -- esFinal (8,5,3) (4,4,0) == True -- esFinal (8,5,3) (4,0,4) == False esFinal :: Integer -> Estado -> Bool esFinal n xs = sum xs == n -- (sucesores n e) es la lista de los sucesores del estado e en el -- problema n. Por ejemplo, -- sucesores (8,5,3) (8,0,0) == [(3,5,0),(5,0,3)] -- sucesores (8,5,3) (3,5,0) == [(0,5,3),(8,0,0),(3,2,3)] sucesores :: Integer -> Estado -> [Estado] sucesores n xs = [1:xs | 1 + k <= n] ++ [3:xs | 3 + k <= n] ++ [4:xs | 4 + k <= n] where k = sum xs -- 2ª definición de descomposiciones (espacios de estado) -- ====================================================== descomposiciones2 :: Integer -> [[Integer]] descomposiciones2 n = busca [inicial2 n] where busca [] = [] busca (e:es) | esFinal2 e = snd e : busca es | otherwise = busca (es ++ sucesores2 n e) -- Un estado es una par formado por la cantidad a conseguir y la lista -- de monedas usadas hasta ahora. type Estado2 = (Integer,[Integer]) -- (inicial2 n) es el estado inicial del problema; es decir, cuando no se -- ha usado ninguna moneda. inicial2 :: Integer -> Estado2 inicial2 n = (n,[]) -- (esFinal2 e) es verifica si e es un estado final del problema. Por -- ejemplo, -- esFinal (8,5,3) (4,4,0) == True -- esFinal (8,5,3) (4,0,4) == False esFinal2 :: Estado2 -> Bool esFinal2 (k,_) = k == 0 -- (sucesores2 n e) es la lista de los sucesores del estado e en el -- problema n. Por ejemplo, -- sucesores (8,5,3) (8,0,0) == [(3,5,0),(5,0,3)] -- sucesores (8,5,3) (3,5,0) == [(0,5,3),(8,0,0),(3,2,3)] sucesores2 :: Integer -> Estado2 -> [Estado2] sucesores2 n (k,xs) = [(k-1, 1:xs) | k >= 1] ++ [(k-3, 3:xs) | k >= 3] ++ [(k-4, 4:xs) | k >= 4] -- 3ª definición de descomposiciones -- ================================= descomposiciones3 :: Integer -> [[Integer]] descomposiciones3 0 = [[]] descomposiciones3 1 = [[1]] descomposiciones3 2 = [[1,1]] descomposiciones3 3 = [[1,1,1],[3]] descomposiciones3 n = [1:xs | xs <- descomposiciones3 (n-1)] ++ [3:xs | xs <- descomposiciones3 (n-3)] ++ [4:xs | xs <- descomposiciones3 (n-4)] -- 4ª definición de descomposiciones (dinámica) -- ============================================ descomposiciones4 :: Integer -> [[Integer]] descomposiciones4 n = v!n where v = array (0,n) [(i,aux v i) | i <- [0..n]] aux v 0 = [[]] aux v 1 = [[1]] aux v 2 = [[1,1]] aux v 3 = [[1,1,1],[3]] aux v k = map (1:) (v!(k-1)) ++ map (3:) (v!(k-3)) ++ map (4:) (v!(k-4)) -- 1ª definición de nDescomposiciones -- ================================== nDescomposiciones1 :: Integer -> Integer nDescomposiciones1 = genericLength . descomposiciones1 -- 2ª definición de nDescomposiciones -- ================================== nDescomposiciones2 :: Integer -> Integer nDescomposiciones2 = genericLength . descomposiciones2 -- 3ª definición de nDescomposiciones -- ================================== nDescomposiciones3 :: Integer -> Integer nDescomposiciones3 = genericLength . descomposiciones3 -- 4ª definición de nDescomposiciones -- ================================== nDescomposiciones4 :: Integer -> Integer nDescomposiciones4 = genericLength . descomposiciones4 -- 5ª definición de nDescomposiciones (dinámica) -- ============================================= nDescomposiciones5 :: Integer -> Integer nDescomposiciones5 n = v!n where v = array (0,n) [(i,aux v i) | i <- [0..n]] aux v 0 = 1 aux v 1 = 1 aux v 2 = 1 aux v 3 = 2 aux v k = v!(k-1) + v!(k-3) + v!(k-4) -- Comparación de eficiencia -- ========================= -- λ> nDescomposiciones1 20 -- 7921 -- (3.21 secs, 3,199,383,064 bytes) -- λ> nDescomposiciones2 20 -- 7921 -- (3.17 secs, 3,176,666,880 bytes) -- λ> nDescomposiciones3 20 -- 7921 -- (0.08 secs, 17,714,152 bytes) -- -- λ> nDescomposiciones3 27 -- 229970 -- (3.73 secs, 628,730,968 bytes) -- λ> nDescomposiciones4 27 -- 229970 -- (0.45 secs, 111,518,016 bytes) -- -- λ> nDescomposiciones4 30 -- 974169 -- (2.02 secs, 454,484,992 bytes) -- λ> nDescomposiciones5 30 -- 974169 -- (0.00 secs, 0 bytes) -- λ> nDescomposiciones2 30 -- 974169 -- (2.10 secs, 441,965,208 bytes) -- λ> nDescomposiciones3 30 -- 974169 -- (0.00 secs, 0 bytes) -- -- λ> length (show (nDescomposiciones5 (10^5))) -- 20899 -- (3.00 secs, 1,050,991,880 bytes) |