当前位置： 文江博客话题详情

k-斐波那契算法

发布于 2024-10-01 02:36:07 字数 1812 浏览 5 评论 0原文

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

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

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

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

和第四个斐波那契数：

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

...依此类推

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

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

我在网上没有找到它。可以提供帮助的资源是 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),
原文

We all know fibonacci series, when k = 2.

I.e.: 1,1,2,3,5,8,13

But this is the 2-fibonacci. Like this, I can count the third-fibonacci:

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

And the 4-fibonacci:

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

...and so goes on

What I'm asking is an algorithm to calculate an 'n' element inside a k-fibonacci series.

Like this: if I ask for fibonacci(n=5,k=4), the result should be: 8, i.e. the fifth element inside the 4-fibonacci series.

I didn't found it anywhere web. A resouce to help could be mathworld

Anyone? And if you know python, I prefer. But if not, any language or algorithm can help.

Tip I think that can help:
Let's analyze the k-fibonacci series, where k will go from 1 to 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, ...

Analyzing this, we can see that the array [0:k] on the k-fibonacci series is equal to the
previous fibonacci series, and it goes on till the k=1

i.e. (I'll try to show, but I'm not finding the right way to say it):

k    fibonacci series

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

Hope I've helped somehow to solve this.

[SOLUTION in python (if anyone needs)]

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（10）

゛清羽墨安 2024-10-08 02:36:07

与 2-斐波那契一样，动态规划是最佳选择。记住前面的 k 值，以便在 O(n) 时间内快速计算后面的值。

您可以用来提高 k 大值速度的另一种优化是将 f(nk) 到 f(n-1) 添加到获取 f(n)，而只需使用 (2*f(n-1)) - f(nk-1)。由于这只使用 2 次查找、2 次加法和一次乘法，因此当 k 变大时，它远远优于 k 查找和 k 加法（但是它仍然是O(n)，只是一个较小的常数乘数）。

As with 2-fibonacci, dynamic programming is the way to go. Memoize the values of earlier ks to quickly compute the later ones, in O(n) time.

Another optimization that you can use to improve speed for large values of k is instead adding f(n-k) through f(n-1) to get f(n), instead just use (2*f(n-1)) - f(n-k-1). Since this only uses 2 lookups, 2 adds, and a multiply, it's vastly superior to k lookups and k adds when k becomes large (but it's still O(n), just a smaller constant multiplier).

回复 原文
私藏温柔 2024-10-08 02:36:07

这是一个基于 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, ...

Here is an iterative solution building on Ambers answer:

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);
    }
}

A test looks like this:

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("...");

        }
    }
}

And prints

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, ...
回复 原文
数理化全能战士 2024-10-08 02:36:07

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

基本上，其工作方式是将向量 F(n), F(n-1) ... F(nk) 表示为矩阵乘以向量 F(n-1) ), F(n-2) ... F(nk-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)]

If you just want to solve for one value (i.e. fibonnaci(n,k)), then a more efficient way is to use a linear recurrence, which will be O(k^3 log(n)) (the k^3 factor can be improved with a better matrix multiplication algorithm).

Basically, the way this works is that you express the vector F(n), F(n-1) ... F(n-k) as matrix times the vector F(n-1), F(n-2) ... F(n-k-1). Then since matrix multiplication is associative, you can raise the matrix to a power, and multiply this by an initial vector F(k), F(k-1) ... F(0).

Exponentiation can be done in O(log(n)) using exponentiation by squaring.

For example, for the k=3 case, we will have:

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

so to solve for F(n), you just find

[F(n+2)]   [1 1 1]^n [F(2)]
[F(n+1)] = [1 0 0]   [F(1)]
[F(n)  ]   [0 1 0]   [F(0)]
回复 原文
可爱咩 2024-10-08 02:36:07

最直接的方法是每次将最后 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)

The straightforward way is to simply add up the last k terms to get the current term every time. This gives us a O(n*k) runtime.

