Medio

Números cubifinitos

PorJosé A. Alonso 15-marzo-201721-enero-2020

El enunciado del problema Números cubifinitos de ¡Acepta el reto! es el siguiente

Se dice que un número es cubifinito cuando al elevar todos sus dígitos al cubo y sumarlos el resultado o bien es 1 o bien es un número cubifinito.

Por ejemplo, el número 1243 es cubifinito, pues al elevar todos sus dígitos al cubo obtenemos 100 que es cubifinito.

Por su parte, el 513 no es cubifinito, pues al elevar al cubo sus dígitos conseguimos el 153 que nunca podrá ser cubifinito, pues la suma de los cubos de sus dígitos vuelve a dar 153.

Definir las funciones

   esCubifinito :: Int -> Bool
   grafica :: Int -> IO ()

1 2	esCubifinito :: Int -> Bool grafica :: Int -> IO ()

tales que

(esCubifinito n) se verifica si n es un número cubifinito. Por ejemplo,

     esCubifinito 1      ==  True
     esCubifinito 10     ==  True
     esCubifinito 1243   ==  True
     esCubifinito 87418  ==  True
     esCubifinito 513    ==  False

esCubifinito 1 == True

esCubifinito 10 == True

esCubifinito 1243 == True

esCubifinito 87418 == True

esCubifinito 513 == False

(grafica n) dibuja la gráfica de la sucesión de los primeros n números cubifinitos. Por ejemplo, al evaluar (grafica 50) se dibuja

Soluciones

import Graphics.Gnuplot.Simple

-- 1ª solución
-- ===========

esCubifinito :: Int -> Bool
esCubifinito n = aux [n]
  where aux (n:ns) | n == 1      = True
                   | n `elem` ns = False
                   | otherwise   = aux (sumaCubosDigitos n : n : ns)

-- (sumaCubosDigitos b) es la suma de los cubos de los dígitos de n. Por
-- ejemplo, 
--    sumaCubosDigitos 513  ==  153
sumaCubosDigitos :: Int -> Int
sumaCubosDigitos = sum . map (^3) . digitos

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 513  ==  [5,1,3]
digitos :: Int -> [Int]
digitos n = [read [c] | c <- show n]

-- 2ª solución
-- ===========

esCubifinito2 :: Int -> Bool
esCubifinito2 n = primerRepetido (orbita n) == 1

-- (orbita n) es la lista cuyo primer elemento es n y los siguientes se
-- obtienen sumando los cubos de los digitos del elemento anterior. Por
-- ejemplo,  
--    take 9 (orbita 2)  ==  [2,8,512,134,92,737,713,371,371]
orbita :: Int -> [Int]
orbita n = iterate sumaCubosDigitos n

