首页 > 代码库 > 数学之路-python计算实战(3)-霍纳法则
数学之路-python计算实战(3)-霍纳法则
假设有n+2个实数a0,a1,…,an,和x的序列,要对多项式Pn(x)= anx ^n+a(n-1)x^(n-1)+…+a1x+a0求值,直接方法是对每一项分别求值,并把每一项求的值累加起来,这种方法十分低效,它需要进行n+(n-1)+…+1=n(n+1)/2次乘法运算和n次加法运算。有没有更高效的算法呢?答案是肯定的。通过如下变换我们可以得到一种快得多的算法,即Pn(x)= anx ^n+a(n-1)x^(n-1)+…+a1x+a0=((…(((anx +an-1)x+an-2)x+ an-3)…)x+a1)x+a0,这种求值的安排我们称为霍纳法则。
本博客所有内容是原创,如果转载请注明来源
http://blog.csdn.net/myhaspl/
a=[1,-6,8,8,4,-40]
myx=3
b=[]
b.append(a[0])
for ai in a[1:]:
b.append(ai+myx*b[-1])
print b[-1]
deep@myddb:~/src$ pypy test.py17
deep@myddb:~/src$
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。