Menu Close

Densidad de números no monótonos

Un número entero positivo se dice que es

  • creciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 134479.
  • decreciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 664210.
  • no monótono si no es creciente ni decreciente; por ejemplo, 155369.

Para cada entero positivo n, la densidad números no monótonos hasta n es el cociente entre la cantidad de n números no monótonos entre menores o iguales que n y el número n. Por ejemplo, hasta 150 hay 19 números no monótonos (101, 102, 103, 104, 105, 106, 107, 108, 109, 120, 121, 130, 131, 132, 140, 141, 142, 143 y 150); por tanto, la densidad hasta 150 es 19/150 = 0.12666667

Definir las siguientes funciones

   densidad              :: Integer -> Float
   menorConDensidadMayor :: Float -> Integer

tales que

  • (densidad n) es la densidad de números no monótonos hasta n. Por ejemplo,
     densidad 100  ==  0.0
     densidad 200  ==  0.265
     densidad 400  ==  0.4375
     densidad 800  ==  0.53375
  • (menorConDensidadMayor x) es el menor número n tal que la densidad de números no monótonos hasta n es mayor o igual que x. Por ejemplo,
     menorConDensidadMayor 0.5   ==  538
     densidad 537                ==  0.49906892
     densidad 538                ==  0.5
     menorConDensidadMayor 0.9   ==  21780
     densidad 21779              ==  0.8999954
     densidad 21780              ==  0.9
     menorConDensidadMayor 0.99  ==  1586996

Soluciones

import Data.List (genericLength, sort)
 
-- 1ª definición
-- =============
 
densidad :: Integer -> Float
densidad n = 
    genericLength [x | x <- [1..n], esNoMonotono x] / fromIntegral n
 
esNoMonotono :: Integer -> Bool
esNoMonotono x = not (esCreciente x) && not (esDecreciente x)
 
esCreciente :: Integer -> Bool
esCreciente x = show x == sort (show x)
 
esDecreciente :: Integer -> Bool
esDecreciente x = reverse (show x) == sort (show x)
 
menorConDensidadMayor :: Float -> Integer 
menorConDensidadMayor x  = 
    buscaProporcion x (filter esNoMonotono [1..])
    where buscaProporcion x = 
              snd . head . filter condicion . zip [1..]
              where condicion (a,b) = a >= x * fromIntegral b
Medio

4 soluciones de “Densidad de números no monótonos

  1. Paola Cabrera Perza
    import Data.List
     
    digitos :: Integer -> [Integer]
    digitos n = [read [c] | c <- show n]
     
    creciente :: Integer -> Bool
    creciente n = sort (digitos n) == digitos n
     
    decreciente :: Integer->Bool
    decreciente n = sort (digitos n) == reverse (digitos n)
     
    noMonotonos :: [Integer]
    noMonotonos = [x | x<- [1..], not (creciente x), not (decreciente x)]
     
    densidad :: Integer -> Float
    densidad n = 
        fromIntegral (length (takeWhile (<=n) noMonotonos)) / fromIntegral n
     
    menorConDensidadMayor :: Float -> Integer
    menorConDensidadMayor x = 
        head [n | n <- [1..], densidad n >= x]
  2. erisan
    import Data.Numbers.Primes
    import Data.List
     
    densidad :: Integer -> Float
    densidad x = 
       genericLength [z | z <- [1..x], 
                          not (decreciente (show z)), 
                          not (creciente (show z))] 
       / fromIntegral x
     
    menorConDensidadMayor :: Float -> Integer
    menorConDensidadMayor x = 
        head [z | z <- [1..], densidad z >= x]                                 
     
    creciente []       = True
    creciente [x]      = True
    creciente [x,y]    = x <= y
    creciente (x:y:xs) = x <= y && creciente (y:xs)  
     
    decreciente []       = False
    decreciente [x]      = False 
    decreciente [x,y]    = x >= y
    decreciente (x:y:xs) = x >= y && decreciente (y:xs)
  3. manvermor
    densidad :: Integer -> Float
    densidad n = fromIntegral (noMon n) / (fromIntegral n)
     
    noMon :: Integer -> Integer
    noMon n = aux [1..n]
       where aux [] = 0
             aux (x:xs) | esNoMon x = 1 + aux xs
                        | otherwise = aux xs
     
    esNoMon :: Integer -> Bool
    esNoMon n = sort xs /= xs && xs /= reverse (sort xs)
       where xs = show n 
     
    menorConDensidadMayor :: Float -> Integer
    menorConDensidadMayor x = aux [100..]
       where aux (z:zs) | densidad z >= x = z
                        | otherwise = aux zs
  4. fracruzam
    densidad :: Integer -> Float
    densidad n = ((x,m) -> m/fromIntegral n) $
                 head $ dropWhile ((x,_) -> x <= n) xs
        where xs = zip ys [0..]
              ys = map read $ filter noMonotono $ map show [101..]
     
    menorConDensidadMayor :: Float -> Integer
    menorConDensidadMayor d = 
        fst $ head $ dropWhile ((_,x) -> x < d) xs
        where xs = zipWith (x n -> (n,x/fromIntegral n)) [1..] ys
              ys = map read $ filter noMonotono $ map show [101..]
     
    noMonotono :: String -> Bool
    noMonotono = noMonAux False False
        where noMonAux b1 b2 (x:xs@(y:_))
                  | x < y = b2 || noMonAux True b2 xs
                  | x > y = b1 || noMonAux b1 True xs
                  | otherwise = noMonAux b1 b2 xs
              noMonAux _ _ _ = False
       -- λ> noMonotono "123"  λ> noMonotono "321"  λ> noMonotono "312"
       -- False                False                True

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.