递归关系的一般公式？

我解决编码问题，并发现了下面的关系找到的可能安排的数量：递归关系的一般公式？

one[1] = two[1] = three[1] = 1

one[i] = two[i-1] + three[i-1]

two[i] = one[i-1] + three[i-1]

three[i] = one[i-1] + two[i-1] + three[i-1]

我能有轻松使用for循环找到直到n，但是n的值是10^9的顺序，并且我将无法从1迭代到如此庞大的数字。

对于n的每个值，我需要在O(1)时间输出值(one[n] + two[n] + three[n]) % 10^9+7。

一些结果：

对于n = 1，结果= 3
对于n = 2，结果= 7
对于n = 3，结果= 17
对于n = 4 ，结果= 41

我花了几个小时在上面找不到n的通用公式。有人可以帮我吗。

编辑：

n = 1, result(1) = 3 
n = 2, result(2) = 7 
n = 3, result(3) = result(2)*2 + result(1) = 17 
n = 4, result(4) = result(3)*2 + result(2) = 41

所以，result(n) = result(n-1)*2 + result(n-2)或 T(n) = 2T(n-1) + T(n-2)

来源

2016-11-27 User_Targaryen

你试过纸，铅笔和一些代数吗？ – FDavidov

是的..尝试铅笔纸找出一个模式。找不到它。尽管代数不太好 –

嗯，我可以告诉你，乍一看，这看起来不难看出。不幸的是，我没有时间参与其中。再试一次，这一次更难。 – FDavidov

你可以用一个矩阵来表示递推关系。（我已更名为one,two,three至a,b,c）。

(a[n+1]) = (0 1 1) (a[n]) 
(b[n+1]) (1 0 1) (b[n]) 
(c[n+1]) (1 1 1) (c[n])

借助这种表示，这是可行的计算值大n，通过矩阵求幂（模数的大量），使用求幂的平方。这会给你O（log n）时间的结果。

(a[n]) = (0 1 1)^(n-1) (1) 
(b[n]) (1 0 1)  (1) 
(c[n]) (1 1 1)  (1)

下面是一些Python从无到有全部实现了这个：

# compute a*b mod K where a and b are square matrices of the same size 
def mmul(a, b, K): 
    n = len(a) 
    return [ 
     [sum(a[i][k] * b[k][j] for k in xrange(n)) % K for j in xrange(n)] 
     for i in xrange(n)] 

# compute a^n mod K where a is a square matrix 
def mpow(a, n, K): 
    if n == 0: return [[i == j for i in xrange(len(a))] for j in xrange(len(a))] 
    if n % 2: return mmul(mpow(a, n-1, K), a, K) 
    a2 = mpow(a, n//2, K) 
    return mmul(a2, a2, K) 

M = [[0, 1, 1], [1, 0, 1], [1, 1, 1]] 

def f(n): 
    K = 10**9+7 
    return sum(sum(a) for a in mpow(M, n-1, K)) % K 

print f(1), f(2), f(3), f(4) 
print f(10 ** 9)

输出：

3 7 17 41 
999999966

它运行有效的瞬间，即使是N = 10 ** 9的情况下。

来源

2016-11-27 13:57:49

这是用于快速计算递归关系的标准技巧（例如：Fibonacci）。 –

递归关系的一般公式？

回答

相关问题