Skip to main content
 首页 » 编程设计

python之在 Python 上使用 Memoization 计算一个简单的 'ATM'

2025年02月15日12txw1958

我创建了一个接收(amount, bills, n) 的代码。 bills 是可用现金账单的元组,n 是您必须准确使用账单才能收到金额的次数。

例如:

atm_rec ( 70 (5,10) 7 )=True

和:

atm_rec ( 10 (2,3,5) 6 )=False

我使用递归创建了以下代码

def atm_rec(amount, bills, n): 
if amount==0: 
    if n==0: 
        return True 
    else: 
        return False 
elif amount<0: 
    return False 
elif len(bills)==0 and amount!=0: 
    return False 
else: 
    tmp = atm_rec(amount - bills[-1],bills,n-1) 
    tmp2 = atm_rec(amount,bills[0:-1], n) 
    return tmp or tmp2 

现在我想通过使用内存来提高效率(dict 键是 amount 和 n 的元组,值是 bool 值)但不知何故代码更滞后.有什么建议吗?

def atm_mem(amount, bills, n,memo = None): 
if amount==0: 
    if n==0: 
        return True 
    else: 
        return False 
elif amount<0: 
    return False 
elif len(bills)==0 and amount!=0: 
    return False 
if memo==None: 
    memo={} 
key = (amount, n)   
if memo is not None and key not in memo: 
    tmp = atm_mem(amount - bills[-1], bills, n - 1, memo) 
    tmp2 = atm_mem(amount, bills[0:-1], n, memo) 
    memo[key] = tmp or tmp2 
return memo[key] 

请您参考如下方法:

问题是您没有使用memo 缓存。这:

if memo is not None: 
    tmp = atm_mem(amount - bills[-1],bills,n-1,memo) 
    tmp2 = atm_mem(amount,bills[0:-1], n, memo) 
    memo[(amount,n)]=tmp or tmp2 

无论何时设置 memo 都会执行。

您必须通过检查 memo 是否包含您的 key 来避免计算,如下所示:

key = (amount,n)  # compute tuple only once 
if memo is not None and key not in memo: 
    tmp = atm_mem(amount - bills[-1],bills,n-1,memo) 
    tmp2 = atm_mem(amount,bills[0:-1], n, memo) 
    memo[key]=tmp or tmp2 
return memo[key] 

所以当(amount,n)已经被计算出来时,你不需要输入if,只是发出预计算的结果。