記憶錢幣變化

我想將我的硬幣更改功能轉換爲記憶功能
要做到這一點，我決定使用字典，以便我的字典中的鍵將是硬幣，並且值將是包含所有可以改變「鑰匙」硬幣的硬幣。
我所做的是：
記憶錢幣變化

def change(a,kinds=(50,20,10,5,1)): 
    if(a==0): 
      return 1 
    if(a<0 or len(kinds)==0): 
      return 0 

    return change(a-kinds[0],kinds)+change(a,kinds[1:]) 


def memoizeChange(f): 
    cache={} 
    def memo(a,kinds=(50,20,10,5,1)): 

     if len(cache)>0 and kinds in cache[a]: 
      return 1 
     else: 
      if(f(a,kinds)==1): 
       cache[a]=kinds // or maybe cache[a].append(..) 
       return cache[a]+memo(a-kinds[0],kinds)+memo(a,kinds[1:]) 
    return memo 

memC=memoizeChange(change) 
kinds=(50,20,10,5,1) 
print(memC(10,kinds))

我希望得到一些建議，也許有另一種方式來做到這一點。
謝謝。

編輯
Memoized版本：0

def change(a,kinds=(50,20,10,5,1)): 
    if(a==0): 
      return 1 
    if(a<0 or len(kinds)==0): 
      return 0 
    return change(a-kinds[0],kinds)+change(a,kinds[1:]) 


def memoizeChange(f): 
    cache={} 
    def memo(a,kinds=(50,20,10,5,1)): 
     if not (a,kinds) in cache: 
       cache[(a,kinds)]=f(a,kinds) 
     return cache[(a,kinds)] 
    return memo 

change=memoizeChange(change) 
print(change(10))

來源

2013-12-23 Ofir Attia

可能重複[有一個裝飾簡單地緩存函數返回值？（http://stackoverflow.com/questions/815110/is -there-A-裝飾到簡單的緩存功能回-v api） – perreal

由於您正在遞歸地調用函數，因此可以考慮將memoization注入到函數本身中，並遞歸地調用memoized函數，這樣您就可以在請求新值時重用現有的memoized函數結果。 –

@perreal「複製」它的罰款來理解它的想法，我面臨的是如何保存重複值並避免它的方法。但無論如何感謝。 –

這是沒有必要寫一個專門的記憶裝飾時，你可以只使用一個通用的預先編寫的一個...如從PythonDecoratorLibrary直以下內容：

import collections 
import functools 

class memoized(object): 
    '''Decorator. Caches a function's return value each time it is called. 
    If called later with the same arguments, the cached value is returned 
    (not reevaluated). 
    ''' 
    def __init__(self, func): 
     self.func = func 
     self.cache = {} 
    def __call__(self, *args): 
     if not isinstance(args, collections.Hashable): 
     # uncacheable. a list, for instance. 
     # better to not cache than blow up. 
     return self.func(*args) 
     if args in self.cache: 
     return self.cache[args] 
     else: 
     value = self.func(*args) 
     self.cache[args] = value 
     return value 
    def __repr__(self): 
     '''Return the function's docstring.''' 
     return self.func.__doc__ 
    def __get__(self, obj, objtype): 
     '''Support instance methods.''' 
     return functools.partial(self.__call__, obj)

然後，您可以將其應用到您的change()函數（或任何其他的，因爲它是通用的）這樣的：

@memoized 
def change(a, kinds=(50, 20, 10, 5, 1)): 
    if a == 0: 
     return 1 
    if a < 0 or len(kinds) == 0: 
     return 0 

    return change(a - kinds[0], kinds) + change(a, kinds[1:]) 

print(change(10)) # 4

的

來源

2013-12-23 14:17:20 martineau

好的，謝謝，順便說一句，我不知道我可以使用它，但在你回答我成功之前，看編輯 –

是的，將結果分配給原始函數的名稱是@decorator語法爲你做的 - 所以通常意味着您不必將所有現有的調用更改爲使用具有不同名稱的修改版本。 – martineau

它不回答你的問題問的，但如果R [0]至R [I]是的數用你的第一個k面值作出改變的方法，那麼r [i + 1]是用第一k-1面值加r [ik]進行改變的方法的數量。這導致了一個優雅的解決你解決這個問題：

def change(total, denominations): 
    r = [1] + [0] * total 
    for k in denominations: 
     for i in xrange(k, len(r)): 
      r[i] += r[i - k] 
    return r[total] 

print change(100, (50, 20, 10, 5, 1))

這種方法在波利亞的書「如何解決這個問題」的討論。一般來說，使用memoisation來改進遞歸解決方案是使用Python編寫動態編程解決方案的一種簡單方法，但我個人認爲，能夠降低關卡並準確計算如何在Python中構建中間結果是一項重要技能一個動態編程解決方案中的表格。通常（並在此例示），結果更快且更易於閱讀（儘管首先編碼更難）。

來源

2013-12-23 12:38:36

+1在另一種方式，很高興知道更多。 –

記憶錢幣變化

回答

相關問題