牛顿差分插值法的正确递归Python实现，获取递归中的部分返回值
我写了一个递归函数，用Python来计算一种插值方法的序列。
这个方法在下面的图片中有图示说明：
f[x]=f(x) 和 f[x0,x1]= (f[x1]-f[x0]) / (x1 - x0)，所以 f[x0,x1,...xn]=f[所有的最小值,除了最后一个] / (最后一个-第一个)。
就是这样，递归地进行。
我写了以下的代码：
xxs=[]
yys=[]
coeficientes = []
h = {}
r = 0.0
def a_j(xx,yy):
global r
if len(yy) == 1:
h[xx[0]] = yy[0]
return yy[0]
else:
r = (a_j(xx[1:],yy[1:]) - a_j(xx[:-1],yy[:-1])) / (xx-1]-xx[0])
h[''.join(str(i) for i in xx[::-1])]=r
coeficientes.append(r)
return ( r )
但是我需要输出一个数组，里面只有那些用绿色圆圈标记的数字。我对如何在递归实现中只获取这些数字感到困惑。
这些数字有一个共同的特点，就是它们总是从X_0开始，所以我考虑给它们打标签，或者使用字典可能会有帮助。
期望的结果是：
[1,1.71828,1.47625,.84553]
我得到的是：
[1, 2.71828, 7.3890599999999997, 20.085540000000002, 1.71828, 4.6707799999999997, 12.696480000000001, 1.4762499999999998, 4.0128500000000003, 0.84553333333333347]
对于另一次运行，如果用不同的参数调用：
a_j([1,2,3,5][4,3.5,4,5.6])
应该输出：
[4,-0.5,0.5,-0.1]
我得到的是：
[4, 3.5, 4, 5.6, -0.5, 0.5, 0.5, 0.7999999999999998, 0.09999999999999994, -0.10000000000000002]
另一个例子：
a_j([-2,-1,0,1,2], [13,24,39,65,106])
将输出：
[13, 24, 39, 65, 106, 11, 15, 2, 26, 5, 1, 41, 7, 0, -1]
但输出应该是：
[13,11,2,1.167,-0.125]
我还成功写了一个迭代实现，这个已经是正确的：
diferencias = {}
coeficientes = []
def sublists_n(l, n):
subs = []
for i in range(len(l)-n+1):
subs.extend([l[i:i+n]])
return subs
def sublists(l):
subs = []
for i in range(len(l)-1,0,-1):
subs.extend(sublists_n(l,i))
subs.insert(0,l)
return subs[::-1]
def diferenciasDivididas(xx,yy,x):
combinaciones = sublists([i for i in range(len(xx))])
for c in combinaciones:
if len(c) == 1:
diferencias[str(c[0])]= float(yy[c[0]])
if c[0] == 0:
coeficientes.append(float(yy[c[0]]))
else:
c1 = diferencias.get(''.join(str(i) for i in c[1:]))
c2 = diferencias.get(''.join(str(i) for i in c[:-1]))
d = float(( c1 - c2 ) / ( xx[c[len(c)-1]] - xx[c[0]] ))
diferencias[''.join(str(i) for i in c)] = d
if c[0] == 0:
coeficientes.append(float(d))
我只是想知道我缺少了什么？
4 个回答
因为你在使用递归，所以每次函数结束时都会把每个值加到结果里，这样你得到的顺序会是反向的，也就是 xn, ... , x3, x2, x1。
当你完成所有的递归并最后一次退出函数时，只需要把这个列表反转一下，这个过程有很多简单的方法可以做到，而且之前也有人问过这个问题。我把你想用的方法留给你自己去选择（或者记得“谷歌是你的朋友”）。
试试这个：
array=[]
h={}
r=0
def a_j(xx,yy):
global r
if len(yy) == 1:
h[int(xx[0])]=yy[0]
return yy[0]
else:
r=( a_j(xx[1:],yy[1:]) - a_j(xx[:-1],yy[:-1])) / (xx[-1]-xx[0])
h[int(''.join(str(i) for i in xx[::-1]))]=r
return r
a_j([0,1,2,3], [1,2.71828,7.38906,20.08554])
array=[h[key] for key in sorted(h.keys())]
print array
输出结果： [1, 2.71828, 7.3890599999999997, 20.085540000000002, 1.71828, 4.6707799999999997, 12.696480000000001, 1.4762499999999998, 4.0128500000000003, 0.84553333333333347]
在这段代码中，首先把一些值放进一个字典里，字典的键是将xx中的元素反转并转换成整数后的结果。
你这里得到负值是因为你没有把减法用括号括起来。否则，代码看起来没问题。
r = ( a_j(xx1,yy1) - a_j(xx0,yy0) ) / (xx[len(xx)-1]-xx[0])
http://www.mathcs.emory.edu/~valerie/courses/fall10/155/resources/op_precedence.html
我对这个脚本做了一些修改。
array=[]
r='s'
s=0
def a_j(xx,yy):
global r,s
if r == 's':
s=xx[0]
r=0.0
if len(yy) == 1:
if xx[0]==s: array.append(yy[0])
return float(yy[0])
else:
r=( a_j(xx[1:],yy[1:]) - a_j(xx[:-1],yy[:-1])) / (xx[-1]-xx[0])
if xx[0]==s: array.append(r)
return float(r)
a_j([1,2,3,5],[4,3.5,4,5.6])
print array
输出结果是： [4, -0.5, 0.5, -0.10000000000000002]
另外，你给的第二个例子看起来不太对。 a_j([-2,-1,0,1,2], [13,24,39,65,106]) --> [13,11,4,7,-3]
上面的答案说第三个元素是4。
3rd element means --> x(-2,-1,0) -> x(-1,0) - x(-2,-1)/(2)
-> x(0)-x(-1)/1 - x(-1)-x(-2)/(1) /(2)
->(39-24) - (24-13) /(2)
->15-11/(2)
->4/2 =2
如果我错了，请纠正我。