Máximos valores de una expresión aritmética
Las expresiones aritméticas generales se pueden definir usando el siguiente tipo de datos
1 2 3 4 5 6 7 |
data Expr = C Int | X | S Expr Expr | R Expr Expr | P Expr Expr | E Expr Int deriving (Eq, Show) |
Por ejemplo, la expresión
1 |
3*x - (x+2)^7 |
se puede definir por
1 |
R (P (C 3) X) (E (S X (C 2)) 7) |
Definir la función
1 |
maximo :: Expr -> [Int] -> (Int,[Int]) |
tal que maximo e xs
es el par formado por el máximo valor de la expresión e
para los puntos de xs
y en qué puntos alcanza el máximo. Por ejemplo,
1 2 |
λ> maximo (E (S (C 10) (P (R (C 1) X) X)) 2) [-3..3] (100,[0,1]) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
data Expr = C Int | X | S Expr Expr | R Expr Expr | P Expr Expr | E Expr Int deriving (Eq, Show) maximo :: Expr -> [Int] -> (Int,[Int]) maximo e ns = (m,[n | n <- ns, valor e n == m]) where m = maximum [valor e n | n <- ns] valor :: Expr -> Int -> Int valor (C x) _ = x valor X n = n valor (S e1 e2) n = valor e1 n + valor e2 n valor (R e1 e2) n = valor e1 n - valor e2 n valor (P e1 e2) n = valor e1 n * valor e2 n valor (E e1 m1) n = valor e1 n ^ m1 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
from dataclasses import dataclass @dataclass class Expr: pass @dataclass class C(Expr): x: int @dataclass class X(Expr): pass @dataclass class S(Expr): x: Expr y: Expr @dataclass class R(Expr): x: Expr y: Expr @dataclass class P(Expr): x: Expr y: Expr @dataclass class E(Expr): x: Expr y: int def valor(e: Expr, n: int) -> int: match e: case C(a): return a case X(): return n case S(e1, e2): return valor(e1, n) + valor(e2, n) case R(e1, e2): return valor(e1, n) - valor(e2, n) case P(e1, e2): return valor(e1, n) * valor(e2, n) case E(e1, m): return valor(e1, n) ** m assert False def maximo(e: Expr, ns: list[int]) -> tuple[int, list[int]]: m = max((valor(e, n) for n in ns)) return (m, [n for n in ns if valor(e, n) == m]) |
La función maximo puede ser implementada de la siguiente manera:
La función eval se encarga de evaluar el valor de la expresión para un valor específico de x, mientras que maximo utiliza esta función para evaluar todos los valores de x en la lista y encontrar el máximo y en qué puntos alcanza el máximo.