多项式的计算.doc

·PAGE 14· 常用算法程序集（C语言描述） ·PAGE 15· 第1章 多项式的计算 第1章 多项式的计算 1.1 一维多项式求值 1．功能 计算多项式 p(x)=an-1xn-1+an-2xn-2+…+a1x+a0 在指定点x处的函数值。 2．方法说明 首先将多项式表述成如下嵌套形式： p(x)=(…((an-1x+an-2)x+an-3)x+…+a1)x+a0 然后从里往外一层一层地进行计算。其递推计算公式如下： un-1=an-1 uk=uk+1x+ak，k=n-2，…，1，0 最后得到的u0即是多项式值p(x)。 3．函数语句与形参说明 double plyv(a，n，x) 形参与函数类型 参 数 意 义 double a[n] 存放n-1次多项式的n个系数 int n 多项式的项数 double x 指定的自变量值 double plyv() 返回多项式值p(x) 4．函数程序（文件名：1plyv.c） double plyv(a，n，x) int n； double x，a[]； { int i； double u； u=a[n－1]； for (i=n－2； i=0； i－－) u=u*x+a[i]； return(u)； } 5．例 计算多项式 p(x)=2x6-5x5+3x4+x3-7x2+7x-20 在x=±0.9，±1.1，±1.3处的函数值。 主函数程序（文件名：1plyv0.c）如下： #include stdio.h #include 1plyv.c main() { int i； static double a[7]={－20.0，7.0，－7.0，1.0，3.0，－5.0，2.0}； static double x[6]={0.9，－0.9，1.1，－1.1，1.3，－1.3}； printf(\n)； for (i=0； i=5； i++) printf(x(%d)=%5.2lf p(%d)=%13.7e\n， i，x[i]，i，plyv(a，7，x[i]))； printf(\n)； } 运行结果为： x(0)= 0.90 p(0)=－1.856227e+01 x(1)=－0.90 p(1)=－2.671537e+01 x(2)= 1.10 p(2)=－1.955613e+01 x(3)=－1.10 p(3)=－2.151303e+01 x(4)= 1.30 p(4)=－2.087573e+01 x(5)=－1.30 p(5)=－6.340432e+00 1.2 一维多项式多组求值 1．功能 利用系数预处理法对多项式 p(x)=an-1xn-1+an-2xn-2+…+a1x+a0 进行多组求值。其中n=2k（k≥1）。 2．方法说明 首先将多项式变为首一多项式，即 T(x)=p(x)/an-1=xn-1+tn-2xn-2+…+t1x+t0 其中tk=ak/an-1（k=n-2，…，1，0）。 然后对首一多项式T(x)的系数进行预处理。其预处理过程如下： 将T(x)分解为 T(x)=(x j+b)q(x)+r(x) 其中j=2k-1，q(x)与r(x)均为2k-1-1次的首一多项式。b，q(x)与r(x)按以下规则确定： 多项式中的中项系数减1即为b，即 b= 多项式左半部分除以x j即为q(x)，即 q(x)=xs-1+qs-2xs-2+…+q1x+q0 其中s=2k-1，qi=ti+s（i=s-2，…，1，0）。 多项式右半部分减去b与q(x)的乘积即为r(x)，即 r(x)=xs-1+rs-2xs-2+…+r1x+r0 其中ri=ti-bqi（i=s-2，…，1，0）。 由于q(x)与r(x)还是首一多项式，因此，它们也可以按照上述方法分别进行分解。这个过程一直做到q(x)与r(x)的次数为1为止。在分解过程中，每次分解后的系数仍存放在T(x)的各系数的存储单元中，最后得到T(x)经分解处理后的系数。 首一多项式T(x)的系数经预处理后，就可以用这些预处理后的系数对不同的x求函数值。这种方法特别适用于对多个x进行求值，减少求值中的乘法次数。 如果原来的多项式不满足n=2k这个条件，则可以添加系数为0的各项及系数为1的最高次项。 3．函数语句与形参说明 void plys(a，n，x，m，p) 形参与函数类型 参 数 意 义 double a[n] 存放n-1次多项式的n个系数。返回时其值将被改变 int n 多项式的项数 double x[m] 存放给定的m个自变量值 int m 给定自变量的个数 double p[m] 返回时存放与给定