algorithm - 递归关系的一般公式？

Question

我在解决一个编码问题，并找到了以下关系来找到可能的排列数:

一个[1] = two[1] = three[1] = 1

一个[i] = 二[i-1] + 三[i-1]

二[i] = 一个[i-1] + 三[i-1]

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

我本可以很容易地使用 for 循环 来找出单个数组的值，直到 n，但是 n 的值是10^9 的顺序，我将无法从 1 迭代到这么大的数字。

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

一些结果:

• 对于 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)

Answer 1

可以用矩阵来表示递归关系。 (我已将 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 的情况下，它也能立即有效地运行。