运用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;
}