Números construidos con los dígitos de un conjunto dado
Definir las siguientes funciones
|
1 2 |
numerosCon :: [Integer] -> [Integer] numeroDeDigitos :: [Integer] -> Integer -> Int |
tales que
- (numerosCon ds) es la lista de los números que se pueden construir con los dígitos de ds (cuyos elementos son distintos elementos del 1 al 9) . Por ejemplo,
|
1 2 3 4 5 6 |
λ> take 22 (numerosCon [1,4,6,9]) [1,4,6,9,11,14,16,19,41,44,46,49,61,64,66,69,91,94,96,99,111,114] λ> take 15 (numerosCon [4,6,9]) [4,6,9,44,46,49,64,66,69,94,96,99,444,446,449] λ> take 15 (numerosCon [6,9]) [6,9,66,69,96,99,666,669,696,699,966,969,996,999,6666] |
- (numeroDeDigitos ds k) es el número de dígitos que tiene el k-ésimo elemento (empezando a contar en 0) de la sucesión (numerosCon ds). Por ejemplo,
|
1 2 3 4 5 6 7 8 |
numeroDeDigitos [1,4,6,9] 3 == 1 numeroDeDigitos [1,4,6,9] 6 == 2 numeroDeDigitos [1,4,6,9] 22 == 3 numeroDeDigitos [4,6,9] 15 == 3 numeroDeDigitos [6,9] 15 == 4 numeroDeDigitos [1,4,6,9] (10^(10^5)) == 166097 numeroDeDigitos [4,6,9] (10^(10^5)) == 209590 numeroDeDigitos [6,9] (10^(10^5)) == 332192 |
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 |
import Data.List (genericIndex, genericLength) -- Definición de numerosCon -- ======================== numerosCon :: [Integer] -> [Integer] numerosCon xs = [n | n <- [0..] , n `tieneSusDigitosEn` xs] -- (tieneSusDigitosEn xs n) se verifica si los dígitos de n están contenidos en -- xs. Por ejemplo, -- 4149 `tieneSusDigitosEn` [1,4,6,9] == True -- 4143 `tieneSusDigitosEn` [1,4,6,9] == False tieneSusDigitosEn :: Integer -> [Integer] -> Bool tieneSusDigitosEn n xs = digitos n `esSubconjunto` xs -- (digitos n) es la lista de los dígitos de n. Por ejemplo, -- digitos 325 == [3,2,5] digitos :: Integer -> [Integer] digitos n = [read [c] | c <- show n] -- (esSubconjunto xs ys) se verifica si xs es subconjunto de ys. Por -- ejemplo, -- esSubconjunto [3,2,5] [4,2,5,7,3] == True -- esSubconjunto [3,2,5] [4,2,5,7] == False esSubconjunto :: Eq a => [a] -> [a] -> Bool esSubconjunto xs ys = all (`elem` ys) xs -- 1ª definición de numeroDeDigitos -- ================================ numeroDeDigitos :: [Integer] -> Integer -> Int numeroDeDigitos xs n = length (show (numerosCon xs `genericIndex` n)) -- 2ª definición de numeroDeDigitos -- ================================ -- Observando que si el conjunto de dígitos tiene n elementos, entonces -- hay n^k números con k dígitos. numeroDeDigitos2 :: [Integer] -> Integer -> Int numeroDeDigitos2 xs n = 1 + length (takeWhile (<= n) (sumasDePotencias (genericLength xs))) -- (potencia n) son las potencias de n. Por ejemplo, -- take 5 (potencias 3) == [3,9,27,81,243] potencias :: Integer -> [Integer] potencias k = iterate (*k) k -- (sumasDePotencias n) es la lista de las sumas acumuladas de las -- potencias de n. Por ejemplo, -- take 5 (sumasDePotencias 3) == [3,12,39,120,363] sumasDePotencias :: Integer -> [Integer] sumasDePotencias k = scanl1 (+) (potencias k) -- Comparación de eficiencia -- ========================= -- λ> numeroDeDigitos [1,4,6,9] 2000 -- 6 -- (3.98 secs, 1,424,390,064 bytes) -- λ> numeroDeDigitos2 [1,4,6,9] 2000 -- 6 -- (0.01 secs, 127,464 bytes) |