多项式求值

一、一维多项式求值：

P(x)=3x^6+7x^5+3x^4+3x^3+8x^2+5x+23

一个通用的计算多项式的值的算法可以采用递推的方式。首先可以将上面多项式变形为如下的等价方式：

P(x)=(...((a_n-1x+a_n-2)x+a_n-3)x+...+a₁)x+a₀

通过以上表达式可以看出，只要从里往外逐层按照如下的方式递推，便可以计算得到一个一维多项式的值：

R_k=R_k+1*x+a_k

具体示例代码如下：

 1 /*
 2  * @author
 3  * 一维多项式求值,从最高一项开始迭代计算
 4  */
 5 void polynomialSingle(double x, double coefficient[], int len) {
 6     double temp;
 7     int i;
 8     temp = coefficient[0];
 9     for (i = 1; i < len; i++) {
10         temp = temp * x + coefficient[i];
11     }
12     printf("The result of the polynomial is %f
", temp);
13 }
14 
15 void initialization() {
16     double coefficient[7]={3.0,7.0,-3.0,2.0,7.0,-7.0,-15.0};
17     double x=-2.0;
18     polynomialSingle(x,coefficient,7);
19 }

二、二维多项式求值

与一维多项式求值的思想一致。具体示例如下：

1、将含x,y二维多项式看成是两个一维多项式：

 1 /*
 2  * @author
 3  * 二维多项式求值
 4  * 以下方法以一维多项式求值的为基础,将二维转化成一维的形式
 5  * （16+17y+18y^2+19y^3+20y^4)x^3+（11+12y+13y^2+14y^3+15y^4)x^2+
 6  * （6+7y+8y^2+9y^3+10y^4)x+（1+2y+3y^2+4y^3+5y^4)
 7  * 这样将含y的部分看成是x的系数部分,x的系数部分又可以看出是含y的一维多项式求值，故多次利用一维
 8  * 多项式求值的方法
 9  *
10  * 注意在求x的一维多项式时，每一次循环都乘了一个x，而多项式中含有常数项，所以要除以一个x
11  */
12 void polynomialDouble(double coefficientMatrix[], double x, double y, int m,
13         int n) {
14     int i, j;
15     double s, temp = 0, k;
16     for (i = 0; i < m; i++) {
17         s = coefficientMatrix[i * n];
18 //        printf("
co[%d*%d]=%f ",i,n,coefficientMatrix[i*n]);
19         for (j = 1; j < n; j++) {
20             s = s * y + coefficientMatrix[i * n + j];
21 //            printf("co[%d*%d+%d]=%f ",i,n,j,coefficientMatrix[i*n+j]);
22         }
23         k = temp + s;
24         temp = k * x;
25     }
26     printf("The result of polynomialDouble is %f
", temp / x);
27 }
28 
29 void initialization() {
30     //polynomialDouble
31     double coefficient[4][5] = { { 20.0, 19.0, 18.0, 17.0, 16.0 }, { 15.0, 14.0,
32             13.0, 12.0, 11.0 }, { 10.0, 9.0, 8.0, 7.0, 6.0 }, { 5.0, 4.0, 3.0,
33             2.0, 1.0 } };
34 double x = 0.5, y = -2.0;
35     polynomialDoubleTwo(*coefficient, x, y, 4, 5);
36 }

2、将含x看成是一个常变量，这样二维多项式变成含y的一维多项式：

/*
 * @author
 * 二维多项式求值
 * 与第一种方法不同的是，将二维多项式看成是一个含y的一维多项式求值,x看成是一常量
 * 即多项式变形为1+2y+3y^2+4y^3+5y^4+6x+7xy+8xy^2+9xy^3+10xy^4+
 * 11x^2+12x^2y+13x^2y^2+14x^2y^3+15x^2y^4+16x^3+17x^3y+18x^3y^2+19x^3y^3+20x^3y^4
 * 这样每一次循环x相当于是y的系数常量
 * 注意：系数矩阵的变化
 */
void polynomialDoubleTwo(double coefficientMatrix[], double x, double y, int m,
        int n) {
    int i, j;
    double s, temp = 0, k = 1.0;
    for (i = 0; i < m; i++) {
        s = coefficientMatrix[i * n] * k;
//        printf("
co[%d*%d]=%f ",i,n,coefficientMatrix[i*n]);
        for (j = 1; j < n; j++) {
            s = s * y + coefficientMatrix[i * n + j] * k;
//            printf("co[%d*%d+%d]=%f ",i,n,j,coefficientMatrix[i*n+j]);
        }
        k = k * x;
        temp = temp + s;
    }
    printf("The result of polynomialDouble is %f
", temp);
}

void initialization() {
    double coefficient[4][5] = { { 5.0, 4.0, 3.0, 2.0, 1.0 }, { 10.0, 9.0, 8.0,
            7.0, 6.0 }, { 15.0, 14.0, 13.0, 12.0, 11.0 }, { 20.0, 19.0, 18.0,
            17.0, 16.0 } };
    double x = 0.5, y = -2.0;
    polynomialDoubleTwo(*coefficient, x, y, 4, 5);
}