我被要求为带有元组的帕斯卡三角形编写递归。 这是我的代码:
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
如何修复此错误?
以下内容将起作用。在上一行上从 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 个元素是由循环中适当的和形成的,因此是范围。