CS19002 Programming and Data Structures Laboratory | Spring 2010, Section 5 |
A multi-variate polynomial can be represented by a sum of non-zero terms. We need to store the number of terms, and a list of the non-zero terms. For example, consider the following 4-variate polynomial, where the variables are denoted by a,b,c,d.
5a^{2}bd^{3} - 2d^{5} + abcd + 31
A possible representation of this polynomial is shown below.
Number of terms 4
Term 0 5 2 1 0 3
Term 1 -2 0 0 0 5
Term 2 1 1 1 1 1
Term 3 31 0 0 0 0
In order to implement this storage of a multi-variate polynomial, we use the following C structure.
#define NVAR 5 #define MAX_TERM 1000 typedef struct { int nterm; int term[MAX_TERM][1+NVAR]; } mvpoly;
I supply a function to print a multi-variate polynomial in the above storage format.
void polyprint ( mvpoly f ) { int i, k; for (i=0; i<f.nterm; ++i) { if ((i)&&(f.term[i][0]>=0)) printf("+"); if (f.term[i][0] != 1) printf("%d", f.term[i][0]); for (k=1; k<=NVAR; ++k) { if (f.term[i][k]) printf("%c",'a'+(char)(k-1)); if (f.term[i][k]>1) printf("^%d", f.term[i][k]); } } }
Henceforth, we will assume that n is the number of variables.
Write a function in order to return the polynomial
a + b + c + ... (n variables)
The function should have the following prototype:
mvpoly setpoly ();
mvpoly polyprod ( mvpoly f, mvpoly g );
Note that when you multiply two multi-variate polynomials, the same product monomial may appear more than once during the monomial-by-monomial product of the input polynomials. It is, therefore, necessary to collect similar terms in the output polynomial. For example, the product of a+b and a+2b should be computed as a^{2}+3ab+2b^{2} instead of as a^{2}+2ab+ab+2b^{2}.
Use n = 5 variables a,b,c,d,e. Compute and print the polynomials (a+b+c+d+e)^{i} for i = 1,2,3,4,5.
Here is a possible output for n = 3.
(a+b+c)^1 = a+b+c (a+b+c)^2 = a^2+2ab+2ac+b^2+2bc+c^2 (a+b+c)^3 = a^3+3a^2b+3a^2c+3ab^2+6abc+3ac^2+b^3+3b^2c+3bc^2+c^3
Lab Home | Submission Site | My Home |