霍纳法则(Horner Rule)介绍及C语言实现

霍纳法则(Horner Rule)介绍及C语言实现参考自:http://flynoi.blog.hexun.com/31272178_d.html

霍纳法则(Horner Rule)介绍及C语言实现霍纳法则简介

假设有n+2个实数a0,a1,…,an,和x的序列,要对多项式Pn(x)= anxn+an-1xn-1+…+ax+a求值,直接方法是对每一项分别求值,并把每一项求的值累加起来,这种方法十分低效,它需要进行n+(n-1)+…+1=n(n+1)/2次乘法运算和n次加法运算。有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法,即Pn(x)= anxn +an-1xn-1+…+ax+a=((…(((anx +an-1)x+an-2)x+ an3)…)x+a1)x+a,这种求值的安排我们称为霍纳法则。

霍纳法则(Horner Rule)介绍及C语言实现霍纳法则C语言实例

霍纳法则(Horner Rule)介绍及C语言实现
/* 霍纳算法实例 */

#include <stdio.h>

long int 
horner(int coefficient[], int n, int x) //coefficient[]为待求多项式的系数数组,n为数组大小,x为多项式中未知数x的具体值
{                                       //注意:coefficient[0]存放系数a0,coefficient[1]存放系数a1,以此类推…
    int i;
    long int result;
    
    result = coefficient[n-1];
    for(i = 1; i <= n-1; i++)
    {
        result = result * x + coefficient[n-1-i];
    }

    return result;
}

int 
main(void)
{
    long int p;
    int a[4] = {3, 2, 1, 1};
    p = horner(a, 4, 1);
    printf("polynomial x^3 + x^2 + 2x + 3 = %ld\n", p);
}
霍纳法则(Horner Rule)介绍及C语言实现

实例测试结果:

霍纳法则(Horner Rule)介绍及C语言实现

霍纳法则(Horner Rule)介绍及C语言实现,布布扣,bubuko.com

霍纳法则(Horner Rule)介绍及C语言实现

上一篇:微信公众号之兼容性


下一篇:twisted应用中异步回调的方式及线程的应用