时间戳

首页 > 解决方案 > 在使用记忆化和递归时，如何改进计算帕斯卡三角形第 N 行的代码？

python - 在使用记忆化和递归时，如何改进计算帕斯卡三角形第 N 行的代码？

问题描述

我一直在修改递归并决定用它来计算帕斯卡三角形的行。我已经成功创建了一个生成 Pascals 三角形的函数，该函数适用于 n <= 7，但它的效率非常低。我知道生成帕斯卡三角的身份，但我对此并不感兴趣。我想要一些指导来改进下面的代码。

在大约 n = 7 之后，计算需要很长时间，这让我认为我的记忆实现错误。

count = 0 
def Pascal(n):
    global count
    count += 1 
    pasc_list = [] 
    i = 0 
    j = i+1
    dictionary = {0:[1],1:[1,1]}

    if n in dictionary:
        return dictionary[n]
    else:
        pasc_list.append(1)
        while j < len(Pascal(n-1)):
            pasc_list.append(Pascal(n-1)[i] + Pascal(n-1)[j])
            i += 1 
            j = i + 1 
        pasc_list.append(1)
        dictionary[n] = pasc_list
    return pasc_list
a = Pascal(5)
print(a)
print(count)

对于 n = 5，作用域的数量已经是 4694，当 n = 6 时，作用域的数量是 75105，这是一个显着的增加。因此，如果有人可以帮助我降低制造范围的速度，我将不胜感激！

标签： pythonrecursionmemoization

解决方案

要在 Python 中正确使用 memoization，请使用可变的默认参数，通常命名为memo：

count = 0 

def Pascal(n, memo={0:[1],1:[1,1]}):
    global count
    count += 1 

    pasc_list = [] 
    i = 0 
    j = i+1

    if n in memo:
        return memo[n]

    else:
        pasc_list.append(1)
        while j < len(Pascal(n-1)):
            pasc_list.append(Pascal(n-1)[i] + Pascal(n-1)[j])
            i += 1 
            j = i+1 

        pasc_list.append(1)
        memo[n] = pasc_list

    return pasc_list

a = Pascal(7)
print(a)
print(count)

输出：

c:\srv\tmp> python pascal.py
[1, 7, 21, 35, 35, 21, 7, 1]
70

您还应该将 memoization 返回作为您的函数执行的第一件事：

def Pascal(n, memo={0:[1],1:[1,1]}):
    if n in memo:
        return memo[n]

    global count
    count += 1 

    pasc_list = [] 
    i = 0 
    j = i+1

    pasc_list.append(1)
    while j < len(Pascal(n-1)):
        pasc_list.append(Pascal(n-1)[i] + Pascal(n-1)[j])
        i += 1 
        j = i+1 

    pasc_list.append(1)
    memo[n] = pasc_list

    return pasc_list

输出：

c:\srv\tmp> python pascal.py
[1, 7, 21, 35, 35, 21, 7, 1]
6

推荐阅读