python - 如何解决 Python 中的递归关系

Question

我正在尝试编写代码来给出递归关系的数字答案。该关系本身很简单，定义如下。变量x是一个整数

• p(i) = p(i+2)/2 + p(i-1)/2 如果 i > 0 且 i < x
• p(0) = p(2)/2
• p(i) = 1 如果 i >= x

这也在这段代码中。

from __future__ import division
def p(i):
    if (i == 0):
        return p(2)/2
    if (i >= x):
        return 1
    return p(i-1)/2+p(i+2)/2


x = 4
#We would like to print p(0)  for example.

这当然不会让您实际计算 p(0)。如何在 Python 中执行此操作？

---

是否可以建立一个 numpy.linalg.solve 可以求解的联立方程组？

Answer 1

你是对的，这可以用线性代数来解决。我在下面所做的是一个简单的硬编码翻译。 p(0) 到 p(3) 的方程式通过重新排列进行编码，使右侧为 =0。对于p(4)和p(5)作为base case出现在递归关系中，右边有一个=1边。

• -p(0) + p(2)/2 = 0

• p(i-1)/2 - p(i) + p(i+2)/2 = 0 对于 i > 0 和 i < x

• p(i) = 1 如果 i >= x

这是为 n=4 硬编码的程序

import numpy
a=numpy.array([[-1,   0, 0.5,  0,   0,   0], # 0
               [0.5, -1,   0,0.5,   0,   0], # 1
               [0,  0.5,  -1,  0, 0.5,   0], # 2
               [0,    0, 0.5, -1,   0, 0.5], # 3
               [0,    0,   0,  0,   1,   0], # 4
               [0,    0,   0,  0,   0,   1], # 5
              ])
b=numpy.array([0,0,0,0,1,1])
# solve ax=b
x = numpy.linalg.solve(a, b)
print x

编辑，这是以编程方式构造矩阵的代码，仅针对 n=4 进行了测试!

n = 4

# construct a
diag = [-1]*n + [1]*2
lowdiag = [0.5]*(n-1) + [0]*2
updiag = [0.5]*n
a=numpy.diag(diag) + numpy.diag(lowdiag, -1) + numpy.diag(updiag, 2)

# solve ax=b
b=numpy.array([0]*n + [1]*2)
x = numpy.linalg.solve(a, b)

print a
print x[:n]

这输出

[[-1.   0.   0.5  0.   0.   0. ]
 [ 0.5 -1.   0.   0.5  0.   0. ]
 [ 0.   0.5 -1.   0.   0.5  0. ]
 [ 0.   0.   0.5 -1.   0.   0.5]
 [ 0.   0.   0.   0.   1.   0. ]
 [ 0.   0.   0.   0.   0.   1. ]]
[ 0.41666667  0.66666667  0.83333333  0.91666667]

与您在问题下的评论中的解决方案相匹配。