递归关系的通用公式？ [英] General formula for a recurrence relation?

问题描述

我正在解决一个编码问题，并发现以下关系以找到可能的排列数量：

I was solving a coding question, and found out the following relation to find the number of possible arrangements:

one [1] =两个[1] =三个[1] = 1

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

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

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

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

I could have easily used a for loop to find out the values of the individual arrays till n, but the value of n is of the order 10^9, and I won't be able to iterate from 1 to such a huge number.

对于每个 n 的值，我需要输出的值（一个[n] +两个[n] +三个[n]） ％10 ^ 9 + 7 在 O（1）时间内。

For every value of n, I need to output the value of (one[n] + two[n] + three[n]) % 10^9+7 in O(1) time.

某些结果：

• 对于n = 1，结果= 3


• 对于n = 2，结果= 7


• 对于n = 3，结果= 17


• 对于n = 4 ，结果= 41

• For n = 1, result = 3
• For n = 2, result = 7
• For n = 3, result = 17
• For n = 4, result = 41

我无法找到 n 在上面花了几个小时之后。有人可以帮我吗？

I was not able to find out a general formula for n for the above after spending hours on it. Can someone help me out.

编辑：

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）=结果（n-1）* 2 +结果（n-2）或
T（n）= 2T（n-1）+ T（n-2）

推荐答案

您可以使用矩阵来表示递归关系。 （我将一个，两个，三个重命名为 a ， b ， c ）。

You can use a matrix to represent the recurrence relation. (I've renamed one, two, three to 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）时间的结果。

With this representation, it's feasible to compute values for large n, by matrix exponentation (modulo your large number), using exponentation by squaring. That'll give you the result in O(log n) time.

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

以下是一些从头实现这些功能的Python：

Here's some Python that implements this all from scratch:

# 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，它也可以立即有效运行。

It runs effectively instantly, even for the n=10**9 case.

这篇关于递归关系的通用公式？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！