k-斐波那契算法

Question

我们都知道 k = 2 时的斐波那契数列。

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

但这是 2-斐波那契数列。像这样，我可以数三次斐波那契:

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

和 4-斐波那契:

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

……等等

我要问的是一种计算 k-斐波那契数列内的“n”元素的算法。

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

我没在网上找到它。提供帮助的资源可能是 mathworld

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

提示我认为这会有所帮助: 让我们分析一下 k-斐波那契数列，其中 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-斐波那契数列上的数组 [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 一样，动态规划是必经之路。记住早期的​​值 k s 快速计算后面的，在 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) ，只是一个较小的常量乘数)。