-- (primerRepetido xs) es el primer elemento repetido de la lista
--  xs. Por ejemplo, 
--    primerRepetido [3,7,5,7,2]  ==  7
primerRepetido :: Eq a => [a] -> a
primerRepetido xs = aux xs []
  where
    aux (x:xs') ys | x `elem` ys = x
                   | otherwise   = aux xs' (x:ys) 

grafica :: Int -> IO ()
grafica n = 
    plotList [Key Nothing, PNG "Numeros_cubifinitos.png"]
             (zip [1..n] [x | x <- [1..], esCubifinito x])

import Graphics.Gnuplot.Simple

-- 1ª solución

-- ===========

esCubifinito :: Int -> Bool

esCubifinito n = aux [n]

where aux (n:ns) | n == 1 = True

| n `elem` ns = False

| otherwise = aux (sumaCubosDigitos n : n : ns)

-- (sumaCubosDigitos b) es la suma de los cubos de los dígitos de n. Por

-- ejemplo,

-- sumaCubosDigitos 513 == 153

sumaCubosDigitos :: Int -> Int

sumaCubosDigitos = sum . map (^3) . digitos

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 513 == [5,1,3]

digitos :: Int -> [Int]

digitos n = [read [c] | c <- show n]

-- 2ª solución

-- ===========

esCubifinito2 :: Int -> Bool

esCubifinito2 n = primerRepetido (orbita n) == 1

-- (orbita n) es la lista cuyo primer elemento es n y los siguientes se

-- obtienen sumando los cubos de los digitos del elemento anterior. Por

-- ejemplo,

-- take 9 (orbita 2) == [2,8,512,134,92,737,713,371,371]

orbita :: Int -> [Int]

orbita n = iterate sumaCubosDigitos n

-- (primerRepetido xs) es el primer elemento repetido de la lista

-- xs. Por ejemplo,

-- primerRepetido [3,7,5,7,2] == 7

primerRepetido :: Eq a => [a] -> a

primerRepetido xs = aux xs []

where

aux (x:xs') ys | x `elem` ys = x

| otherwise = aux xs' (x:ys)

grafica :: Int -> IO ()

grafica n =

plotList [Key Nothing, PNG "Numeros_cubifinitos.png"]

(zip [1..n] [x | x <- [1..], esCubifinito x])

Números de Catalan

PorJosé A. Alonso 13-marzo-201726-marzo-2022

Los números de Catalan forman la sucesión cuyo término general es

Los primeros números de Catalan son

   1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786

1	1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786

Los números de Catalan satisfacen la siguiente relación de recurrencia:

Asintóticamente, los números de Catalan crecen como:

considerando que el cociente entre el n-ésimo número de Catalan y la expresión de la derecha tiende hacia 1 cuando n tiende a infinito.

Definir las funciones

   catalan :: [Integer]
   grafica :: Int -> Int -> IO ()

1 2	catalan :: [Integer] grafica :: Int -> Int -> IO ()

tales que

catalan es la lista de términos de la sucesión de Catalan. Por ejemplo,

     λ> take 12 catalan
     [1,1,2,5,14,42,132,429,1430,4862,16796,58786]
     λ> length (show (catalan !! 50000))
     30096

λ> take 12 catalan

[1,1,2,5,14,42,132,429,1430,4862,16796,58786]

λ> length (show (catalan !! 50000))

30096

(grafica a b) dibuja los n-ésimos términos de la sucesión de Catalan, para n entre a y b, junto con los de la expresión de la derecha de

Por ejemplo, (grafica 5 10) dibuja

y (grafica 55 60) dibuja

Soluciones

import Graphics.Gnuplot.Simple

catalan :: [Integer]
catalan = scanl (\c n -> c*2*(2*n-1) `div` (n+1)) 1 [1..]

grafica :: Int -> Int -> IO ()
grafica a b = 
  plotLists [Key Nothing]
            [[(fromIntegral n, fromIntegral (catalan !! n)) | n <- [a..b]]
            ,[(n,4**n/(n**(3/2)*(sqrt pi))) | n <- [c..d]]]
  where c, d :: Double
        c = fromIntegral a
        d = fromIntegral b

import Graphics.Gnuplot.Simple

catalan :: [Integer]

catalan = scanl (\c n -> c*2*(2*n-1) `div` (n+1)) 1 [1..]

grafica :: Int -> Int -> IO ()

grafica a b =

plotLists [Key Nothing]

[[(fromIntegral n, fromIntegral (catalan !! n)) | n <- [a..b]]

,[(n,4**n/(n**(3/2)*(sqrt pi))) | n <- [c..d]]]

where c, d :: Double

c = fromIntegral a

d = fromIntegral b

La codificación de Luka

PorJosé A. Alonso 7-marzo-201714-marzo-2017

En el problema Kemija se utiliza la codificación de Luka consistente en añadir detrás de cada vocal la letra ‘p’ seguida de la vocal. Por ejemplo, la palabra «elena» se codifica como «epelepenapa» y «luisa» por «lupuipisapa».

Definir las funciones

   codifica   :: String -> String
   decodifica :: String -> String

1 2	codifica :: String -> String decodifica :: String -> String

tales que
+ (codifica cs) es la codificación de Luka de la cadena cs. Por ejemplo,

     λ> codifica "elena admira a luisa"
     "epelepenapa apadmipirapa apa lupuipisapa"
     λ> codifica "todo para nada"
     "topodopo paparapa napadapa"

λ> codifica "elena admira a luisa"

"epelepenapa apadmipirapa apa lupuipisapa"

λ> codifica "todo para nada"

"topodopo paparapa napadapa"

(decodifica cs) es la decodificación de Luka de la cadena cs. Por ejemplo,

     λ> decodifica "epelepenapa apadmipirapa apa lupuipisapa"
     "elena admira a luisa"
     λ> decodifica "topodopo paparapa napadapa"
     "todo para nada"

λ> decodifica "epelepenapa apadmipirapa apa lupuipisapa"

"elena admira a luisa"

λ> decodifica "topodopo paparapa napadapa"

"todo para nada"

Soluciones

codifica :: String -> String
codifica "" = ""
codifica (c:cs) | esVocal c = c : 'p' : c : codifica cs
                | otherwise = c : codifica cs

esVocal :: Char -> Bool
esVocal c = c `elem` "aeiou"

decodifica :: String -> String
decodifica "" = ""
decodifica (c:cs) | esVocal c = c : decodifica (drop 2 cs)
                  | otherwise = c : decodifica cs

codifica :: String -> String

codifica "" = ""

codifica (c:cs) | esVocal c = c : 'p' : c : codifica cs

| otherwise = c : codifica cs

esVocal :: Char -> Bool

esVocal c = c `elem` "aeiou"

decodifica :: String -> String

decodifica "" = ""

decodifica (c:cs) | esVocal c = c : decodifica (drop 2 cs)

| otherwise = c : decodifica cs

Números binarios invertidos

PorJosé A. Alonso 6-marzo-201713-marzo-2017

La representación binaria de 13 es 1101, que al invertirlo da 1011 cuya representación decimal es el número 11.

Definir la función

   transformado :: Integer -> Integer

1	transformado :: Integer -> Integer

tal que (transformado x) es la representación decimal del número obtenido invirtiendo la representación binaria de x. Por ejemplo,

   transformado 13  ==  11
   transformado 47  ==  61

1 2	transformado 13 == 11 transformado 47 == 61

Nota: El ejercicio está basado en el problema Reversed Binary Numbers de Kattis.

Soluciones

transformado :: Integer -> Integer 
transformado = bin2int . reverse . int2bin

-- (int2bin x) es la representación binaria de x. Por ejemplo,
--    int2bin 13  ==  [1,0,1,1]
int2bin :: Integer -> [Integer]
int2bin n | n < 2     = [n]
          | otherwise = n `mod` 2 : int2bin (n `div` 2)

-- (bin2int x) es la representación decimal del número binario x. Por
-- ejemplo, 
--    bin2int [1,0,1,1]           ==  13
--    bin2int (reverse [1,0,1,1]) ==  11
bin2int :: [Integer] -> Integer
bin2int =  foldr (\x y -> x + 2*y) 0

transformado :: Integer -> Integer

transformado = bin2int . reverse . int2bin

-- (int2bin x) es la representación binaria de x. Por ejemplo,

-- int2bin 13 == [1,0,1,1]

int2bin :: Integer -> [Integer]

int2bin n | n < 2 = [n]

| otherwise = n `mod` 2 : int2bin (n `div` 2)

-- (bin2int x) es la representación decimal del número binario x. Por

-- ejemplo,

-- bin2int [1,0,1,1] == 13

-- bin2int (reverse [1,0,1,1]) == 11

bin2int :: [Integer] -> Integer

bin2int = foldr (\x y -> x + 2*y) 0

Contando en la arena

PorJosé A. Alonso 2-marzo-20179-marzo-2017

El problema de ayer de ¡Acepta el reto! fue Contando en la arena cuyo enunciado es el siguiente:

Es ampliamente conocido que escribimos los números utilizando base 10, en la que expresamos las cantidades utilizando 10 dígitos distintos (0…9). El valor de cada uno de ellos depende de la posición que ocupe dentro del número, pues cada dígito se multiplica por una potencia de 10 distinta según cuál sea esa posición.

La descomposición, por ejemplo, del número 1.234 es: 1.234 = 1×10^3 + 2×10^2 + 3×10^1 + 4×10^0

Otra base muy conocida es la base 2 al ser la utilizada por los dispositivos electrónicos. En ella sólo hay dos dígitos distintos (0 y 1), que se ven multiplicados por potencias de 2.

Mucho antes de que llegaran la base 2, la base 10 e incluso los números romanos, los primeros seres humanos contaban haciendo surcos en la arena, muescas en un trozo de madera o colocando palos en línea. Estaban, sin saberlo, usando base 1. En ella sólo hay un símbolo y cada dígito es multiplicado por una potencia de 1. Dado que 1^n = 1 el resultado es que todos los dígitos tienen el mismo peso.

Definir la función

   transformaAbase1 :: FilePath -> FilePath -> IO ()

1	transformaAbase1 :: FilePath -> FilePath -> IO ()

tal que al evaluar (transformaAbase1 f1 f2) lee el contenido del fichero f1 (que estará compuesto por distintos números mayores que 0, cada uno en una línea) y escribe en el fichero f2 una línea con la representación en base 1 de cada uno de los números de f1 excepto el 0 final. Por ejemplo, si el contenido de «Entrada.txt» es

al evaluar (transformaAbase1 «Entrada.txt» «Salida.txt») el contenido de «Salida.txt» debe de ser

1
1111
111111

1111

111111

Soluciones

transformaAbase1 :: FilePath -> FilePath -> IO ()
transformaAbase1 f1 f2 = do
  cs <- readFile f1
  writeFile f2 (transformaAbase1Aux cs)

-- (transformaAbase1Aux cs) es la cadena obtenida transformando a base 1
-- cada uno de los números de cs. Por ejemplo,
--    λ> transformaAbase1Aux "1\n4\n6\n0\n" 
--    "1\n1111\n111111\n"
transformaAbase1Aux :: String -> String
transformaAbase1Aux cs =
  unlines (map (show . enBase1) (numeros cs))

-- (numeros cs) es la lista de los números de cs, excepto el último. Por
-- ejemplo, 
--    numeros "1\n4\n6\n0\n"  ==  [1,4,6]
numeros :: String -> [Integer]
numeros cs  =
  init (map read (lines cs))

-- (enBsase1 x) es la representación de x en base 1. Por ejemplo,
--    enBase1 4  ==  1111
enBase1 :: Integer -> Integer
enBase1 x = (10^x - 1) `div` 9

transformaAbase1 :: FilePath -> FilePath -> IO ()

transformaAbase1 f1 f2 = do

cs <- readFile f1

writeFile f2 (transformaAbase1Aux cs)

-- (transformaAbase1Aux cs) es la cadena obtenida transformando a base 1

-- cada uno de los números de cs. Por ejemplo,

-- λ> transformaAbase1Aux "1\n4\n6\n0\n"

-- "1\n1111\n111111\n"

transformaAbase1Aux :: String -> String

transformaAbase1Aux cs =

unlines (map (show . enBase1) (numeros cs))

-- (numeros cs) es la lista de los números de cs, excepto el último. Por

-- ejemplo,

-- numeros "1\n4\n6\n0\n" == [1,4,6]

numeros :: String -> [Integer]

numeros cs =

init (map read (lines cs))

-- (enBsase1 x) es la representación de x en base 1. Por ejemplo,

-- enBase1 4 == 1111

enBase1 :: Integer -> Integer

enBase1 x = (10^x - 1) `div` 9

Números cubifinitos

Soluciones

Números de Catalan

Soluciones

La codificación de Luka

Soluciones

Números binarios invertidos

Soluciones

Contando en la arena

Soluciones

Entradas recientes

Buscar

Correo electrónico