问题描述
可能重复:
递推关系
如何找到第n个号码中tribonacci系列?我需要和算法足够快的 N
可达10 ^ 15。
How do I find the n:th number in the tribonacci series?I need and algorithm fast enough for n
up to 10^15.
Tribonacci号码被定义为的一(N)=一个第(n-1)+ A(N-2)+ A(N-3)用(0)= 1(1) = 0,一(2)= 1。
Tribonacci numbers are defined as a(n) = a(n-1) + a(n-2) + a(n-3) with a(0)=a(1)=0, a(2)=1.
推荐答案
对于任何序列的线性复发,矩阵幂算法的作品。
For any sequence with a linear recurrence, the matrix exponentiation algorithm works.
如果如该序列具有复发
a[k] = x*a[k-1] + y*a[k-2] + z*a[k-3]
为 K> = 3
和初始值 A [0],A [1],A [2]
,您获得三重(一[N + 2]中,[N + 1]中,[N])
乘以
for k >= 3
and initial values a[0], a[1], a[2]
, you obtain the triple (a[n+2], a[n+1], a[n])
by multiplying
|x y z|^n |a[2]|
|1 0 0| * |a[1]|
|0 1 0| |a[0]|
该矩阵可以提高到n 使用幂反复平方的 O(log n)的
步骤力量。
The matrix can be raised to the n power using exponentiation by repeated squaring in O(log n)
steps.
这篇关于Tribonacci系列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!