尝试使用递归将帕斯卡三角生成为元组

Question

我需要编写一个函数来使用递归将帕斯卡三角生成为元组。

e.g pascal(5)   
((1,), (1, 1), (1, 2, 1), (1, 3, 3, 1), (1, 4, 6, 4, 1))

我可以使用以下函数将其生成为列表：

def triangle(n):
    if n == 0:
        return []
    elif n == 1:
        return [[1]]
    else:
        new_row = [1]
        result = triangle(n-1)
        last_row = result[-1]
        for i in range(len(last_row)-1):
            new_row.append(last_row[i] + last_row[i+1])
        new_row += [1]
        result.append(new_row)
    return result

我试过将其更改为元组：

def pascal(n):
    if n==0:
        return ()
    elif n==1:
        return ((1,),)
    else:
        new_row = (1,)
        result = pascal(n-1)
        last_row = result[-1]
        print(last_row)
        for i in range(len(last_row)-1):
            new_row = new_row+last_row[i]+last_row[i+1]
        new_row = new_row +(1,)
        result=result+(new_row,)
    return result

但它不起作用，我收到错误 len(last_row)-1 type int has no len。

我不确定如何修复此代码，如有任何帮助，我将不胜感激。

Answer 1

在您的第一个代码中，只需在 return 之前添加此行即可将 list of lists 转换为 tuple of tuples:

tuple_results = tuple(tuple(x) for x in results)
return tuple_results

Answer 2

我认为问题出在 result = result + new_row 行。

如果您想了解原因，请将鼠标悬停在下方...

result 是元组的元组，new_row 是数字的元组。如果您将数字元组添加到元组元组，您将以元组 and 数字结束！例如 ((1,), 1) 这不是你想要的。通过 result = result + (new_row,)
修复它

Answer 3

注意

不要把它交作业。你的老师会（正确地）认为你是从网上抄袭的。主要是为了学习它的紧凑程度，即专业 Python 程序员如何编写它。

这里是简短的 8 行版本：

def pascal(n):
    if n <= 0:
        return ()
    elif n == 1:
        return ((1,),)
    else:
        res = pascal(n - 1) # recursive call
        return (*res, (1, *[n + i for n, i in zip(res[-1], res[-1][1:])], 1))    
print(pascal(5))

在这种情况下，您的代码中缺少的部分是展开运算符。它所做的是从递归调用中解压缩元组的元组，您将其添加到下一行。

这很密集，所以让我们稍微解压一下：

return (*res, # open paren starts new tuple, *res unpacks the recursive call
    (1, # starts the tuple for the current row
      *[ # spread the result of the list comprehension
          n + i for n, i in # we're going to add the items in two lists
          zip( # here's where we combine the two lists to add
              res[-1], # last row of recursive call
              res[-1][1:] # same but shifted 1 index
          ),
       ], # end list comprehension
     1) # 1 to end the current row
  ) # end the total result, i.e. tuple of rows

之所以可行，是因为 zip 如何处理不同长度的列表。例如，如果最后一行是 (1,3,3,1)，那么我们会得到 zip((1,3,3,1),(3,3,1))，也就是 ((1,3), (3,3), (3,1))。然后我们将推导中成对的数字相加得到(4,6,4)。处理那些，然后是下一行。

尝试使用递归将帕斯卡三角生成为元组

Attempting to generate Pascal's Triangle as a tuple using recursion

python

list

recursion

tuples

pascals-triangle

注意