我是一名学生,我们的老师要求我们做以下任务(为了方便我将其翻译成英文)
The algorithm for computing the function F(n), where n is a natural number, is given by the following relations:
F(n) = n if n ≥ 10,000,
F(n) = n/4 + F(n / 4 + 2) if n < 10 000 and n is divisible by 4,
F(n) = 1 + F(n + 2) , if n < 10 000 and n is not divisible by 4.
What is the value of the expression F(174) - F(3)?
正确答案:67
他建议我们使用lru_cache进行缓存和更快的递归,但是这种缓存在桌面电脑上不起作用,只能在在线Python解释器上工作
我的代码:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
@lru_cache(None)
def F(n):
if n >= 10000:
return n
elif n % 4 == 0:
return n // 4 + F(n // 4 + 2)
else:
return 1 + F(n + 2)
print(F(174) - F(3))
VS代码: 程序在VScode中运行,输出响应为空 https://i.imgur.com/jZwLZyb.png
如果我注释掉带有缓存的行,那么没有它一切都会工作。麻烦的是,我们已经解决了类似的任务,并且出现了同样的情况 - 你不能没有缓存,但它只适用于在线解释器
最有趣的是,这些任务是为了考试而设计的,当然,无法使用在线口译员。
程序应该在 PC 和在线解释器上输出 67 答案,但只发生在最后一种情况。也许在这个任务中使用缓存没有意义,但我不明白为什么它拒绝工作
您的代码出现段错误。
sys.setrecursionlimit(10**6)
并不意味着您实际上可以递归一百万层深度。这意味着 Python 的安全检查不会阻止您尝试。突破你的 C 堆栈的限制,你就会崩溃。
不同的系统有不同的默认堆栈大小。您可能能够深入到足以让您的代码在您尝试过的在线解释器上取得成功,但在您的 PC 上,您没有足够的堆栈空间。