如何用装饰器实现Tabulation（制表法）求阶乘？附尝试代码求指导

原始制表法阶乘代码 #

你最初实现的制表法阶乘函数逻辑是正确的：

def factorial(n):
    if n<1:
        return 1
    else:
        f=[0]*(n+1)           # 创建存储阶乘结果的数组
        f[0]=1                # 初始化基础值
        for i in range(1,n+1):# 自底向上迭代计算
            f[i]=i*f[i-1]       # 利用前序结果计算当前值
        return f[n]

你的尝试代码问题分析 #

你提供的装饰器尝试存在几个核心问题：

• 参数提取逻辑错误：n=str(args)+str(kwargs)是完全冗余且错误的取参方式，直接通过args[0]就能获取传入的n值
• 缓存逻辑无效：每次调用装饰器内部函数都会重新创建数组m，无法复用之前的计算结果；if n not in m的判断逻辑错误（检查的是n是否为数组元素，而非索引）
• 未实现制表法核心：装饰器没有替换递归逻辑，依然依赖原函数的递归调用，没有做到自底向上的迭代计算
• 局部变量越界访问：全局作用域调用print(m)会报错，因为m是装饰器内部函数的局部变量

修正后的实现方案 #

方案一：带缓存复用的制表法装饰器 #

这个方案会维护全局缓存，避免重复计算，更贴合装饰器的复用特性：

import time

def tabulation(func):
    # 维护缓存字典和已计算的最大n值，实现复用
    cache = {0: 1, 1: 1}
    max_calculated = 1

    def inner(n):
        nonlocal max_calculated
        # 若n已计算过，直接返回缓存值
        if n <= max_calculated:
            return cache[n]
        # 自底向上迭代计算从max_calculated+1到n的所有值
        for i in range(max_calculated + 1, n + 1):
            cache[i] = i * cache[i-1]
        max_calculated = n
        return cache[n]
    return inner

@tabulation
def fact(n):
    # 函数体作为 fallback，实际会被装饰器逻辑覆盖
    if n <= 1:
        return 1
    return n * fact(n-1)

# 测试代码
start = time.time()
f = fact(5)
end = time.time()
print(f, " 耗时:", end - start)

start = time.time()
g = fact(10)
end = time.time()
print(g, " 耗时:", end - start)

# 再次调用已计算过的n，直接取缓存
start = time.time()
h = fact(5)
end = time.time()
print(h, " 耗时:", end - start)

方案二：严格贴合原始制表法的装饰器 #

如果希望装饰器完全复刻你最初的制表法逻辑，可以直接在装饰器内实现迭代计算：

import time

def tabulation(func):
    def inner(n):
        if n < 1:
            return 1
        # 复刻原始制表法的数组创建与填充逻辑
        f = [0] * (n + 1)
        f[0] = 1
        for i in range(1, n + 1):
            f[i] = i * f[i-1]
        return f[n]
    return inner

@tabulation
def fact(n):
    # 原函数体无需执行，装饰器直接返回计算结果
    pass

# 测试代码
start = time.time()
f = fact(5)
end = time.time()
print(f, " 耗时:", end - start)

start = time.time()
g = fact(10)
end = time.time()
print(g, " 耗时:", end - start)

内容的提问来源于stack exchange，提问作者Debopam Das