几天来我一直在为这个问题而苦苦挣扎,我对 Python 和更多数学密集型编码仍然是新手,所以任何帮助将不胜感激,只要指出正确的方向:)
所以问题是这样的:
You have a movie pass which is valid for N days. You can use it in any way you want except for 3 consecutive days or more.
So basically, you can either use your pass on a given day or choose to not, meaning 2 raised to N total possibilities. The valid ways for claiming the pass are then 2 raised to N - invalidCases
You have to find the number of valid cases % (10^9+7)
我发现无效案例的递归关系看起来像
invalidCases(at_N) = 2^(n-4) + 2*invalidCases(at_N-1) - invalidCases(at_n-4)
所以我的第一 react 是简单地使用递归:
def invalidCases(n):
if(n<3):
return 0;
elif(n==3):
return 1;
else:
return 2**(n-4)+ 2*invalidCases(n-1)- invalidCases(n-4)
效率很低,但我的等式似乎是正确的。 我的下一次尝试,我尝试了内存,但我一直在 N=1006 处遇到错误。 所以我改变了递归限制。
我目前的尝试(使用内存和增加递归限制)
import sys
sys.setrecursionlimit(10**6)
T=int(input());
#2**(n-4) + 2*ans(n-1)-ans(n-4)
memo={0:0,1:0,2:0,3:1,4:3,5:8,6:20,7:47} #
def ans(n):
#complete this function
if n not in memo:
memo[n]=(2**(n-4) + 2*ans(n-1)-ans(n-4));
return memo[n];
modulo = 10**9 + 7;
print((2**n-ans(n))%modulo);
最后,我的问题。 我需要此代码才能为 n = 999999 工作。
如何将最坏的情况降到最低? 任何指示或提示都会很棒。
最佳答案
这是一个完整的解决方案,它基于以下观察:三天或更长时间的有效解决方案必须从以下之一开始:
0
10
110
其中 1 表示当天使用了通行证,0 表示未使用。
第一种形式有有效的(n-1)种可能性,第二种形式有有效的(n-2)种可能性,第三种形式有有效的(n-3)种可能性。
那么递归就是:
valid(n) = valid(n-1) + valid(n-2) + valid(n-3)
基本情况是 valid(0) = 1、valid(1) = 2 和 valid(2) = 4。重要的是要注意 valid(0) 是 1,而不是零。这是因为当n=0时,只有一个解,即空序列。这不仅在数学上是正确的,而且也是递归正确工作所必需的。
这段代码做了三件事来让它运行得更快:
- 它使用缓存来缓存结果(记忆化),就像您所做的那样。
- 它不存储完整的结果,而是先应用模数,大大缩小取值范围。
- 它预加载缓存,从 0 开始,一直到所需的值。这会将最大递归深度减少到一。
代码如下:
cache = {}
modulus = 10**9 + 7
def valid(n):
if n in cache:
return cache[n]
if n == 0:
v = 1
elif n == 1:
v = 2
elif n == 2:
v = 4
else:
v = valid(n-1) + valid(n-2) + valid(n-3)
v %= modulus
cache[n] = v
return v
def main():
# Preload the cache
for n in range(1000000):
valid(n)
print(valid(999999))
main()
这是输出:
746580045
它在我的系统上运行不到 2 秒。
更新:这是一个最小的迭代解决方案,灵感来自 MFisherKDX 使用的方法。种子值的构建方式消除了对特殊外壳的需求(初始 v2 有效(0)):
modulus = 10**9 + 7
def valid(n):
v0, v1, v2 = 0, 1, 1
for i in range(n):
v0, v1, v2 = v1, v2, (v0 + v1 + v2) % modulus
return v2
print(valid(999999))
此解决方案可能会尽可能快。它会在使用后丢弃中间结果,如果您只调用该函数一次,这很好。
关于python - 如何在代码中更好地实现递归关系?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46837378/