递推关系 [英] Recurrence Relations

问题描述

如何计算tribonacci号在最佳的复杂性非​​常大的n（比如说10 ^ 14）。 Tribonacci号码被定义为 F（N）= F（N-1）+ F（N-2）+ F（N-3）与 F0 = 1，F1 = 2，F2 = 4 。

How to calculate tribonacci number for very large n ( say 10^14 ) in best complexity. Tribonacci numbers are defined as F(n)=F(n-1)+F(n-2)+F(n-3) with F0=1, F1=2, F2=4.

或复发的定义为 F（N）= AF（N-1）+ BF（N-2）+ CF（N-3）与 F0 = 1，F1 = 2，F2 = 4 。

我要计算在日志中第n项（n）的，就像第n个斐波纳契数。

I want to Calculate nth term in log(n) just like nth Fibonacci number.

如何才能产生相应的矩阵使用矩阵幂来calulate第n 长期？

How can I generate the Base Matrix for using matrix exponentiation to calulate the nth term?

previously我试图用DP来实现，但由于我们不能采取这样大尺寸的工作不细的数组。同样递归没有在这里工作，由于堆栈溢出非常大的数字顺序10 ^ 14。

Previously I was trying to implement it using DP but as we cannot take array of such large size its not working fine. Similarly Recursion didn't work here due to stack overflow for very large numbers of order of 10^14.

推荐答案

在最佳的渐近的tribonacci数字的复杂性将使用矩阵幂方法类似的一个斐波那契数。具体地，正确写入，这是O（log n）的整数运算，而不是为O（n）（如动态规划法）或O-（3 ^N ）（象幼稚溶液）。

The best asymptotic complexity for tribonacci numbers will be using a matrix exponentiation method like the one for Fibonacci numbers. Specifically, written correctly, this is O(log n) integer operations, rather than O(n) (like the dynamic programming method) or O(3ⁿ) (like the naive solution).

感兴趣的矩阵是

    [1, 1, 1]
M = [1, 0, 0]
    [0, 1, 0]

和 N 个tribonacci数在左上角的 M ^N 。矩阵幂必须平方实现的log（n）的复杂性来计算。

and the nth tribonacci number is in the upper left corner of Mⁿ. The matrix exponentiation must be computed by squaring to achieve log(n) complexity.

（对于 F（N + 3）=一F（N + 2）+ B F（N + 1）+ C F（N），矩阵是

    [a, b, c]
M = [1, 0, 0]
    [0, 1, 0]

和结果是数列{F <子> N + 2 F <子> N + 1 F <子> N } = M ^N 数列{F ₂ F ₁ F ₀ }，同样的看到这里。）

and the result is {F_n+2,F_n+1,F_n} = Mⁿ {F₂,F₁,F₀}, also see here.)

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