算法

Question

当k= 2时，我们都知道fibonacci级数。

即：1,1,2,3,5,8,13

但这是2-斐波纳契。就像这样，我能数到第三个斐波纳契：

1,1,2,4,7,13,24

4-斐波纳契：

1,1,2,4,8,15,29

...and就这样继续

我想问的是一个算法来计算一个k-斐波那契级数中的'n‘元素。

像这样:如果我要求fibonacci(n=5,k=4)，结果应该是：8，即4-fibonacci系列中的第五个元素。

我在任何地方都没找到。需要帮助的资源可能是数学世界

有没有人？如果你知道蟒蛇我更喜欢。但如果没有，任何语言或算法都能有所帮助。

提示:让我们分析级数，其中k将从1到5。

k    fibonacci series

1    1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, ...
2    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3    1, 1, 2, 4, 7, 13, 24, 44, 81, ...
4    1, 1, 2, 4, 8, 15, 29, 56, 108, ...
5    1, 1, 2, 4, 8, 16, 31, 61, 120, ...

通过分析，我们可以看到，级数上的数组0:k等于以前的斐波纳契级数，并且一直延续到k=1。

也就是说(我试着展示，但我没有找到正确的方式说)：

k    fibonacci series

1    1, 
2    1, 1, 
3    1, 1, 2, 
4    1, 1, 2, 4, 
5    1, 1, 2, 4, 8, 

希望我能帮你解决这个问题。

python中的解决方案(如果有人需要的话)

class Fibonacci:

    def __init__(self, k):
        self.cache = []
        self.k = k

        #Bootstrap the cache
        self.cache.append(1)
        for i in range(1,k+1):
            self.cache.append(1 << (i-1))

    def fib(self, n):
        #Extend cache until it includes value for n.
        #(If we've already computed a value for n, we won't loop at all.)
        for i in range(len(self.cache), n+1):
            self.cache.append(2 * self.cache[i-1] - self.cache[i-self.k-1])

        return self.cache[n]


#example for k = 5
if __name__ == '__main__':
    k = 5
    f = Fibonacci(k)
    for i in range(10):
        print f.fib(i),

Answer 1

下面是基于琥珀回答的迭代解决方案构建

class Fibonacci {

    List<Integer> cache = new ArrayList<Integer>();
    final int K;

    public Fibonacci(int k) {
        this.K = k;

        // Bootstrap the cache
        cache.add(1);
        for (int i = 1; i <= k; i++)
            cache.add(1 << (i-1));
    }

    public long fib(int n) {

        // Extend cache until it includes value for n.
        // (If we've already computed a value for n, we won't loop at all.)
        for (int i = cache.size(); i <= n; i++)
            cache.add(2 * cache.get(i-1) - cache.get(i-K-1));

        // Return cached value.
        return cache.get(n);
    }
}

测试结果如下：

public class Main {
    public static void main(String[] args) {
        System.out.println("k     fibonacci series");

        for (int k = 1; k <= 5; k++) {
            System.out.print(k + "     ");

            Fibonacci f = new Fibonacci(k);
            for (int i = 0; i < 10; i++)
                System.out.print(f.fib(i) + ", ");
            System.out.println("...");

        }
    }
}

和指纹

k     fibonacci series
1     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
2     1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3     1, 1, 2, 4, 7, 13, 24, 44, 81, 149, ...
4     1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ...
5     1, 1, 2, 4, 8, 16, 31, 61, 120, 236, ...

Answer 2

与2-fibonacci一样，动态规划是可行的。记住早期k的值，以便在O(n)时间内快速计算后面的值。

另一个可以用来提高k大值的速度的优化是通过f(n-1)添加f(n-k)以获得f(n)，而只是使用(2*f(n-1)) - f(n-k-1)。因为它只使用两个查找、两个添加和一个乘法，所以它比k查找要好得多，当k变大时，k会添加(但它仍然是O(n)，只是一个更小的常数乘数)。

Answer 3

如果您只想求解一个值(即fibonnaci(n,k))，那么更有效的方法是使用线性递归，即O(k^3 log(n)) (可以用更好的矩阵乘法算法改进k^3因子)。

基本上，它的工作方式是将向量F(n), F(n-1) ... F(n-k)表示为矩阵乘以向量F(n-1), F(n-2) ... F(n-k-1)。然后，由于矩阵乘法是相联的，所以可以将矩阵提升到幂，并将其乘以一个初始向量F(k), F(k-1) ... F(0)。

在O(log(n))中，可以通过平方进行指数运算。

例如，对于k=3案例，我们将拥有：

[F(n+2)]   [1 1 1] [F(n+1)]
[F(n+1)] = [1 0 0] [F(n)  ]
[F(n)  ]   [0 1 0] [F(n-1)]

所以要解F(n)，你只要找到

[F(n+2)]   [1 1 1]^n [F(2)]
[F(n+1)] = [1 0 0]   [F(1)]
[F(n)  ]   [0 1 0]   [F(0)]