14

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

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

但这是 2-斐波那契。像这样，我可以算出第三个斐波那契：

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

和 4 斐波那契：

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

...等等继续

我要问的是一种算法来计算 k-fibonacci 系列中的“n”元素。

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

我没有在任何网络上找到它。可以帮助的资源可能是数学世界

任何人？如果你知道 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-fibonacci数列上的数组[0:k]等于前面的fibonacci数列，一直持续到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),
4

10 回答 10

9

与 2-fibonacci 一样，动态规划是要走的路。记住早期ks 的值，以便及时快速计算后面的值O(n)。

您可以使用另一个优化来提高大值的速度，k而不是添加f(n-k)throughf(n-1)来获取f(n)，而不是只使用(2*f(n-1)) - f(n-k-1). 由于这只使用 2 次查找、2 次加法和一次乘法，因此它比k查找和k加法要大得多k（但它仍然是O(n)，只是一个较小的常数乘数）。

于 2010-11-08T08:46:31.613 回答
7

这是一个基于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, ...
于 2010-11-08T08:58:37.050 回答
7

如果您只想求解一个值（即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)]
于 2010-11-08T09:47:59.813 回答
3

直接的方法是简单地将最后 k 个术语相加，每次都得到当前术语。这给了我们一个 O(n*k) 的运行时间。

另一种方法是使用矩阵求幂。对于 k=2，您可以使用矩阵对情况进行建模。从 (Fn-1, Fn-2) 我们可以通过计算 (Fn-1+Fn-2,Fn-1) 推导出 (Fn, Fn-1)。

因此，将列矩阵相乘

[
Fn-1
Fn-2
]

与方阵

[
1 1
1 0
]

产量

[
Fn-1 + Fn-2
Fn-1
]

从而给我们 Fn 的值。

当然，这并不比 O(n*k) 更好。我们仍然会运行 O(n) 循环/递归来获得第 n 项。

请注意（为了方便，我现在水平写列向量，但它们仍然是列）

[[Fn],[Fn-1]] = [[Fn-1],[Fn-2]]*[[1,1] [1,0]]
              = [[Fn-2],[Fn-3]]*[[1,1] [1,0]]*[[1,1] [1,0]]
              = [[Fn-3],[Fn-4]]*[[1,1] [1,0]]*[[1,1] [1,0]]*[[1,1] [1,0]]
              = [[Fn-3],[Fn-4]]*([[1,1] [1,0]])^3
              = [[Fn-k],[Fn-k-1]]*([[1,1] [1,0]])^k
              = [[F1],[F0]]*([[1,1] [1,0]])^n-1

现在，([[1,1] [1,0]])^n-1可以使用乘方求幂在 O(log(n)) 时间内计算。因此，您最多可以使用 log(n) 矩阵乘法来计算 k-fibonacci 的第 n 项。使用简单的矩阵乘法，这给了我们 O(k^3*log(n)) 的复杂度。

编辑：

下面是我编写的一些 Python 代码，以更好地说明我所说的内容：

from itertools import izip

def expo(matrix,power, identity):
    if power==0:
        return identity
    elif power==1:
        return matrix
    elif power&1:
        return multiply(matrix,expo(matrix,power-1,identity))
    else:
        x=expo(matrix,power>>1,identity)
        return multiply(x,x)

def multiply(A,B):
    ret=[list() for i in xrange(len(B))]
    for i,row in enumerate(B):
        for j in xrange(len(A[0])):
            coloumn=(r[j] for r in A)
            ret[i].append(vector_multiply(row,coloumn))
    return ret

def vector_multiply(X,Y):
    return sum(a*b for (a,b) in izip(X,Y))

def fibonacci(n,start=[[1],[0]], k=2):
    identity=[[1 if col==row else 0 for col in xrange(k)] for row in xrange(k)] # identity matrix
    # build the matrix for k
    matrix=[[1]*k]
    for i in xrange(1,k):
        matrix.append([0]*(i-1)+[1]+[0]*(k-i))
    return multiply(start,expo(matrix,n-1,identity))[0][0]

