python - SPOJ - acode - Python 3 中的 NZEC 错误

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

注意：我也提交了没有“try:except:”但我在 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 运行时的最大递归深度。

Answer 3

我有确切的问题！因为我写了几乎完全相同的代码！:P

@rabih-kodeih 是对的，这是因为超出了递归深度。我修复了这个

sys.setrecursionlimit(10**6)

使用该sys库，您可以设置递归限制！

注意：这也有其限制，如果输入值足够高，它也可能超过堆内存。因此，此解决方案适用于 SPOJ 的这个问题，但请谨慎使用。