Tribonacci系列 [英] Tribonacci series

问题描述

可能重复：
  递推关系

如何找到第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＆GT; = 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^th power using exponentiation by repeated squaring in O(log n) steps.

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