Con algún nueve
Definir las funciones
|
1 2 |
numerosConNueve :: [Integer] conNueve :: Integer -> Integer |
tales que
- numerosConNueve es la lista de los números con algún dígito igual a 9. Por ejemplo,
|
1 2 |
λ> take 20 numerosConNueve [9,19,29,39,49,59,69,79,89,90,91,92,93,94,95,96,97,98,99,109] |
- (conNueve n) es la cantidad de números enteros no negativos menores o iguales que n con algún dígito igual a 9. Por ejemplo,
|
1 2 3 4 5 6 7 8 |
conNueve 1 == 0 conNueve 10 == 1 conNueve 90 == 10 length (show (conNueve (10^3))) == 3 length (show (conNueve (10^30))) == 30 length (show (conNueve (10^300))) == 300 length (show (conNueve (10^3000))) == 3000 length (show (conNueve (10^30000))) == 30000 |
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 (genericLength) import Test.QuickCheck (Property, (==>), quickCheck) numerosConNueve :: [Integer] numerosConNueve = filter tieneNueve [9..] -- (tieneNueve n) se verifica si algún dígito de n es igual a 9. Por -- ejemplo, -- tieneNueve 2919 == True -- tieneNueve 2717 == False tieneNueve :: Integer -> Bool tieneNueve n = '9' `elem` show n -- 1ª definición de conNueve -- ========================= conNueve :: Integer -> Integer conNueve n = genericLength (takeWhile (<= n) numerosConNueve) -- 2ª definición de conNueve -- ========================= conNueve2 :: Integer -> Integer conNueve2 0 = 0 conNueve2 n | tieneNueve n = 1 + conNueve2 (n-1) | otherwise = conNueve2 (n-1) -- 3ª definición de conNueve -- ========================= conNueve3 :: Integer -> Integer conNueve3 n = n + 1 - sinNueve n -- (sinNueve n) es la cantidad de números enteros no negativos menores -- o iguales que n con ningún dígito igual a 9. Por ejemplo, -- sinNueve 1 == 2 -- sinNueve 9 == 9 -- sinNueve 90 == 81 sinNueve :: Integer -> Integer sinNueve n = aux (digitos n) where aux [] = 0 aux [9] = 9 aux [x] = x+1 aux (9:xs) = 9^(1 + length xs) aux (x:xs) = x*9^(length xs) + aux xs -- (digitos n) es la lista de los dígitod de n. Por ejemplo, -- digitos 2021 == [2,0,2,1] digitos :: Integer -> [Integer] digitos n = [read [c] | c <- show n] -- 4ª definición de conNueve -- ========================= conNueve4 :: Integer -> Integer conNueve4 n = n + 1 - sinNueve2 n sinNueve2 :: Integer -> Integer sinNueve2 n = aux ds (length ds) where ds = digitos n aux [] _ = 0 aux [9] _ = 9 aux [x] _ = x+1 aux (9:xs) m = 9^m aux (x:xs) m = x*9^(m-1) + aux xs (m-1) -- Comprobacion de equivalencia -- ============================ -- La propiedad es prop_conNueve_equiv :: Integer -> Property prop_conNueve_equiv n = n >= 0 ==> all (== (conNueve n)) [conNueve2 n, conNueve3 n, conNueve4 n] -- La comprobación es -- λ> quickCheck prop_conNueve_equiv -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> conNueve (10^7) -- 5217031 -- (5.21 secs, 5,215,047,968 bytes) -- λ> conNueve2 (10^7) -- 5217031 -- (8.25 secs, 5,651,944,872 bytes) -- λ> conNueve3 (10^7) -- 5217031 -- (0.02 secs, 144,000 bytes) -- λ> conNueve4 (10^7) -- 5217031 -- (0.02 secs, 145,904 bytes) -- -- λ> length (show (conNueve3 (10^30000))) -- 30000 -- (3.24 secs, 776,076,072 bytes) -- λ> length (show (conNueve4 (10^30000))) -- 30000 -- (2.00 secs, 786,452,856 bytes) |
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>