Python 3.3如何將此遞歸函數轉換爲純循環版本？

Question

我的問題來自河內的一個變種，它有四座塔樓。

我知道this article其中說，在C++中，你可以將任何遞歸函數轉換爲循環，但我只熟悉Python。我試圖讀取十條規則，但關鍵字struct和stack意味着什麼？

因此，任何與上面的C++類似的文章或討論python也非常值得讚賞。謝謝。

---

原始遞歸函數是fmove（保持另一遞歸函數tmove），接收的整數，返回對的元組。這是優雅的，但沒用（嘗試tmove(100)並小心你的記憶）。

我想將它轉換爲純循環版本，所以即使n變得像100或1000一樣大，我仍然可以知道元組的前10對或100對是什麼。

def memory(function): 
    """ 
    This is a decorator to help raw recursion 
    functions to avoid repetitive calculation. 
    """ 
    cache = {} 
    def memofunc(*nkw,**kw): 
     key=str(nkw)+str(kw) 
     if key not in cache:    
      cache[key] = function(*nkw,**kw) 
     return cache[key] 
    return memofunc 

@memory 
def tmove(n, a=0, b=1, c=2): 
    "int n -> a tuple of pairs" 
    if n==1: 
     return ((a,c),) 
    return tmove(n-1,a,c,b)+\ 
      ((a,c),)+\ 
      tmove(n-1,b,a,c) 

@memory   
def fmove(n,a=0,b=1,c=2,d=3): 
    "int n -> a tuple of pairs" 
    if n==1: 
     return ((a,d),) 
    return min(
     (
      fmove(n-i,a,d,b,c) + 
      tmove(i,a,b,d) + 
      fmove(n-i,c,b,a,d) 
      for i in range(1,n) 
     ), 
     key=len,) 

隨着user2357112的this question的幫助下，我知道如何遞歸函數轉換像tmove - 回報復發（...）+缺點或另一個呼叫+ RECUR（...），但是當情況變得像fmove更復雜，我不知道如何設計結構， - i與n有關，它在不同的堆棧中是不同的，最後你必須使用min來獲得最小尺寸的元組作爲正確的輸出。當前的堆棧。

這是我嘗試（核心算法best(n)仍然是遞歸函數）：

@memory   
def _best(n): 
    if n==1: 
     return 1,1 
    return min(
     (
      (i, 2*(_best(n-i)[1])+2**i-1) 
      for i in range(1,n) 
     ), 
     key=lambda x:x[1], 
    ) 

def best(n): 
    return _best(n)[0] 

def xtmove(n,a=0,b=1,c=2): 
    stack = [(True,n,a,b,c)] 
    while stack: 
     tag,n,a,b,c = stack.pop() 
     if n==1: 
      yield a,c 
     elif tag: 
      stack.append((False,n,a,b,c)) 
      stack.append((True,n-1,a,c,b)) 
     else: 
      yield a,c 
      stack.append((True,n-1,b,a,c)) 

def xfmove(n,a=0,b=1,c=2,d=3): 
    stack = [(True,n,a,b,c,d)] 
    while stack: 
     is_four,n,a,b,c,d = stack.pop() 
     if n==1 and is_four: 
      yield a,d 
     elif is_four: 
      # here I use a none-tail-recursion function 'best' 
      # to get the best i, so the core is still not explicit stack. 
      i = best(n) 
      stack.append((True,n-i,c,b,a,d)) 
      stack.append((False,i,a,b,d,None)) 
      stack.append((True,n-i,a,d,b,c)) 
     else: 
      for t in xtmove(n,a,b,c): 
       yield t 

這是測試代碼。確保你可以通過它。

if __name__=='__main__': 
    MAX_TEST_NUM = 20 
    is_passed = all((
       fmove(test_num) == tuple(xfmove(test_num)) 
       for test_num in range(1,MAX_TEST_NUM) 
      )) 
    assert is_passed, "Doesn't pass the test." 
    print("Pass the test!") 

Answer 1

fmove執行min在其遞歸調用的所有值，並調用tmove所以不可能有在這種情況下，結果流。您需要完成100％的電話才能獲得min的結果。

關於堆棧方法，它創建了一個包含2個操作碼的最小解釋器，True和False。 :)

看看tmove如何在沒有生成器的語言中重複使用不需要重複使用的古老技術的結果。

from itertools import chain 

def xtmove(n, a=0, b=1, c=2): 
    "int n -> a tuple of pairs" 
    if n==1: 
     yield (a,c) 
    else: 
     for i in chain(xtmove(n-1,a,c,b), [(a,c)], xtmove(n-1,b,a,c)): 
      yield i 

Answer 2

經過幾天的學習，在C++文章的幫助下，我終於得到了自己的純循環版本。我認爲@Javier是對的 - 這是不可能的。

def best(n): 
    """ 
    n -> best_cut_number 
    four-towers Hanoi best cut number for n disks. 
    """ 
    stacks = [(0,n,[],None,)] #(stg,n,possible,choice) 
    cache={1:(1,0)} 
    while stacks: 
     stg,n,possible,choice=stacks.pop() 
     if n in cache: 
      res = cache[n] 
     elif stg==0: 
      stacks.append((1,n,possible,n-1)) 
      stacks.append((0,1,[],None)) 
     else: 
      value = 2*res[0] + 2**choice-1 
      possible.append((value,choice)) 
      if choice > 1: 
       stacks.append((1,n,possible,choice-1)) 
       stacks.append((0,n-choice+1,[],None)) 
      else: 
       res = min(possible,key=lambda x:x[0]) 
       cache[n] = res 
    best_cut_number = res[1] 
    return best_cut_number