Menu Close

Representación decimal de números racionales

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

    6/2  = 3                  se representa por (3,[],[])
    1/2  = 0.5                se representa por (0,[5],[])
    1/3  = 0.333333...        se representa por (0,[],[3])  
   23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

   type Decimal = (Integer,[Integer],[Integer])

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

   type Racional = (Integer,Integer)

Definir las funciones

   decimal  :: Racional -> Decimal
   racional :: Decimal -> Racional

tales que

  • (decimal r) es la representación decimal del número racional r. Por ejemplo,
        decimal (1,4)    ==  (0,[2,5],[])
        decimal (1,3)    ==  (0,[],[3])
        decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])
  • (racional d) es el número racional cuya representación decimal es d. Por ejemplo,
        racional (0,[2,5],[])           ==  (1,4)
        racional (0,[],[3])             ==  (1,3)
        racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

   ghci> let (_,_,p) = decimal (23,14) in concatMap show p
   "428571"
   ghci> let (_,_,p) = decimal (1,47) in concatMap show p
   "0212765957446808510638297872340425531914893617"
   ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)
   540

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

Soluciones

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------
 
import Data.List
import Test.QuickCheck
 
-- ---------------------------------------------------------------------
-- § Tipos                                                            --
-- ---------------------------------------------------------------------
 
-- Un número racional se representa por un par de enteros, donde el
-- primer elemento es el numerador y el segundo el denominador.
type Racional = (Integer,Integer)
 
-- Un número decimal es una terna donde el primer elemento es la parte
-- entera, el segundo es el anteperíodo y el tercero es el período.
type Decimal = (Integer,[Integer],[Integer])
 
-- ---------------------------------------------------------------------
-- § De racional a decimal                                            --
-- ---------------------------------------------------------------------
 
-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,
--    mayorExponente 2 40  ==  3
--    mayorExponente 5 40  ==  1
--    mayorExponente 5 41  ==  0
mayorExponente :: Integer -> Integer -> Integer
mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1
 
-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudAnteperiodo 2   ==  1
--    longitudAnteperiodo 3   ==  0
--    longitudAnteperiodo 14  ==  1
longitudAnteperiodo :: Integer -> Integer
longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)
 
-- (longitudPeriodo n) es la longitud del período de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudPeriodo 2  ==  0
--    longitudPeriodo 3  ==  1
--    longitudPeriodo 7  ==  6
longitudPeriodo :: Integer -> Integer
longitudPeriodo n
    | m == 1    = 0 
    | otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]
    where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))
 
-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo, 
--    take 10 (expansionDec (1,4))    ==  [0,2,5]
--    take 10 (expansionDec (1,7))    ==  [0,1,4,2,8,5,7,1,4,2]
--    take 12 (expansionDec (90,7))   ==  [12,8,5,7,1,4,2,8,5,7,1,4]
--    take 12 (expansionDec (23,14))  ==  [1,6,4,2,8,5,7,1,4,2,8,5]
expansionDec :: Racional -> [Integer]
expansionDec (x,y) 
    | r == 0    = [q] 
    | otherwise = q : expansionDec (r*10,y)
    where (q,r) = quotRem x y
 
-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,
--    parteEntera (125,3)  ==  41
parteEntera :: Racional -> Integer
parteEntera (a,b) = a `div` b
 
-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de
-- cifras que se encuentran entre la parte entera y el primer período de
-- a/b. Por ejemplo,
--    antePeriodo (23,14)  ==  [6]
--    antePeriodo (1,5)    ==  [2]
antePeriodo :: Racional -> [Integer]
antePeriodo (a,b) = genericTake s (tail xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b
 
-- (periodo (a,b)) es el período de a/b; es decir, la lista de cifras que
-- se encuentran entre la parte entera y el primer período de a/b. Por
-- ejemplo, 
--    periodo (1,3)                   ==  [3]
--    periodo (1,5)                   ==  []
--    periodo (1,7)                   ==  [1,4,2,8,5,7]
--    periodo (23,14)                 ==  [4,2,8,5,7,1]
--    concatMap show $ periodo (1,29) == "0344827586206896551724137931"
periodo :: Racional -> [Integer]
periodo (a,b) = genericTake t (genericDrop (1+s) xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b
          t  = longitudPeriodo b
 
-- (reducido (a,b)) es la forma reducida del número racional a/b. Por
-- ejemplo, 
--    reducido (40,80)  ==  (1,2)
reducido :: Racional -> Racional
reducido (a,b) = (a `div` m, b `div` m) 
    where m = gcd a b
 
-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna
-- formada por la parte entera, la parte decimal pura y la parte decimal
-- periódica. Por ejemplo, 
--    decimal (1,4)    ==  (0,[2,5],[])
--    decimal (1,3)    ==  (0,[],[3])
--    decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])
decimal :: Racional -> Decimal
decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)
    where r = reducido (a,b)
 
