秦九韶算法的理解

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/05 17:00:27

秦九韶算法的理解
秦九韶算法的理解

秦九韶算法的理解
对n次多项式,a[n]x^n+...+a[1]x+a[0],可以分解为如下计算过程:
v[0] = a[n]
v[1] = v[0]*x + a[n-1]
v[2] = v[1]*x + a[n-2]
...
v[n] = v[n-1]*x + a[0]
对于一个n次多项式,至多做n次乘法和n次加法.其最大的意义在于将求n次多项式的值转化为求n个一次多项式的值,相比直接计算则需要2+3+...+n+(n+1)次乘法和n次加法,本质是避免了重复计算x的n次方.