Menu Close

Con mínimo común denominador

Los números racionales se pueden representar como pares de enteros:

   type Racional a = (a,a)

Definir la función

   reducida :: Integral a => [Racional a] -> [Racional a]

tal que (reducida xs) es la lista de los números racionales donde cada uno es igual al correspondiente elemento de xs y el denominador de todos los elementos de (reducida xs) es el menor número que cumple dicha condición; es decir, si xs es la lista

   [(x_1, y_1), ..., (x_n, y_n)]

entonces (reducida xs) es

   [(z_1, d), ..., (z_n, d)]

tales que

   z_1/d = x_1/y_1, ..., z_n/d = x_n/y_n

y d es el menor posible. Por ejemplo,

   reducida [(1,2),(1,3),(1,4)]  ==  [(6,12),(4,12),(3,12)]
   reducida [(1,2),(1,3),(6,4)]  ==  [(3,6),(2,6),(9,6)]
   reducida [(-7,6),(-10,-8)]    ==  [(-14,12),(15,12)]
   reducida [(8,12)]             ==  [(2,3)]

Soluciones

type Racional a = (a,a) 
 
reducida :: Integral a => [Racional a] -> [Racional a]
reducida xs = 
    [(x * (m `div` y), m) | (x,y) <- ys]
    where ys = map fraccionReducida xs
          m  = mcm [y | (_,y) <- ys]
 
-- (fraccionReducida r) es el número racional igual a r con menor
-- denominador positivo. Por ejemplo,
--    fraccionReducida ( 6, 10)  ==  ( 3,5)
--    fraccionReducida (-6, 10)  ==  (-3,5)
--    fraccionReducida ( 6,-10)  ==  (-3,5)
--    fraccionReducida (-6,-10)  ==  ( 3,5)
--    fraccionReducida ( 3,  5)  ==  ( 3,5)
fraccionReducida :: Integral a => (a,a) -> (a,a)
fraccionReducida (x,y) =
    (s * x1 `div` m, y1 `div` m)
    where s  = signum x * signum y      
          x1 = abs x
          y1 = abs y
          m  = gcd x1 y1
 
-- (mcm xs) es el mínimo común múltiplo de xs. Por ejemplo,
--    mcm [2,6,10]  ==  30
mcm :: Integral a => [a] -> a
mcm = foldl lcm 1

3 soluciones de “Con mínimo común denominador

  1. Diego
    type Racional a = (a,a)
    reducida :: Integral a => [Racional a] -> [Racional a]
    reducida xs = 
        let d  = foldr ((a,b) r -> lcm (b `div` gcd a b) r) 1 xs in
        map ((a,b) -> (a * d `div` b, d)) xs
  2. Pedro Martín Chávez
    type Racional a = (a,a)
     
    reducida :: Integral a => [Racional a] -> [Racional a]
    reducida xs = aux numeradores denominadores
        where (numeradores, denominadores) = unzip $ irreducible xs
              n = mcm denominadores
              aux [] []         = []
              aux (x:xs) (y:ys) = (x * div n y, n) : aux xs ys
     
    irreducible :: Integral a => [Racional a] -> [Racional a]
    irreducible [] = []
    irreducible ((x,y):xs) = (div x g, div y g) : irreducible xs
        where g = gcd x y
     
    mcm :: Integral a => [a] -> a
    mcm [x]      = abs x
    mcm (x:y:ys) = lcm x (mcm (y:ys))
  3. Chema Cortés
    type Racional a = (a,a)
     
    reducida :: Integral a => [Racional a] -> [Racional a]
    reducida xs = [(x*d `div` y, d)| (x,y) <- xs ]
        where d = foldr (lcm . denom) 1 xs
              denom (a,b) =  b `div` gcd a b

Escribe tu solución

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