Another way would be to use matrix exponentiation. For k=2, you can model the situation using a matrix. From (Fn-1, Fn-2) we can derive (Fn, Fn-1) by computing (Fn-1+Fn-2,Fn-1).

Thus, multiplying the coloumn matrix

[
Fn-1
Fn-2
]

with the square matrix

[
1 1
1 0
]

yields

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

thereby giving us the value of Fn.

Of course, this isn't really any better than O(n*k) yet. We would still be running a O(n) loop/recursion to get the n-th term.

Observe that
(I am writing coloumn vectors horizontally for convenience now, but they are still coloumns)

[[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

Now, ([[1,1] [1,0]])^n-1 can be computed in O(log(n)) time using exponentiation by squaring. Thus, you can compute the n-th term of k-fibonacci using at most log(n) matrix multiplications. Using straightforward matrix multiplication, this gives us a complexity of O(k^3*log(n)).

Edit:

Here's some code in Python I hacked together to illustrate what I'm saying better:

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)
回复 原文
城歌 2024-10-08 02:36:07

为了练习它，我在 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]

For the exercise of it, I implemented this in Haskell. Here is how fib is ordinarily written as a list comprehension:

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

Generalizing to 'k' terms is difficult because the zip requires two arguments. There is a zip3, zip4, etc. but no general zipn. However we can do away with the technique of creating pairs, and instead generate "all tails of the sequence", and sum the first k members of those. Here is how that looks for the k=2 case:

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

Generalizing to any 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]
回复 原文
倚栏听风 2024-10-08 02:36:07

下面是另一个 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;
    }
}

Another log(n) solution below.
Source and explanation here.
You could cache the solutions if a lot of calls are made.

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;
    }
}
回复 原文
舟遥客 2024-10-08 02:36:07

人们已经提到过 O(logN) 解决方案。没有多少人了解求幂矩阵中的常数是如何产生的。如果你想详细分析如何使用矩阵求解线性递推，请查看 代码溢出。

People have already mentioned O(logN) solutions. Not many people understand how the constants in the matrix that is exponentiated came into being. If you want a detailed analysis of how to use matrices to solve linear recurrences, have a look at Code Overflow.

回复 原文
紙鸢 2024-10-08 02:36:07

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

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 来执行以整数计算。

Here's an efficient, terse and exact closed form solution.

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

Here's the output:

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

The method is effectively computing X^(n+k) in the polynomial ring Z[X]/(X^k-X^(k-1)-X^(k-2)-...-1) (where the result of the constant term in the final polynomial is somewhat surprisingly fibk(n, k)), but using a large enough integer A instead of X to perform the calculation in the integers.

回复 原文
勿忘初心 2024-10-08 02:36:07

我猜您需要比 O(nk) 更好的东西。
对于O(nk)，您可以简单地计算它。
如果您有 n <= N 和 k <= K 的上限，您还可以构建一个矩阵 NxK 一次并在需要该值时随时查询。

编辑
如果您想进一步深入数学，您可以尝试阅读这篇关于广义阶的论文 - k 佩尔号码。

I guess that you need something that is better than O(nk).
For O(nk), you can just compute it naively.
In case that you have an upper bound on n <= N and k <= K, you can also build a matrix NxK once and query it anytime you need the value.

EDIT
If you want to dig further into math, you can try to read this paper on Generalized Order-k Pell Numbers.

回复 原文
通知家属抬走 2024-10-08 02:36:07

简单的暴力解决方案

    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]+" ");
    }

simple brute-force solution

    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]+" ");
    }
回复 原文
~没有更多了~

关于作者

绅士风度i

暂无简介

文章
评论
26 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

尘曦

文章 0 评论 0

在梵高的星空下

文章 0 评论 0

善良天后

文章 0 评论 0

韬韬不绝

文章 0 评论 0

qq_CgiN62

文章 0 评论 0

不美如何

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文