运用Horner规则计算多项式的值
对于一个多项式，如：5*X^3 + 4*X^2 + 2*X，我们该如何编程来求多项式的值呢？最直接的做法就是一项一项的求：先求5*X^3，再求4*X^2，继续求2*X，最后把它们的值加起来即可，这样做需要6次乘法运算，2次加法运算。但是运用Horner规则我们可以使用更少的乘法运算和加法运算来得到结果。Horner规则的思想是不断的运用乘法分配率提出X项。以刚才的例子来说，计算过程如下：
[(5*X + 4)*X + 2]*X
这样，只需要3次乘法运算和2次加法运算即得到结果了。
下面的C程序将普通做法和运用Horner规则进行对比
#include <stdio.h>#define MAX_NUM 100 //约定多项式项数不超过100 /*直接计算多项式*/float polynomial_1(int n[][2],int num,float x,int* count_mul,int* count_add){ int i,j; float sinpoly;//每个单项的值 float result;//多项式的值 result = 0; for(i = 0;i < num;i++) { sinpoly = n[i][0]; for(j = 0;j < n[i][1];j++) { sinpoly = sinpoly * x; (*count_mul)++; } result = result + sinpoly; (*count_add)++; } return result;}/*运用Horner规则计算多项式*/float polynomial_2(int n[][2],int num,float x,int* count_mul,int* count_add){ int i,j; float result;//多项式的值 result = n[0][0]; for(i = 1;i < num;i++) { for(j = 0;j < n[i-1][1] - n[i][1];j++) { result = result * x; (*count_mul)++; } result += n[i][0]; (*count_add)++; } if(n[num-1][1] != 0)//如果最后一项不是常数项，则要继续乘法运算 { for(j = 0;j < n[num-1][1];j++) { result *= x; (*count_mul)++; } } return result; } int main(){ int n[MAX_NUM][2]; int num;//多项式项数 int count_mul;//乘法运算次数 int count_add;//加法运算次数 float x; int i; printf("please input the number of polynomial:\n"); scanf("%d",&num);//输入多项式项数 printf("please input x:\n"); scanf("%f",&x); for(i = 0;i < num;i++) scanf("%d %d",&n[i][0],&n[i][1]);//第一个数表示系数，第二个数表示x的阶数 count_mul = 0; count_add = 0; printf("polynomial_1=%f,count_mul=%d,count_add=%d\n",polynomial_1(n,num,x,&count_mul,&count_add),count_mul,count_add); count_mul = 0; count_add = 0; printf("polynomial_2=%f,count_mul=%d,count_add=%d\n",polynomial_2(n,num,x,&count_mul,&count_add),count_mul,count_add); system("pause"); return 0;}?