遞歸關係的一般公式？

我解決編碼問題，並發現了下面的關係找到的可能安排的數量：遞歸關係的一般公式？

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）。 –

遞歸關係的一般公式？

回答

相關問題