PFH: La semana en Exercitium (del 9 al 13 de mayo de 2022)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Mínimo producto escalar
- 2. Particiones de enteros positivos
- 3. Reconocimiento de potencias de 2
- 4. Conjunto de divisores
- 5. Número de divisores
A continuación se muestran las soluciones.
1. Mínimo producto escalar
El producto escalar de los vectores [a1,a2,…,an] y [b1,b2,…, bn] es
1 |
a1 * b1 + a2 * b2 + ··· + an * bn. |
Definir la función
1 |
menorProductoEscalar :: (Ord a, Num a) => [a] -> [a] -> a |
tal que (menorProductoEscalar xs ys)
es el mínimo de los productos
escalares de las permutaciones de xs
y de las permutaciones de
ys
. Por ejemplo,
1 2 3 4 5 6 7 |
menorProductoEscalar [3,2,5] [1,4,6] == 29 menorProductoEscalar [3,2,5] [1,4,-6] == -19 menorProductoEscalar [1..10^2] [1..10^2] == 171700 menorProductoEscalar [1..10^3] [1..10^3] == 167167000 menorProductoEscalar [1..10^4] [1..10^4] == 166716670000 menorProductoEscalar [1..10^5] [1..10^5] == 166671666700000 menorProductoEscalar [1..10^6] [1..10^6] == 166667166667000000 |
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 |
module Minimo_producto_escalar where import Data.List (sort, permutations) import Test.QuickCheck (quickCheck) -- 1ª solución -- =========== menorProductoEscalar1 :: (Ord a, Num a) => [a] -> [a] -> a menorProductoEscalar1 xs ys = minimum [sum (zipWith (*) pxs pys) | pxs <- permutations xs, pys <- permutations ys] -- 2ª solución -- =========== menorProductoEscalar2 :: (Ord a, Num a) => [a] -> [a] -> a menorProductoEscalar2 xs ys = minimum [sum (zipWith (*) pxs ys) | pxs <- permutations xs] -- 3ª solución -- =========== menorProductoEscalar3 :: (Ord a, Num a) => [a] -> [a] -> a menorProductoEscalar3 xs ys = sum (zipWith (*) (sort xs) (reverse (sort ys))) -- Equivalencia -- ============ -- La propiedad es prop_menorProductoEscalar :: [Integer] -> [Integer] -> Bool prop_menorProductoEscalar xs ys = all (== menorProductoEscalar1 xs' ys') [menorProductoEscalar2 xs' ys', menorProductoEscalar3 xs' ys'] where n = min (length xs) (length ys) xs' = take n xs ys' = take n ys -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=7}) prop_menorProductoEscalar -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> menorProductoEscalar1 [0..5] [0..5] -- 20 -- (3.24 secs, 977385528 bytes) -- λ> menorProductoEscalar2 [0..5] [0..5] -- 20 -- (0.01 secs, 4185776 bytes) -- -- λ> menorProductoEscalar2 [0..9] [0..9] -- 120 -- (23.86 secs, 9342872784 bytes) -- λ> menorProductoEscalar3 [0..9] [0..9] -- 120 -- (0.01 secs, 2580824 bytes) -- -- λ> menorProductoEscalar3 [0..10^6] [0..10^6] -- 166666666666500000 -- (2.46 secs, 473,338,912 bytes) |
El código se encuentra en GitHub.
2. Particiones de enteros positivos
Una partición de un entero positivo n es una manera de escribir n como una suma de enteros positivos. Dos sumas que sólo difieren en el orden de sus sumandos se consideran la misma partición. Por ejemplo, 4 tiene cinco particiones: 4, 3+1, 2+2, 2+1+1 y 1+1+1+1.
Definir la función
1 |
particiones :: Int -> [[Int]] |
tal que (particiones n)
es la lista de las particiones del número n
. Por ejemplo,
1 2 3 |
particiones 4 == [[4],[3,1],[2,2],[2,1,1],[1,1,1,1]] particiones 5 == [[5],[4,1],[3,2],[3,1,1],[2,2,1],[2,1,1,1],[1,1,1,1,1]] length (particiones 50) == 204226 |
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 |
module Particiones_de_enteros_positivos where import Test.QuickCheck -- 1ª solución -- =========== particiones1 :: Int -> [[Int]] particiones1 0 = [[]] particiones1 n = [x:y | x <- [n,n-1..1], y <- particiones1 (n-x), [x] >= take 1 y] -- 2ª solución -- =========== particiones2 :: Int -> [[Int]] particiones2 n = aux !! n where aux = [] : map particiones [1..] particiones m = [m] : [x:p | x <- [m,m-1..1], p <- aux !! (m-x), x >= head p] -- 3ª solución -- =========== particiones3 :: Int -> [[Int]] particiones3 n = aux n n where aux 0 _ = [[]] aux n' m = concat [map (i:) (aux (n'-i) i) | i <- [n',n'-1..1], i <= m] -- 4ª solución -- =========== particiones4 :: Int -> [[Int]] particiones4 n = aux n n where aux 0 _ = [[]] aux n' m = concat [map (i:) (aux (n'-i) i) | i <- [k,k-1..1]] where k = min m n' -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_particiones :: Positive Int -> Bool prop_particiones (Positive n) = all (== particiones1 n) [ particiones2 n , particiones3 n , particiones4 n ] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=20}) prop_particiones -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- -- ========================= -- La comparación es -- λ> length (particiones1 23) -- 1255 -- (12.50 secs, 6,614,487,992 bytes) -- λ> length (particiones2 23) -- 1255 -- (0.04 secs, 3,071,104 bytes) -- λ> length (particiones3 23) -- 1255 -- (0.02 secs, 9,163,544 bytes) -- λ> length (particiones4 23) -- 1255 -- (0.01 secs, 7,149,512 bytes) -- -- λ> length (particiones2 50) -- 204226 -- (2.50 secs, 758,729,104 bytes) -- λ> length (particiones3 50) -- 204226 -- (4.26 secs, 2,359,121,096 bytes) -- λ> length (particiones4 50) -- 204226 -- (2.67 secs, 1,598,588,040 bytes) |
El código se encuentra en GitHub.
3. Reconocimiento de potencias de 2
Definir la función
1 |
esPotenciaDeDos :: Integer -> Bool |
tal que (esPotenciaDeDos n)
se verifica si n
es una potencia de dos (suponiendo que n
es mayor que 0). Por ejemplo.
1 2 3 4 5 6 7 |
esPotenciaDeDos 1 == True esPotenciaDeDos 2 == True esPotenciaDeDos 6 == False esPotenciaDeDos 8 == True esPotenciaDeDos 1024 == True esPotenciaDeDos 1026 == False esPotenciaDeDos (2^(10^8)) == True |
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 |
import Data.Bits ((.&.)) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck (Positive (Positive), quickCheck) -- 1ª solución -- =========== esPotenciaDeDos1 :: Integer -> Bool esPotenciaDeDos1 1 = True esPotenciaDeDos1 n | even n = esPotenciaDeDos1 (n `div` 2) | otherwise = False -- 2ª solución -- =========== esPotenciaDeDos2 :: Integer -> Bool esPotenciaDeDos2 n = n == head (dropWhile (<n) potenciasDeDos) -- potenciasDeDos es la lista de las potencias de dos. Por ejemplo, -- take 10 potenciasDeDos == [1,2,4,8,16,32,64,128,256,512] potenciasDeDos :: [Integer] potenciasDeDos = iterate (*2) 1 -- 3ª solución -- =========== esPotenciaDeDos3 :: Integer -> Bool esPotenciaDeDos3 x = all (==2) (primeFactors x) -- 4ª solución -- =========== -- Usando la función (.&.) de la librería Data.Bits. Dicha función -- calcula el número correspondiente a la conjunción de las -- representaciones binarias de sus argumentos. Por ejemplo, -- 6 .&. 3 == 2 -- ya que -- la representación binaria de 6 es [1,1,0] -- la representación binaria de 3 es [1,1] -- la conjunción es [1,0] -- la representación decimal de [1,0] es 2 -- -- Otros ejemplos: -- 4 .&. 3 == [1,0,0] .&. [1,1] == 0 -- 8 .&. 7 == [1,0,0,0] .&. [1,1,1] = 0 esPotenciaDeDos4 :: Integer -> Bool esPotenciaDeDos4 n = n .&. (n-1) == 0 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_esPotenciaDeDos :: Positive Integer -> Bool prop_esPotenciaDeDos (Positive n) = all (== esPotenciaDeDos1 n) [ esPotenciaDeDos2 n , esPotenciaDeDos3 n , esPotenciaDeDos4 n ] -- La comprobación es -- λ> quickCheck prop_esPotenciaDeDos -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> esPotenciaDeDos1 (2^(3*10^5)) -- True -- (3.51 secs, 5,730,072,544 bytes) -- λ> esPotenciaDeDos2 (2^(3*10^5)) -- True -- (3.12 secs, 5,755,639,952 bytes) -- λ> esPotenciaDeDos3 (2^(3*10^5)) -- True -- (2.92 secs, 5,758,872,040 bytes) -- λ> esPotenciaDeDos4 (2^(3*10^5)) -- True -- (0.03 secs, 715,152 bytes) |
El código se encuentra en GitHub.
4. Conjunto de divisores
Definir la función
1 |
divisores :: Integer -> [Integer] |
tal que (divisores x)
es el conjunto de divisores de x
. Por ejemplo,
1 2 3 |
divisores 30 == [1,2,3,5,6,10,15,30] length (divisores (product [1..10])) == 270 length (divisores (product [1..25])) == 340032 |
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 |
import Data.List (group, inits, nub, sort, subsequences) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck -- 1ª solución -- =========== divisores1 :: Integer -> [Integer] divisores1 n = [x | x <- [1..n], n `rem` x == 0] -- 2ª solución -- =========== divisores2 :: Integer -> [Integer] divisores2 n = filter ((== 0) . mod n) [1..n] -- 3ª solución -- =========== divisores3 :: Integer -> [Integer] divisores3 = nub . sort . map product . subsequences . primeFactors -- 4ª solución -- =========== divisores4 :: Integer -> [Integer] divisores4 = sort . map (product . concat) . productoCartesiano . map inits . group . primeFactors -- (productoCartesiano xss) es el producto cartesiano de los conjuntos -- xss. Por ejemplo, -- λ> productoCartesiano [[1,3],[2,5],[6,4]] -- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] productoCartesiano :: [[a]] -> [[a]] productoCartesiano [] = [[]] productoCartesiano (xs:xss) = [x:ys | x <- xs, ys <- productoCartesiano xss] -- 5ª solución -- =========== divisores5 :: Integer -> [Integer] divisores5 = sort . map (product . concat) . sequence . map inits . group . primeFactors -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_divisores :: Positive Integer -> Bool prop_divisores (Positive n) = all (== divisores1 n) [ divisores2 n , divisores3 n , divisores4 n , divisores5 n ] -- La comprobación es -- λ> quickCheck prop_divisores -- +++ OK, passed 100 tests. -- Comparación de la eficiencia -- ============================ -- λ> length (divisores (product [1..11])) -- 540 -- (12.51 secs, 7,983,499,736 bytes) -- λ> length (divisores2 (product [1..11])) -- 540 -- (4.81 secs, 4,790,146,656 bytes) -- λ> length (divisores3 (product [1..11])) -- 540 -- (0.10 secs, 107,339,848 bytes) -- λ> length (divisores4 (product [1..11])) -- 540 -- (0.02 secs, 1,702,616 bytes) -- λ> length (divisores5 (product [1..11])) -- 540 -- (0.02 secs, 1,205,824 bytes) -- -- λ> length (divisores3 (product [1..14])) -- 2592 -- (7.89 secs, 9,378,454,912 bytes) -- λ> length (divisores4 (product [1..14])) -- 2592 -- (0.03 secs, 9,426,528 bytes) -- λ> length (divisores5 (product [1..14])) -- 2592 -- (0.02 secs, 6,636,608 bytes) -- -- λ> length (divisores4 (product [1..25])) -- 340032 -- (1.65 secs, 2,055,558,208 bytes) -- λ> length (divisores5 (product [1..25])) -- 340032 -- (0.88 secs, 1,532,515,304 bytes) |
El código se encuentra en GitHub.
5. Número de divisores
Definir la función
1 |
numeroDivisores :: Integer -> Integer |
tal que (numeroDivisores x)
es el número de divisores de x
. Por ejemplo,
1 2 3 |
numeroDivisores 12 == 6 numeroDivisores 25 == 3 length (show (numeroDivisores (product [1..3*10^4]))) == 1948 |
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 |
import Data.List (genericLength, group, inits) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck -- 1ª solución -- =========== numeroDivisores1 :: Integer -> Integer numeroDivisores1 x = genericLength [y | y <- [1..x], x `mod` y == 0] -- 2ª solución -- =========== numeroDivisores2 :: Integer -> Integer numeroDivisores2 1 = 1 numeroDivisores2 x | esCuadrado x = 2 * genericLength [y | y <- [1..raizEntera x], x `mod` y == 0] - 1 | otherwise = 2 * genericLength [y | y <- [1..raizEntera x], x `mod` y == 0] -- (raizEntera x) es el mayor número entero cuyo cuadrado es menor o -- igual que x. Por ejemplo, -- raizEntera 3 == 1 -- raizEntera 4 == 2 -- raizEntera 5 == 2 -- raizEntera 8 == 2 -- raizEntera 9 == 3 raizEntera :: Integer -> Integer raizEntera x = floor (sqrt (fromInteger x)) -- (esCuadrado x) se verifica si x es un cuadrado perfecto. Por ejemplo, -- esCuadrado 9 == True -- esCuadrado 7 == False esCuadrado :: Integer -> Bool esCuadrado x = x == (raizEntera x)^2 -- 3ª solución -- =========== numeroDivisores3 :: Integer -> Integer numeroDivisores3 = genericLength . divisores -- (divisores x) es la lista de los divisores de x. Por ejemplo, -- divisores 12 == [1,3,2,6,4,12] -- divisores 25 == [1,5,25] divisores :: Integer -> [Integer] divisores = map (product . concat) . productoCartesiano . map inits . group . primeFactors -- (productoCartesiano xss) es el producto cartesiano de los conjuntos -- xss. Por ejemplo, -- λ> productoCartesiano [[1,3],[2,5],[6,4]] -- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] productoCartesiano :: [[a]] -> [[a]] productoCartesiano [] = [[]] productoCartesiano (xs:xss) = [x:ys | x <- xs, ys <- productoCartesiano xss] -- 4ª solución -- =========== numeroDivisores4 :: Integer -> Integer numeroDivisores4 = genericLength . map (product . concat) . sequence . map inits . group . primeFactors -- 5ª solución -- =========== numeroDivisores5 :: Integer -> Integer numeroDivisores5 = product . map ((+1) . genericLength) . group . primeFactors -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_numeroDivisores :: Positive Integer -> Bool prop_numeroDivisores (Positive x) = all (== numeroDivisores1 x) [ numeroDivisores2 x , numeroDivisores3 x , numeroDivisores4 x , numeroDivisores5 x] -- La comprobación es -- λ> quickCheck prop_numeroDivisores -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> numeroDivisores1 (product [1..10]) -- 270 -- (1.67 secs, 726,327,208 bytes) -- λ> numeroDivisores2 (product [1..10]) -- 270 -- (0.01 secs, 929,000 bytes) -- -- λ> numeroDivisores2 (product [1..16]) -- 5376 -- (2.10 secs, 915,864,664 bytes) -- λ> numeroDivisores3 (product [1..16]) -- 5376 -- (0.01 secs, 548,472 bytes) -- -- λ> numeroDivisores3 (product [1..30]) -- 2332800 -- (3.80 secs, 4,149,811,688 bytes) -- λ> numeroDivisores4 (product [1..30]) -- 2332800 -- (0.59 secs, 722,253,848 bytes) -- λ> numeroDivisores5 (product [1..30]) -- 2332800 -- (0.00 secs, 587,856 bytes) |
El código se encuentra en GitHub.