Menu Close

Con mínimo común denominador

José A. Alonso,

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
Medio
, , , , , , , ,

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

  1. Responder
    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. Responder
    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. Responder
    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.