Definir las funciones
numerosConNueve :: [Integer]
conNueve :: Integer -> Integer |
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,
λ> take 20 numerosConNueve
[9,19,29,39,49,59,69,79,89,90,91,92,93,94,95,96,97,98,99,109] |
λ> 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,
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 |
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
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) |
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>