Menu Close

Representación decimal de números racionales

José A. Alonso,

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.
Avanzado
, , , , , , , , , , , , , , , , , ,

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

  1. Responder
    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. Responder
    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. Responder
    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 juamorrom1 Cancel reply

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