Todos sabemos fibonacci serie, cuando k = 2.Algoritmo para la k-Fibonacci
es decir .: 1,1,2,3,5,8,13
Pero este es el 2-Fibonacci. De esta manera, puedo contar el tercer Fibonacci:
1,1,2,4,7,13,24
Y el 4 de Fibonacci:
1,1,2,4,8,15,29
... y así sucede en
Lo que estoy pidiendo es un algoritmo para calcular un elemento 'n' dentro de una serie k-fibonacci.
De esta manera: si pido fibonacci(n=5,k=4)
, el resultado debería ser: 8
, es decir, el quinto elemento dentro de la serie 4-fibonacci.
No lo encontré en ningún sitio web. Un recurso para ayudar podría ser mathworld
¿Alguien? Y si conoces Python, yo prefiero. Pero si no, cualquier lenguaje o algoritmo puede ayudar.
Tip creo que puede ayudar: Vamos a analizar la serie K-Fibonacci, donde k se van desde 1 hasta 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, ...
Analizando esto, podemos ver que la matriz [0: k] en la serie K-Fibonacci es igual a la anterior serie de Fibonacci, y continúa hasta el k = 1
es decir, (voy a tratar de demostrar, pero no voy a encontrar la forma correcta de decirlo):
k fibonacci series
1 1,
2 1, 1,
3 1, 1, 2,
4 1, 1, 2, 4,
5 1, 1, 2, 4, 8,
Espero haber ayudado de alguna manera a resolver esto.
[SOLUCIÓN en Python (si alguien necesita)]
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),
@Amber, @Itay: gracias por los consejos. Algún algoritmo para resolver esto? Estoy realmente perdido en este problema. –
@ Gabriel - ¿No estás seguro de a qué te refieres con el algoritmo? El cálculo de los números de Fibonacci no es realmente complejo ... – Amber
Encontré algo de papel al respecto *** LA FÓRMULA DE BINETES GENERALIZADA ***. Publicado el enlace en mi respuesta. –