Menu Close

Operaciones con polinomios como diccionarios

José A. Alonso,

Los polinomios se pueden representar mediante diccionarios con los exponentes como claves y los coeficientes como valores.

El tipo de los polinomios con coeficientes de tipo a se define por

   type Polinomio a = M.Map Int a

Dos ejemplos de polinomios (que usaremos en los ejemplos) son

   3 + 7x - 5x^3
   4 + 5x^3 + x^5

se definen por

  ejPol1, ejPol2 :: Polinomio Int
  ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
  ejPol2 = M.fromList [(0,4),(3,5),(5,1)]

Definir las funciones

   sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
   multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
   multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a

tales que

  • (sumaPol p q) es la suma de los polinomios p y q. Por ejemplo,
     ghci> sumaPol ejPol1 ejPol2
     fromList [(0,7),(1,7),(5,1)]
     ghci> sumaPol ejPol1 ejPol1
     fromList [(0,6),(1,14),(3,-10)]
  • (multPorTerm (n,a) p) es el producto del término ax^n por p. Por ejemplo, 
     ghci> multPorTerm (2,3) (M.fromList [(0,4),(2,1)])
     fromList [(2,12),(4,3)]
  • (multPol p q) es el producto de los polinomios p y q. Por ejemplo, 
     ghci> multPol ejPol1 ejPol2
     fromList [(0,12),(1,28),(3,-5),(4,35),(5,3),(6,-18),(8,-5)]
     ghci> multPol ejPol1 ejPol1
     fromList [(0,9),(1,42),(2,49),(3,-30),(4,-70),(6,25)]
     ghci> multPol ejPol2 ejPol2
     fromList [(0,16),(3,40),(5,8),(6,25),(8,10),(10,1)]

Soluciones

import qualified Data.Map as M
 
type Polinomio a = M.Map Int a 
 
ejPol1, ejPol2 :: Polinomio Int
ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
ejPol2 = M.fromList [(0,4),(3,5),(5,1)]
 
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q = 
    M.filter (/=0) (M.unionWith (+) p q)
 
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPorTerm (n,a) p =
    M.map (*a) (M.mapKeys (+n) p)
 
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q
    | M.null p  = M.empty
    | otherwise = sumaPol (multPorTerm t q) (multPol r q)
    where (t,r) = M.deleteFindMin p
Avanzado
, , , , , , , , ,

5 soluciones de “Operaciones con polinomios como diccionarios”

  1. Responder
    albcercid 
     
type Polinomio a = M.Map Int a
 
 
ejPol1, ejPol2 :: Polinomio Int
ejPol1 = M.fromList [(0,3),(1,7),(3,-5)]
ejPol2 = M.fromList [(0,4),(3,5),(5,1)]
 
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol m1 = (M.filter (/= 0)).(M.unionWith (+) m1)
 
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPorTerm (a,b) = (M.mapKeys (+a)).(M.map (*b))
 
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
multPol m1 m2 = aux (M.assocs m1)
   where aux [] = M.fromList [(0,0)]
         aux ((a,b):xs) = sumaPol (multPorTerm (a,b) m2) (aux xs)
  2. Responder
    joscasgom1 
     
import Data.Map as M
 
type Polinomio a = M.Map Int a
 
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol d1 d2 =M.filter (/=0)( M.unionWith (+) d1 d2)
 
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPorTerm (a,b) d =M.mapKeys (+a) (M.map (*b) d)
 
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q = sumasPol (prod p q)
 
prod :: (Eq a,Num a) => Polinomio a -> Polinomio a -> [Polinomio a]
prod p q | M.null p = []
           | otherwise = multPorTerm (M.findMin p) q : prod (M.deleteMin p) q
 
sumasPol :: (Eq a, Num a) => [Polinomio a] -> Polinomio a
sumasPol [] = M.empty
sumasPol (x:xs) = sumaPol x (sumasPol xs)
  3. Responder
    paumacpar 
    sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q = M.filter (/=0) (M.unionWith (+) p q)
 
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPorTerm (n,a) p = M.mapKeys (+n) (M.mapWithKey f p)
  where f _ x = a*x
 
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q |  M.null p || M.null q = M.empty
            | otherwise = sumaPol (multPorTerm (n,a) q) (multPol r q)
  where ((n,a),r) = M.deleteFindMax p
  4. Responder
    enrnarbej 
    import Data.Map
import Prelude hiding (map,filter)
 
type Polinomio a = Map Int a
 
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p = filter (/=0) . unionWith (+) p
 
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPorTerm (n,a)= map (*a) . mapKeys (+n) 
 
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q = foldlWithKey' f empty q
            where
             f s k v = (sumaPol s . multPorTerm (k,v)) p
  5. Responder
    Juanjo Ortega (juaorture) 
    import Data.Map as M
 
sumaPol :: (Num a, Eq a) => Polinomio a -> Polinomio a -> Polinomio a
sumaPol p q | M.null p = q
            | M.null q = p
            | otherwise = limpia 0 (aux (max (fst (findMax p)) (fst (findMax q))))
        where aux n | n < 0      = p
                    | member n q = insertWithKey (a b c -> c + b) n (q!n) (aux (n-1))  
                    | otherwise  = aux (n-1)
 
multPorTerm :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPorTerm (k,x) p = aux 0
            where aux n | n > fst (findMax p) = empty
                        | member n p      = insert (k+n) (x*(p!n)) (aux (n+1))
                        | otherwise       = aux (n+1)
 
-- Otra definición usando map
multPorTerm' :: Num a => (Int,a) -> Polinomio a -> Polinomio a
multPorTerm' (k,x) p = M.map (*x) (mapKeys (+k) p)
 
multPol :: (Eq a, Num a) => Polinomio a -> Polinomio a -> Polinomio a
multPol p q = sumaPolList [multPorTerm' (k,x) p | k <- keys q, let x = q ! k]
          where sumaPolList []     = empty
                sumaPolList (x:xs) = sumaPol x (sumaPolList xs)
 
 
limpia :: (Eq a, Num a) => Int -> Polinomio a -> Polinomio a
limpia n s | n > fst (findMax s) = s
           | not (member n s)    = limpia (n+1) s
           | s ! n == 0          = delete n (limpia (n+1) s)
           | otherwise           = limpia (n+1) s

Escribe tu solución

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