UC知道有没有人了解Horner算法的？
来源：百度知道 编辑：UC知道 时间：2024/05/05 05:35:44
秦九韶算法是中国南宋时期的数学家秦九韶提出的一种多项式简化算法。在西方被称作霍纳算法（Horner algorithm或Horner scheme），是以英国数学家威廉·乔治·霍纳命名的.
把一个n次多项式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改写成如下形式：
f(x)=a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0]
=(a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0]
=((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0]
=......
=(......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0].
求多项式的值时，首先计算最内层括号内一次多项式的值，即
v[1]=a[n]x+a[n-1]
然后由内向外逐层计算一次多项式的值，即
v[2]=v[1]x+a[n-2]
v[3]=v[2]x+a[n-3]
......
v[n]=v[n-1]x+a[0]
这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。
（注：中括号里的数表示下标）
结论：对于一个n次多项式，至多做n次乘法和n次加法。
这是horner算法的简介，如果我想去改进这个算法，把一个未知数x改成两个，或者三个未知数，x，y，z这样。请教编程达人！！
一个未知数的算法如下：
v[n]=a[n];
for(i=n-1;i>0;i--)
{
v[i]=v[i+1]*x+a[i];
}
return v[0];
把一个n次多项式f(x)=a[n]x^n+a[n-1]x^(n-1)+......+a[1]x+a[0]改写成如下形式：
f(x)=a[n]x^n+a[n-1]x^(n-1))+......+a[1]x+a[0]
=(a[n]x^(n-1)+a[n-1]x^(n-2)+......+a[1])x+a[0]
=((a[n]x^(n-2)+a[n-1]x^(n-3)+......+a[2])x+a[1])x+a[0]
=......
=(......((a[n]x+a[n-1])x+a[n-2])x+......+a[1])x+a[0].
求多项式的值时，首先计算最内层括号内一次多项式的值，即
v[1]=a[n]x+a[n-1]
然后由内向外逐层计算一次多项式的值，即
v[2]=v[1]x+a[n-2]
v[3]=v[2]x+a[n-3]
......
v[n]=v[n-1]x+a[0]
这样，求n次多项式f(x)的值就转化为求n个一次多项式的值。
（注：中括号里的数表示下标）
结论：对于一个n次多项式，至多做n次乘法和n次加法。
这是horner算法的简介，如果我想去改进这个算法，把一个未知数x改成两个，或者三个未知数，x，y，z这样。请教编程达人！！
一个未知数的算法如下：
v[n]=a[n];
for(i=n-1;i>0;i--)
{
v[i]=v[i+1]*x+a[i];
}
return v[0];
你的意思是计算
sigma(a(i,j,k)*x^i*y^j*z^k)，sigma对i,j,k求和？
我有一个想法，但是和秦九韶的算法不同，显然他的算法更先进。
可以借助空间换取时间。
用递推的方法填表f[m,n,p]使f[i,j,k]=x^i*y^j*z^k
最后求和s=..就可以
这种算法浪费了空间，显然不好。但是可以比较好的完成任务，时间复杂度O(MNP)己经是最低值。
另外可以优化空间，方法类似秦九韶算法。类似滚动数组。其实没有必要。你可以思考一下。先对x的0次方的y^j*z^k求和，它可以拆成多N个任务。这样可以把空间复杂度降至O(1)。不过我认为没有必要