-- ---------------------------------------------------------------------
-- § De decimal a racional                                            --
-- ---------------------------------------------------------------------
 
-- (digitosAnumero xs) es el número correspondiente a la lista de
-- dígitos xs. Por ejemplo,
--    digitosAnumero [3,2,5]  ==  325
digitosAnumero :: [Integer] -> Integer
digitosAnumero = foldl (\a y -> 10*a+y) 0
 
-- 2ª definición de digitosAnumero (por comprensión)
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]
    where n = length xs
 
-- (racional (x,ys,zs)) es el número racional cuya representación
-- decimal es (x,ys,zs). Por ejemplo,
--    racional (0,[2,5],[])           ==  (1,4)
--    racional (0,[],[3])             ==  (1,3)
--    racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)
racional :: Decimal -> Racional
racional (x,ys,[]) = reducido (a,b) where
    a = digitosAnumero (x:ys)
    b = 10^(length ys)
racional (x,ys,zs) = reducido (a,b) where 
    a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)
    b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)
 
-- ---------------------------------------------------------------------
-- § Propiedades                                                      --
-- ---------------------------------------------------------------------
 
-- La 1ª propiedad es
prop_RacionalDecimal :: Racional -> Property
prop_RacionalDecimal (a,b) =
    a >= 0 && b > 0  ==>
    racional (decimal (a,b)) == reducido (a,b)
 
-- La comprobación es 
--    ghci> quickCheck prop_RacionalDecimal
--    +++ OK, passed 100 tests.
 
-- En lugar de reducido se puede usar un generador de números racionales
numeroRacional :: Gen Racional
numeroRacional = do a <- arbitrary
                    b <- arbitrary
                    return (reducido (abs a, 1+ abs b))
 
-- La propiedad es
prop_RacionalDecimal2 :: Property
prop_RacionalDecimal2 =
    forAll numeroRacional
           (\(a,b) -> racional (decimal (a,b)) == (a,b))
 
-- La comprobación es
--   ghci> quickCheck prop_RacionalDecimal2
--   +++ OK, passed 100 tests.
 
-- Para la 2ª propiedad se define un generador de números decimales
numeroDecimal :: Gen Decimal
numeroDecimal = do a <- arbitrary
                   b <- arbitrary
                   return (decimal (abs a, 1+ abs b))
 
-- La 2ª propiedad es
prop_DecimalRacional :: Property
prop_DecimalRacional =
    forAll numeroDecimal 
           (\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))
 
-- La comprobación es
--   ghci> quickCheck prop_DecimalRacional
--   +++ OK, passed 100 tests.

