¿Cómo almacenar un polinomio?

Question

Los enteros se pueden usar para almacenar números individuales, pero no expresiones matemáticas. Por ejemplo, digamos que tengo la expresión:

6x^2 + 5x + 3

¿Cómo puedo almacenar el polinomio? Pude crear mi propio objeto, pero no veo cómo podría representar el polinomio a través de los datos de los miembros. No quiero crear una función para evaluar un argumento pasado porque no solo necesito evaluarlo, sino que también necesito manipular la expresión.

¿Es un vector mi única opción o hay una solución más adecuada?

Answer 1

Una forma simple pero ineficiente sería almacenarlo como una lista de coeficientes. Por ejemplo, el polinomio en la cuestión sería el siguiente:

[6, 5, 3] 

Si un término que falta, colocar un cero en su lugar. Por ejemplo, el polinomio 2x^3 - 4x + 7 estaría representado como esto:

[2, 0, -4, 7] 

El grado del polinomio está dada por la longitud de la lista de menos uno. Esta representación tiene una seria desventaja: para polinomios dispersos, la lista contendrá muchos ceros.

Una representación más razonable del término lista de un polinomio disperso es como una lista de términos distintos de cero, donde cada término es una lista que contiene el orden del término y el coeficiente para ese orden; el grado del polinomio viene dado por el orden del primer término. Por ejemplo, el polinomio x^100+2x^2+1 estarían representados por esta lista:

[[100, 1], [2, 2], [0, 1]] 

Como ejemplo de la utilidad de esta representación es, el libro SICP construye un simple pero muy eficaz symbolic algebra system usando la segunda representación para los polinomios descritos anteriormente.

Answer 2

Una lista no es la única.

Puede usar un mapa (diccionario) mapeando el exponente al coeficiente correspondiente.

Usar un mapa, el ejemplo sería

{2: 6, 1: 5, 0: 3} 

Una lista de pares (coeficiente, exponente) es bastante estándar. Si sabes que tu polinomio es denso, es decir, todas las posiciones del exponente son enteros pequeños en el rango de 0 a algún exponente máximo pequeño, puedes usar la matriz, como lo veo a Óscar López recién publicado. :)

Answer 3

Vector/matriz es una elección obvia. Dependiendo del tipo de expresiones, puede considerar algún tipo de vector disperso (por encargo, es decir, basado en el diccionario o incluso en la lista vinculada si sus expresiones tienen 2-3 coeficientes distintos de cero 5x^100 + x).

En cualquier caso, la exposición a través de clase/interfaz personalizada sería beneficioso ya que puede reemplazar la implementación más tarde. Es probable que desee proporcionar operaciones estándar (+, -, *, equivalentes) si planea escribir una gran cantidad de código de manipulación de expresiones.

Answer 4

necesita almacenar dos cosas:

1. El grado de su polinomio (por ejemplo, "3")
2. una lista que contiene cada coeficiente (por ejemplo, "{3, 0, 2}")

En C++ estándar, "std :: vector <>" y "std :: list <>" pueden hacer ambas cosas.

Answer 5

Puede representar expresiones como árboles de expresiones. Ver por ejemplo .NET Expression Trees.

Esto permite expresiones mucho más complejas que los polinomios simples y esas expresiones también pueden usar múltiples variables.

En .NET puede manipular el árbol de expresiones como un árbol Y puede evaluarlo como una función.

 Expression<Func<double,double>> polynomial = x => (x * x + 2 * x - 1); 
     double result = polynomial.Compile()(23.0); 

Answer 6

Simplemente almacene los coeficientes en una matriz o vector. Por ejemplo, en C++ si solo está utilizando coeficientes enteros, puede usar std::vector<int>, o para números reales, std::vector<double>. Luego, simplemente presione los coeficientes en orden y acceda a ellos por el número variable de exponente.

Por ejemplo (de nuevo en C++), para almacenar 5 * x^3 + 9 * x - 2 que podría hacer:

std::vector<int> poly; 
    poly.push_back(-2); // x^0, acceesed with poly[0] 
    poly.push_back(9); // x^1, accessed with poly[1] 
    poly.push_back(0); // x^2, etc 
    poly.push_back(5); // x^3, etc 

Si tiene grandes y dispersas, polinomios, entonces tal vez te quiere usar un mapa en lugar de un vector. Si ha fijado longitudes de tamaño, quizás utilice una matriz de longitud fija en lugar de un vector.

He usado C++ para ejemplos, pero este mismo esquema se puede usar en cualquier idioma.

Answer 7

También puede transformarlo en reverse Polish notation:

6x^2 + 5x + 3 -> x 2^6 * x 5 * + 3 +

Dónde x y los números son " insertado "en una pila y las operaciones (^, *, +) toman los dos valores más altos de la pila y los reemplazan con el resultado de la operación. Al final, obtienes el valor resultante en la pila.

De esta forma es fácil calcular expresiones arbitrariamente complejas.

Esta representación también está cerca de la representación en árbol de expresiones donde los nodos de árbol no hoja representan operaciones y funciones y los nodos hoja son para constantes y variables.

Lo bueno de los árboles es que también puedes evaluar fácilmente las expresiones y también puedes hacer cosas como la diferenciación simbólica de ellas. Ambos tienen naturaleza recursiva.

Answer 8

Un enfoque orientado a objetos diría que un polinomio es una colección de monomios, y un monomio encapsula un coeficiente y un exponente juntos.

Este enfoque funciona cuando cuando se tiene un polinomio de esta manera:

y(x) = x^1000 + 1 

Un enfoque que ató una estructura de datos a un polinomio de orden sería terriblemente derrochador para este caso patológico.