python - 在 Python 中使用递归元组的 Pascal 三角形

Question

我被要求用元组为帕斯卡三角形写一个递归。这是我的代码:

def pascal(n):
    if n == 1:
        return (1,)
    if n == 2:
        return ((1,),(1,1))
    else:
        new_row = ()
        for i in range(-1, n-1):
            if i == -1:
                new_row = new_row + (1,)
            elif i == n - 1:
                new_row = new_row + (1,)
            else: 
                a = pascal(n-1)[n-2][i] + pascal(n-2)[n-1][i+1]
                new_row = new_row + (a,)
        return pascal(n-1), new_row

如果我调用 pascal(3) 或更高版本，我会收到一个错误，提示元组索引超出范围。

这是跟踪输出:

Traceback (most recent call last):
  File "tup.py", line 19, in <module>
    print pascal(3)
  File "tup.py", line 15, in pascal
    a = pascal(n-1)[n-2][i] + pascal(n-2)[n-1][i+1]
IndexError: tuple index out of range

感谢任何帮助，谢谢!

Answer 1

以下将起作用。在上一行从 0 循环到 n-2(不包括):

def pascal(n):
    if n == 1:  # one base case is enough
        return ((1,),)  # return tuple of tuples to be consistent
    prev = pascal(n-1)
    new_row = [1] + [prev[-1][i]+prev[-1][i+1] for i in range(n-2)] + [1]
    return prev + tuple(new_row)

>>> pascal(2)
((1,), (1, 1))
>>> pascal(3)
((1,), (1, 1), (1, 2, 1))
>>> pascal(4)
((1,), (1, 1), (1, 2, 1), (1, 3, 3, 1))

解释:第 n 行有 n 个元素，其中 2 个为 1。因此 n-2 个元素由循环中的适当求和形成，因此是范围。