print fibonacci(10)
于 2010-11-08T09:43:00.060 回答
1

为了练习它，我在 Haskell 中实现了它。以下是fib通常写成列表推导的方式：

fib = 1:1:[x + y | (x,y) <- zip fib $ tail fib]

推广到“k”项是困难的，因为这zip需要两个参数。有zip3,zip4等但没有一般zipn. 然而，我们可以取消创建对的技术，而是生成“序列的所有尾部”，并对其中的第一个k成员求和。这是 k=2 的情况：

fib2 = 1:1:[sum $ take 2 x | x <- tails fib2]

推广到任何k：

fibk k = fibk'
  where fibk' = take (k - 1) (repeat 0) ++ (1:[sum $ take k x | x <- tails fibk'])


> take 10 $ fibk 2
[0,1,1,2,3,5,8,13,21,34]

> take 10 $ fibk 3
[0,0,1,1,2,4,7,13,24,44]

> take 10 $ fibk 4
[0,0,0,1,1,2,4,8,15,29]
于 2012-06-12T01:08:33.273 回答
1

下面的另一个 log(n) 解决方案。
来源和解释在这里。
如果进行了大量调用，您可以缓存解决方案。

public class Main {
    /* 
     * F(2n) = F(n) * (2*F(n+1) - F(n))
     * F(2n+1) = F(n+1)^2 + F(n)^2
     * Compute up to n = 92, due to long limitation<br>
     * Use different type for larger numbers
     */
    public static long getNthFibonacci(int n) {
        long a = 0;
        long b = 1;
        for (int i = 31 - Integer.numberOfLeadingZeros(n); i >= 0; i--) {

            long d = a * ((b << 1) - a); // F(2n)
            long e = a * a + b * b; // F(2n+1)
            a = d;
            b = e;

            if (((1 << i) & n) != 0) { // advance by one
                long c = a + b;
                a = b;
                b = c;
            }
        }
        return a;
    }
}
于 2013-07-31T00:12:14.300 回答
1

人们已经提到了 O(logN) 解决方案。没有多少人了解求幂矩阵中的常数是如何形成的。如果您想详细分析如何使用矩阵来解决线性递归，请查看Code Overflow。

于 2013-09-01T07:18:22.870 回答
1

这是一个高效、简洁和精确的封闭形式解决方案。

def fibk(n, k):
    A = 2**(n+k+1)
    M = A**k - A**k // (A - 1)
    return pow(A, n+k, M) % A

for k in xrange(1, 10):
    print ', '.join(str(fibk(n, k)) for n in xrange(15))

这是输出：

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610
1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136
1, 1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536
1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930
1, 1, 2, 4, 8, 16, 32, 63, 125, 248, 492, 976, 1936, 3840, 7617
1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936
1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1016, 2028, 4048, 8080
1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144

该方法有效地计算多项式环 Z[X]/(X^kX^(k-1)-X^(k-2)-...-1) 中的 X^(n+k) （其中结果最终多项式中常数项的 fibk(n, k)) 有点令人惊讶，但使用了足够大的整数A而不是整数X来执行计算。

于 2018-01-03T11:11:11.920 回答
0

我猜你需要比O(nk).
对于O(nk)，您可以简单地计算它。如果您在和
上有一个上限，您还可以构建一次矩阵并在需要该值时随时查询。 n <= Nk <= KNxK

编辑
如果你想进一步研究数学，你可以尝试阅读这篇关于广义阶数 - k Pell Numbers的论文。

于 2010-11-08T08:45:14.500 回答
0

简单的蛮力解决方案

    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    int k = scanner.nextInt();
    long formula ;
    formula = k ;


    long[] fib = new long[n+1];

    for (int i = 1; i <=n ; i++) {
        if(i<=k) fib[i]  = 1;
        else {
            fib[i] = formula;
            formula =(formula*2-fib[i-k]);
        }
    }


    for (int i = 1; i <=fib.length-1 ; i++) {
        System.out.print(fib[i]+" ");
    }
于 2018-01-02T18:05:03.947 回答