k-Fibonacci的算法

Question

当k = 2时,我们都知道斐波那契数列.

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

但这是2-fibonacci.像这样,我可以算第三个斐波那契:

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

而4-fibonacci:

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

......等等

我要问的是计算k-fibonacci系列中'n'元素的算法.

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

我没有在任何网站找到它.帮助的资源可能是mathworld

任何人？如果你知道python,我更喜欢.但如果没有,任何语言或算法都可以提供帮助.

提示我认为这可以帮助:让我们分析k-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, ...

分析这一点,我们可以看到k-fibonacci系列上的数组[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

与2-fibonacci一样,动态编程是最佳选择.记住早期ks 的值,以便及时快速计算后面的值O(n).

另一种优化,你可以用它来提高速度的较大值k是不是增加f(n-k)通过f(n-1)获得f(n),而不是仅仅使用(2*f(n-1)) - f(n-k-1).由于这仅使用2次查找,2次添加和乘法,因此它比k查找要大得多,并且k当k变大时会增加(但它仍然O(n)只是一个较小的常数乘数).

Answer 2

这是一个基于Ambers答案的迭代解决方案:

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 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)]