SPOJ - ACODE - 在Python NZEC錯誤3

Question

我剛剛發現SPOJ網站，我提出我的第一個解決問題的辦法：Alphacode http://www.spoj.com/problems/ACODE/

在線法官報以NZEC錯誤與下面的代碼，我不不明白爲什麼。我選擇了Python 3.2.3（functools.lru_cache出現在Python3.2中），我也嘗試刪除lru_cache並將其替換爲memoize修飾器，但同樣的問題。

from functools import lru_cache 

@lru_cache(maxsize=10000) 
def acode(s, i=0): 
    if i == len(s): 
     return 1 
    if s[i] == "0": 
     return 0 
    res = acode(s, i+1) 
    if i + 1 < len(s) and (10 * int(s[i]) + int(s[i+1]) <= 26): 
     res += acode(s, i+2) 
    return res 

def main(): 
    i = input().strip() 
    while i != "0": 
     print(acode(i)) 
     i = input().strip() 

if __name__ == "__main__": 
    import sys 
    try: 
     main() 
    except: 
     sys.exit(0) 

您可以使用此命令測試：

$ echo "123\n1111\n21\n0" | python3 acode.py 

注：SPOJ網站上，但我找不到輸出日誌我也沒有「：除了嘗試」提交。

Answer 1

你的程序似乎沒有給NZEC（至少現在）。但是，它與WA代碼保釋。但採用LRU緩存，如果我用動態規劃明確滾下陣列，代替

它被接受

from functools import lru_cache 


@lru_cache(maxsize=10000) 
def acode(s, i=0): 
    if i == len(s): 
     return 1 
    if s[i] == "0": 
     return 0 
    res = acode(s, i + 1) 
    if i + 1 < len(s) and (10 * int(s[i]) + int(s[i + 1]) ≤ 26): 
     res += acode(s, i + 2) 
    return res 


def acode_second_try(s): 
    n = len(s) 
    f = [0 for i in range(1 + n)] 
    f[n] = 1 
    for i in range(n - 1, -1, -1): 
     if s[i] != '0': 
      f[i] = f[1 + i] 
      if 1 + i < n: 
       if 10 * int(s[i]) + int(s[1 + i]) ≤ 26: 
        f[i] += f[2 + i] 
    return f[0] 


def main(): 
    i = input().strip() 
    while i[0] != '0': 
     print(acode_second_try(i)) 
     #print(acode(i)) 
     i = input().strip() 

if __name__ == "__main__": 
    import sys 

    try: 
     main() 
    except: 
     sys.exit(0)

Answer 2

你得到了NZEC錯誤，因爲Python運行時的最大遞歸深度超標。