Come memorizzare un polinomio?

Question

I numeri interi possono essere utilizzati per memorizzare numeri individuali, ma non espressioni matematiche. Ad esempio, consente di dire che ho l'espressione:

6x^2 + 5x + 3

Come dovrei conservare il polinomio? Potrei creare il mio oggetto, ma non vedo come potrei rappresentare il polinomio attraverso i dati dei membri. Non voglio creare una funzione per valutare una discussione passata perché non solo ho bisogno di valutarla, ma anche di manipolare l'espressione.

È un vettore la mia unica opzione o esiste una soluzione più adatta?

Answer 1

Un modo semplice ma inefficiente sarebbe memorizzarlo come un elenco di coefficienti. Ad esempio, il polinomio nella domanda sarà simile a questo:

[6, 5, 3] 

Se manca un termine, posizionare uno zero al suo posto. Ad esempio, il polinomio 2x^3 - 4x + 7 sarebbero rappresentati simili:

[2, 0, -4, 7] 

Il grado del polinomio è data dalla lunghezza della lista meno uno. Questa rappresentazione ha un serio svantaggio: per i polinomi sparsi, la lista conterrà molti zeri.

Una rappresentazione più ragionevole dell'elenco di termini di un polinomio sparse è come un elenco di termini diversi da zero, in cui ogni termine è un elenco contenente l'ordine del termine e il coefficiente per tale ordine; il grado del polinomio è dato dall'ordine del primo termine. Ad esempio, il polinomio x^100+2x^2+1 sarebbe rappresentato da questo elenco:

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

Come esempio di come utile questa rappresentazione è, il libro SICP costruisce un semplice ma molto efficace symbolic algebra system utilizzando la seconda rappresentazione di polinomi sopra descritti.

Answer 2

Un elenco non è l'unica opzione.

È possibile utilizzare una mappa (dizionario) che associa l'esponente al coefficiente corrispondente.

Utilizzando una mappa, il tuo esempio sarebbe

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

una lista di coppie (coefficiente, esponente) è abbastanza standard. Se sai che il tuo polinomio è denso, cioè tutte le posizioni esponenti sono piccoli interi compresi tra 0 e qualche piccolo massimo esponente, puoi usare l'array, come vedo Óscar Lopez appena pubblicato. :)

Answer 3

Vector/array è una scelta ovvia. A seconda del tipo di espressioni, si può considerare una specie di tipo vettoriale sparse (personalizzato, cioè basato sul dizionario o anche sull'elenco collegato se le espressioni hanno coefficienti non zero pari a 5x^100 + x).

In entrambi i casi l'esposizione tramite classe/interfaccia personalizzata sarebbe utile in quanto è possibile sostituire l'implementazione in un secondo momento. Probabilmente vorrai fornire operazioni standard (+, -, *, uguale) se prevedi di scrivere un sacco di codice di manipolazione delle espressioni.

Answer 4

è necessario memorizzare due cose:

1. Il grado del polinomio (ad esempio "3")
2. un elenco contenente ogni coefficiente (per esempio "{3, 0, 2}")

In standard C++, "std :: vector <>" e "std :: list <>" possono eseguire entrambe le operazioni.

Answer 5

È possibile rappresentare espressioni come alberi di espressione. Vedi ad esempio .NET Expression Trees.

Ciò consente espressioni molto più complesse rispetto ai polinomi semplici e tali espressioni possono anche utilizzare più variabili.

In .NET è possibile manipolare l'albero delle espressioni come un albero E è possibile valutarlo come una funzione.

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

Answer 6

Basta memorizzare i coefficienti in un vettore o matrice. Ad esempio, in C++ se si utilizzano solo coefficienti interi, è possibile utilizzare std::vector<int> o per numeri reali, std::vector<double>. Quindi basta spingere i coefficienti in ordine e accedervi con un numero di esponente variabile.

Per esempio (di nuovo in C++), per memorizzare 5 * x^3 + 9 * x - 2 si potrebbe fare:

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 

Se si dispone di grandi, sparse, polinomi, allora forse ci si vuoi usare una mappa invece di un vettore. Se hai fissato lunghezze di dimensioni, allora potresti usare una matrice di lunghezza fissa invece di un vettore.

Ho usato C++ per gli esempi, ma questo stesso schema può essere utilizzato in qualsiasi lingua.

Answer 7

Si può anche trasformarlo in reverse Polish notation:

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

Dove x e numeri sono " spinto "su una pila e le operazioni (^, *, +) prendono i due valori più alti dalla pila e li sostituiscono con il risultato dell'operazione. Alla fine ottieni il valore risultante in pila.

In questo modulo è facile calcolare espressioni arbitrariamente complesse.

Questa rappresentazione è anche vicino alla rappresentazione ad albero di espressioni in cui i nodi di albero non foglia rappresentano operazioni e funzioni e i nodi foglia sono per costanti e variabili.

Ciò che è buono per gli alberi è che puoi anche valutare facilmente le espressioni e puoi anche fare qualcosa come la differenziazione simbolica su di esse. Entrambi hanno natura ricorsiva.

Answer 8

Un approccio orientato agli oggetti direbbe che un polinomio è una raccolta di monomali e un monomero incapsula un coefficiente ed esponente insieme.

Questo approccio funziona quando quando si dispone di un polinomio come questo:

y(x) = x^1000 + 1 

Un approccio che ha legato una struttura di dati ad un ordine polinomiale sarebbe terribilmente dispendioso per questo caso patologico.