当k = 2时，我们都知道斐波那契数列。
即：yasxsvppoi
但这是2-fibonacci。像这样，我可以算第三个斐波那契：
1,1,2,3,5,8,13而4-fibonacci：
1,1,2,4,7,13,24
......等等
我要问的是计算k-fibonacci系列中'n'元素的算法。
像这样：如果我要求1,1,2,4,8,15,29
，结果应该是：fibonacci(n=5,k=4)，即4-fibonacci系列中的第五个元素。
我没有在任何网站找到它。帮助的资源可能是qazxsw poi
任何人？如果你知道python，我更喜欢。但如果没有，任何语言或算法都可以提供帮助。
提示我认为这可以帮助：让我们分析k-fibonacci系列，其中k将从1到5
8分析这一点，我们可以看到k-fibonacci系列上的数组[0：k]等于之前的斐波那契数列，它一直持续到k = 1
即（我会尝试展示，但我找不到正确的说法）：
mathworld
希望我能以某种方式解决这个问题。
[python中的解决方案（如果有人需要的话）]
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 series
1 1,
2 1, 1,
3 1, 1, 2,
4 1, 1, 2, 4,
5 1, 1, 2, 4, 8,
的迭代解决方案：
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),
测试看起来像这样：
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);
}
}
简单的蛮力解决方案
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
与2-fibonacci一样，动态编程是最佳选择。记住早期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("...");
}
}
}
s的值，以便在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, ...
时间快速计算后面的值。
你可以用来提高k大值的速度的另一个优化是通过O(n)添加k来获得f(n-k)，而只是使用f(n-1)。由于这仅使用2次查找，2次加法和乘法，因此它大大优于f(n)查找和(2*f(n-1)) - f(n-k-1)在k变大时增加（但它仍然是k，只是一个较小的常数乘数）。
如果你只想求一个值（即k），那么更有效的方法是使用线性递归，这将是O(n)（可以用更好的矩阵乘法算法改进fibonnaci(n,k)因子）。
基本上，这种方法的工作方式是将向量O(k^3 log(n))表示为矩阵乘以向量k^3。然后，由于矩阵乘法是关联的，您可以将矩阵提升为幂，并将其乘以初始向量F(n), F(n-1) ... F(n-k)。
可以使用qonxswpoi通过平方乘幂进行指数化。
例如，对于k = 3的情况，我们将：
F(n-1), F(n-2) ... F(n-k-1)所以要解决F（n），你才发现
F(k), F(k-1) ... F(0)直接的方法是简单地将最后的k个术语相加以每次获得当前术语。这给了我们一个O（n * k）运行时。
另一种方法是使用矩阵求幂。对于k = 2，您可以使用矩阵对情况进行建模。从（Fn-1，Fn-2）我们可以通过计算（Fn-1 + Fn-2，Fn-1）导出（Fn，Fn-1）。
因此，乘以列矩阵
O(log(n))用方阵
[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+2)] [1 1 1]^n [F(2)]
[F(n+1)] = [1 0 0] [F(1)]
[F(n) ] [0 1 0] [F(0)]
从而给我们Fn的价值。
当然，这还不比O（n * k）好。我们仍然会运行O（n）循环/递归来获得第n个项。
观察（我现在正在水平编写列向量，但它们仍然是列）
[
Fn-1
Fn-2
]
现在，[
1 1
1 0
]
可以使用[
Fn-1 + Fn-2
Fn-1
]
在O（log（n））时间内计算。因此，您可以使用最多log（n）矩阵乘法计算k-fibonacci的第n项。使用直接矩阵乘法，这给出了O（k ^ 3 * log（n））的复杂度。
编辑：
这是Python中的一些代码我一起入侵以说明我说的更好：
[[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
为了练习它，我在Haskell中实现了它。以下是([[1,1] [1,0]])^n-1通常被编写为列表理解的方式：
exponentiation by squaring
推广到'k'项很难，因为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)
需要两个参数。有一个fib，fib = 1:1:[x + y | (x,y) <- zip fib $ tail fib]
等，但没有一般的zip。然而，我们可以取消创建对的技术，而是生成“序列的所有尾部”，并将这些的第一个zip3成员相加。以下是查找k = 2情况的方法：
zip4推广到任何zipn：
k下面的另一个log（n）解决方案。
fib2 = 1:1:[sum $ take 2 x | x <- tails fib2]
。
如果进行了大量调用，您可以缓存解决方案。
k人们已经提到了O（logN）解决方案。没有多少人理解矩阵中被取幂的常数是如何形成的。如果你想详细分析如何使用矩阵来解决线性递归问题，请看看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]
我想你需要的东西比Source and explanation here更好。
对于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;
}
}
，你可以天真地计算它。
如果你有Code Overflow.和O(nk)的上限，你也可以建立一个矩阵O(nk)一次，并在你需要值的时候查询它。
编辑
如果你想深入挖掘数学，你可以尝试阅读n <= N。
这是一个高效，简洁，精确的封闭式解决方案。
k <= K这是输出：
NxK该方法有效地计算多项式环Z [X] /（X ^ kX ^（k-1）-X ^（k-2）-...- 1）中的X ^（n + k）（其中结果最终多项式中的常数项的某些意义有点令人惊讶的是fibk（n，k）），但使用足够大的整数this paper on Generalized Order-k Pell Numbers而不是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))
来执行整数计算。