3 soluciones de “Representación decimal de números racionales

  1. Chema Cortés
    import Test.QuickCheck
     
    type Decimal = (Integer,[Integer],[Integer])
    type Racional = (Integer,Integer)
     
    decimal  :: Racional -> Decimal
    decimal r | null ds     = (0, [], [])
              | otherwise   = (fst (head ds), as', ps')
        where
            ds = digitos r
            (as, ps) = partePuraPeriodica (tail ds)
            as' = map fst as
            ps' = map fst ps
     
    digitos :: Racional -> [Racional]
    digitos (n,d) | n == 0    = []
                  | r == 0    = [(e,0)]
                  | otherwise = (e,r) : digitos (10*r, d)
        where (e,r) = n `divMod` d
     
    partePuraPeriodica :: Eq a => [a] -> ([a],[a])
    partePuraPeriodica = aux []
        where
            aux as []  = (reverse as, [])
            aux as (b:bs) | b `elem` as = span (/=b) (reverse as)
                          | otherwise = aux (b:as) bs
     
    racional :: Decimal -> Racional
    racional (e, as, ps) | null ps   = reduce (x, 10^a)
                         | otherwise = reduce (y-x, 10^b-10^a)
        where
            a = length as
            x = read (concatMap show (e:as))
            b = length as + length ps
            y = read (concatMap show (e:as ++ ps))
     
    reduce :: Racional -> Racional
    reduce (n,d) = (n `div` g, d `div` g)
        where g = gcd n d
     
    prop_inversa :: (Positive Integer, Positive Integer) -> Bool
    prop_inversa (n,d) = (racional . decimal) r == r
        where r = reduce (getPositive n, getPositive d)
  2. juamorrom1
    import Test.QuickCheck
    import Data.List
    import Data.Char
     
    type Decimal = (Integer,[Integer],[Integer])
     
    type Racional = (Integer,Integer)
     
    -- * La función "decimal" es:
     
    decimal  :: Racional -> Decimal
    decimal (_,0) = error "El denominador no puede ser cero"
    decimal (0,_) = (0,[],[])
    decimal (a,b) | parteEnteraPequeña ds2 =
                    (0,(replicate ((digitToInt (last ds2))-1) 0) ++
                    (stringAlista (buscarAnteperiodo (init ds') [])),
                    stringAlista (quitarLista (buscarPeriodo (init ds'))))
                  | parteEnteraGrande ds2 = (e*10^((digitToInt (last ds2))-1),xs,ys)
                  | a < 0 = algunNegativo (decimal (-a,b))
                  | b < 0 = algunNegativo (decimal (a,-b))
                  | otherwise = (e,xs,ys)
               where e  = (fromIntegral (parteEntera ds1)) 
                     xs = stringAlista (buscarAnteperiodo ds2 [])
                     ys = quitaRepetidosSolos (stringAlista
                          (quitarLista(buscarPeriodo ds2)))
                     ds = digitos ((fromIntegral a)/(fromIntegral b))
                     ds' = filter (isDigit) ((fst ds) ++ (snd ds))
                     ds1 = fst ds
                     ds2 = snd ds
     
    -- * Las funciones auxiliares utilizadas son:
     
    -- (digitos n) devuelve el par (a,b), donde a es la parte entera del número racional n
    -- y b es la parte decimal de n (a y b son cadenas).
    digitos :: Show a => a -> ([Char], [Char])
    digitos n = aux (show n) []
           where aux [] ys = (ys,[])
                 aux (x:xs) ys | x == '.'  = (ys,xs)
                               | otherwise = aux xs (ys ++ [x])
     
    -- (stringAlista xs) tranforma la lista de caracteres xs en una lista de números.
    stringAlista :: Num t => [Char] -> [t]
    stringAlista xs = [ fromIntegral (digitToInt x) | x <- xs ]
     
    -- (buscarPeriodo' xs) devuelve la lista con las cadenas que se repiten en xs.
    buscarPeriodo' :: [Char] -> [[Char]]
    buscarPeriodo' xs =  [ x | x <- inits xs, y <- inits xs, x ++ x == y, x /= "",
                         length x >= 2 ]
     
    -- (buscarPeriodo xs) va analizando los decimales del número racional hasta que
    -- encuentra alguna cadena que se repita; esto se hace por si tuviera anteperíodo.
    buscarPeriodo :: [Char] -> [[Char]]
    buscarPeriodo [] =  []
    buscarPeriodo (x:xs) | buscarPeriodo' (x:xs) == [] = buscarPeriodo xs
                         | otherwise = buscarPeriodo' (x:xs)
     
    -- (buscarAnteperiodo xs) devuelve el anteperiodo de la cadena xs.
    buscarAnteperiodo :: [Char] -> [Char] -> [Char]
    buscarAnteperiodo [] ys = ys
    buscarAnteperiodo (x:xs) ys | buscarPeriodo' (x:xs) == [] =
                                    buscarAnteperiodo xs (ys ++ [x])
                                | otherwise = ys
     
    -- (quitarLista xss) la uso para la función (buscarPeriodo xs), de la cual quiero solo
    -- el primer elemento, aunque si se tratara de una lista vacía querría una lista vacía,
    -- por lo que no puedo usar "head" sólo, de ahí a que tenga que crearla.
    quitarLista :: [[t]] -> [t]
    quitarLista xss | length xss >= 1 = head xss
                    | otherwise       = []
     
    -- (parteEntera xs) transforma la cadena xs en un número entero.
    parteEntera :: [Char] -> Int
    parteEntera (x:[]) = digitToInt x
    parteEntera (x:xs) = (10 ^ ((length (x:xs))-1)) * (digitToInt x) + parteEntera xs
     
    -- (parteEnteraPequeña xs) se verifica si el número racional que estamos trabajando
    -- es muy pequeño, tanto que Haskell nos lo devuelve con notación científica.
    parteEnteraPequeña :: [Char] -> Bool
    parteEnteraPequeña ys = isInfixOf "e-" ys
     
    -- (parteEnteraGrande xs) se verifica si el número racional que estamos trabajando
    -- es muy grande, tanto que Haskell nos lo devuelve con notación científica.
    parteEnteraGrande :: Foldable t => t Char -> Bool
    parteEnteraGrande ys = notElem '-' ys && elem 'e' ys
     
    -- (quitaRepetidoSolos xs) devuelve [x] si todos los elementos de xs son x; se usa por
    -- si, por ejemplo, tenemos un período [3,3,3], y solo queremos [3] (no se puede usar
    -- (nub xs) por si el período fuera, por ejemplo, [3,3,4] ).
    quitaRepetidosSolos :: Eq t => [t] -> [t]
    quitaRepetidosSolos [] = []
    quitaRepetidosSolos (x:xs) | all (== x) xs = [x]
                               | otherwise     = (x:xs)
     
    -- (algunNegativo d) devuelve la representación decimal d, pero con parte entera negativa.
    algunNegativo :: Num t => (t, t1, t2) -> (t, t1, t2)
    algunNegativo (e,xs,ys) = (-e,xs,ys)
     
     
     
    -- * Por otro lado, la función "racional" es:
     
    racional :: Decimal -> Racional
    racional d@(e,xs,ys) | e < 0 = head [ (-a,b) | a <- [1..], b <- [1..a],
                           decimal (-a,b) == d ]
                         | e > 0 = head [ (a,b) | a <- [1..], b <- [1..a],
                           decimal (a,b) == d ]
                         | otherwise = head [ (a,b) | b <- [1..], a <- [1..b],
                           decimal (a,b) == d ]
     
    -- * La propiedad es
     
    prop_inversa :: Integer -> Integer -> Property
    prop_inversa a b = a > 0 && b > 0 ==> racional (decimal (a,b)) == reduce (a,b)
     
    reduce :: Racional -> Racional
    reduce (n,d) = (n `div` g, d `div` g)
        where g = gcd n d
     
    -- La comprobación es
    -- *Main> quickCheck prop_inversa
    -- +++ OK, passed 100 tests.
     
    -- NOTAS:
    --  * No he conseguido verificar los dos últimos ejemplos sobre calcular los
    --    períodos de los números racionales (mi función tiene en cuenta
    --    solo los 17 primeros dígitos de los números racionales).
    --  * A la hora de comprobar con QuickCheck si la propiedad se cumple, evito los 
    --    negativos debido al caso en el que la parte entera del racional es 0, ya que
    --    no puedo diferenciar si es positiva o negativa (para Haskell: 0 == -0). Es decir:
    --    *Main> decimal (1,3)
    --    (0,[],[3])
    --    *Main> decimal (-1,3)
    --    (0,[],[3])
  3. abrdelrod
    import Data.Numbers.Primes
     
    type Decimal = (Integer,[Integer],[Integer])
    type Racional = (Integer,Integer)
     
    -- Funciones auxiliares:
    lista2Int :: [Integer] -> Integer
    lista2Int = read.concatMap show
     
    digitos :: Integer -> [Integer]
    digitos x = [read [c]| c <- show x]
     
    decimales :: Integer -> Integer -> [[Integer]]
    decimales x y = tail (aux x)
       where aux m = [a,z] : aux (10*z)
                     where z = m-y*a
                           a = div m y
     
    seccion :: Eq a => [a] -> [a]
    seccion xs = aux xs []
        where aux [] ys = reverse ys
              aux (x:xs) ys | x `elem` ys = reverse ys
                            | otherwise   = aux xs (x:ys)
     
    -- Las funciones pedidas:
    decimal  :: Racional -> Decimal
    decimal (x,y) | all (`elem`[2,5]) (primeFactors y) = (div x y, map head $ fst d, [])
                  | otherwise = (div x y, map head $ fst d, map head $ snd d)
                                   where xs = seccion ys
                                         ys = decimales x y
                                         d  =  span (/= ys!!n) xs
                                         n  = length xs
     
    racional :: Decimal -> Racional
    racional (x,ys,[]) = (div b a, div c a)
       where b = lista2Int (digitos x ++ ys)
             c = 10^(length ys)
             a = gcd c b
    racional (x,[],zs) = (div c a, div d a)
         where c = lista2Int (digitos x ++ zs) - x
               d = 10^(length zs) - 1
               a = gcd c d
    racional (x,ys,zs) = (div d a, div e a)
        where d = lista2Int (digitos x ++ ys ++ zs) - lista2Int (digitos x ++ ys)
              e = lista2Int (replicate (length zs) 9 ++ replicate (length ys) 0)
              a = gcd d e
     
    -- Y la comprobación (usando la propiedad definida por Chema Cortés):
     
    --*Main> quickCheck prop_inversa
    -- +++ OK, passed 100 tests.

Leave a Reply to Chema Cortés Cancel reply

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