Usando linked lists para trabajar con polinomios
Agosto 13 2009 :: Estructuras de datos, c ::
Uno de las cosas fascinantes del Mathematica y ( ahora del wolfram alpha ) es como resuelve y además simplifica expresiones matemáticas (por ejemplo: derivando funciones y dando cada uno de los pasos). Se usa de esta manera la computadora no para hacer cálculos numéricos ( que arrojen como resultado un número ) sino para computación simbólica ( cálculos que arrojan como resultado una expresión matemática ).
La pregunta es como una maquina que guarda resultados en memoria en forma de expresiones binarias ( esencialmente números, aunque pueden representar otra cosa ) para hacer esto. La respuesta es que la representación de formulas matemáticas puede ser realizada a través de diferentes estructuras de datos y es manipulando estas estructuras que se pueden realizar estos cómputos.
Como un ejemplo básico de esto acá va un ejemplo sacado de C & Data Structures sobre como se pueden hacer operaciones sobre polinomios.
Una estructura de datos para guardar un polinomio y las funciones para llenarlo y mostrarlo.
# include <stdio.h>
# include <stdlib.h>
struct pnode
{
int exp;
int coeff;
struct pnode *link;
};
struct pnode *insert(struct pnode *p, int e,int c) {
struct pnode *temp;
temp = p;
if(p==NULL) {
p=(struct pnode *)malloc(sizeof(struct pnode));
if(p==NULL) {
printf("Error de alocación de memoria\n");
exit(0);
}
p-> exp = e;
p->coeff = c;
p-> link = NULL;
} else {
//Si tienen el mismo exponente se suman los coeficientes en vez de agregar un nodo.
if(p->exp == e) {
p->coeff = p->coeff + c;
} else {
p->link = insert(p->link, e, c);
}
}
return (p);
}
void printpoly ( struct pnode *p ) {
printf("The polynomial is\n");
while (p!= NULL) {
if(p->exp != 1) {
printf("%dx^%d\t", p->coeff, p-> exp);
} else {
printf("%dx\t", p->coeff);
}
p = p-> link;
}
printf("\n");
}
Nota: en la función de insertar si un nuevo termino tiene el mismo exponente que uno anterior se lo suma en vez de agregarlo. Esto es una de las modificaciones al código del libro.
Ordenando el polinomio
/* a function to sort a list */
struct pnode *sortpoly(struct pnode *p)
{
struct pnode *temp1,*temp2,*max,*prev,*q;
q = NULL;
while(p != NULL) {
prev = NULL;
max = temp1 = p;
temp2 = p -> link;
while ( temp2 != NULL ) {
if(max -> exp < temp2 -> exp) {
max = temp2;
prev = temp1;
}
temp1 = temp2;
temp2 = temp2-> link;
}
if(prev == NULL) {
p = max -> link;
} else {
prev -> link = max -> link;
}
max -> link = NULL;
if( q == NULL) {
q = max;
} else {
temp1 = q;
while( temp1 -> link != NULL) {
temp1 = temp1 -> link;
}
temp1 -> link = max;
}
}
return (q);
}
Una Función para sumar 2 polinomios
/* A function to add two polynomials */
struct pnode *polyadd(struct pnode *p, struct pnode *q)
{
struct pnode *r = NULL;
int e;
int c;
while((p!=NULL) && (q != NULL)) {
//p mayor exponente que q
if(p->exp > q->exp) {
r = insert(r,p->exp,p->coeff);
p = p->link;
//q mayor exponenete que p
} else if(p->exp < q->exp) {
r = insert(r,q->exp,q->coeff);
q = q->link;
//mismo exponente
} else {
c = p->coeff + q->coeff;
e = q->exp;
r = insert( r, e,c);
p = p->link;
q = q->link;
}
}
//Lo que quede de ambos polinomios
while(p != NULL) {
r = insert( r, p->exp,p->coeff);
p = p->link;
}
while(q!=NULL) {
r = insert( r, q->exp,q->coeff);
q = q->link;
}
return(r);
}
Una función para multiplicar polinomios.
Teniendo una función insertar que sume los términos del mismo exponente y una función de suma es muy fácil agregar una función que multiplique polinomios.
struct pnode *polymult(struct pnode *p, struct pnode *q) {
struct pnode *r, *r2, *temp;
r = NULL;
temp = q;
while(p != NULL) {
temp = q;
while(temp != NULL) {
r = insert(r, (temp->exp + p->exp), (temp->coeff * p->coeff));
temp = temp->link;
}
p = p->link;
}
return r;
}
Probando el programa
int main()
{
int e;
int n,i, c;
struct pnode *poly1 = NULL ;
struct pnode *poly2=NULL;
struct pnode *result;
printf("Enter the terms in the polynomial1 \n");
scanf("%d",&n);
i=1;
while ( n-- > 0 )
{
printf( "Enter the exponent and coefficient of the term number %d\n",n);
scanf("%d %d",&e,&c);
poly1 = insert ( poly1,e,c);
}
printf("Enter the terms in the polynomial2 \n");
scanf("%d",&n);
i=1;
while ( n-- > 0 )
{
printf( "Enter the exponent and coefficient of the term number %d\n",n);
scanf("%d %d",&e,&c);
poly2 = insert ( poly2,e,c);
}
poly1 = sortpoly(poly1);
poly2 = sortpoly(poly2);
printf("The polynomial 1 is\n");
printpoly ( poly1 );
printf("The polynomial 2 is\n");
printpoly ( poly2 );
result = polyadd(poly1,poly2);
printf("The result of addition is\n");
printpoly ( result );
result = polymult(poly1, poly2);
printf("The result of multiplication is\n");
printpoly ( result );
return 0;
}
Resultados
Enter the terms in the polynomial1
5
Enter the exponent and coefficient of the term number 4
5 5
Enter the exponent and coefficient of the term number 3
4 4
Enter the exponent and coefficient of the term number 2
3 3
Enter the exponent and coefficient of the term number 1
2 2
Enter the exponent and coefficient of the term number 0
1 1
Enter the terms in the polynomial2
2
Enter the exponent and coefficient of the term number 1
2 2
Enter the exponent and coefficient of the term number 0
1 1
sdfsdfThe polynomial 1 is
The polynomial is
5x^5 4x^4 3x^3 2x^2 1x
The polynomial 2 is
The polynomial is
2x^2 1x
The result of addition is
The polynomial is
5x^5 4x^4 3x^3 4x^2 2x
The result of multiplication is
The polynomial is
10x^7 13x^6 10x^5 7x^4 4x^3 1x^2
Pensando en todo esto es interesante en como en MathML se usan estructuras arboreas ( MathML esta basado en XML ) para representar expresiones matematicas y las implicaciones que puede tener a futuro para la automatización de determinado tipo de calculos.
Referencias
C & Data Structures, Deshpande, Kakde; Charles River Media, 2004
