2010-11-08 43 views
13

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

@Amber, @Itay: gracias por los consejos. Algún algoritmo para resolver esto? Estoy realmente perdido en este problema. –

+0

@ 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

+0

Encontré algo de papel al respecto *** LA FÓRMULA DE BINETES GENERALIZADA ***. Publicado el enlace en mi respuesta. –

Respuesta

6

Aquí es un edificio de solución iterativa en 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); 
    } 
} 

Una prueba es el siguiente:

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

     } 
    } 
} 

e imprime

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, ... 
+0

Tenga en cuenta que debido a la implementación vía recursión, esto puede aparecer en (irónico para el sitio) errores de desbordamiento de pila para valores grandes de 'n' (o en ciertos lenguajes, errores de 'profundidad de recursión máxima'). – Amber

+0

Buen punto. Estoy actualizando ... – aioobe

+0

@Amber, mucho mejor ahora. Buena idea con la sugerencia '(2 * f (n-1)) - f (n-k-1)'. – aioobe

0

supongo que se necesita algo que es mejor que O(nk).
Para O(nk), puede simplemente calcularlo ingenuamente.
En caso de que tenga un límite superior en n <= N y k <= K, también puede crear una matriz NxK una vez y consultarla en cualquier momento que necesite el valor.

EDITAR
Si desea excavar más en matemáticas, se puede tratar de leer this paper on Generalized Order-k Pell Numbers.

+0

Tenga en cuenta que algunos cálculos "ingenuos" son más ingenuos que otros. Un cálculo verdaderamente ingenuo de un número de Fibonacci es más parecido a 'O (N!)' (Si usa cálculos recursivos sin memoria). – Amber

+0

@Amber - Quise decir para el menos ingenuo :) –

+1

@Itay: Su enlace está muerto. Aquí está la lista de publicaciones del autor. Muchos artículos útiles para este tema: http://ekilic.etu.edu.tr/Publications.htm –

9

Al igual que con 2-fibonacci, la programación dinámica es el camino a seguir. Recuerde los valores de k s anteriores para calcular rápidamente los posteriores, en O(n) tiempo.

Otra optimización que se puede utilizar para mejorar la velocidad para valores grandes de k en su lugar se agregó f(n-k) través f(n-1) para obtener f(n), en lugar de simplemente utilizar (2*f(n-1)) - f(n-k-1).Como esto solo usa 2 búsquedas, 2 agregaciones y una multiplicación, es muy superior a las búsquedas k y k agrega cuando k se vuelve grande (pero sigue siendo O(n), solo un multiplicador constante más pequeño).

3

La forma más sencilla es simplemente sumar los últimos k términos para obtener el término actual cada vez. Esto nos da un tiempo de ejecución O (n * k).

Otra forma sería utilizar la exponenciación de la matriz. Para k = 2, puede modelar la situación usando una matriz. Desde (Fn-1, Fn-2) podemos derivar (Fn, Fn-1) mediante cálculo (Fn-1 + Fn-2, Fn-1).

Por lo tanto, multiplicando la matriz de Coloumn

[ 
Fn-1 
Fn-2 
] 

con la matriz cuadrada

[ 
1 1 
1 0 
] 

rendimientos

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

lo que nos da el valor de Fn.

Por supuesto, esto no es mucho mejor que O (n * k) todavía. Todavía estaríamos ejecutando un O/n loop/recursión para obtener el n-ésimo término.

observar que (vectores de Coloumn estoy escribiendo horizontalmente para mayor comodidad ahora, pero siguen siendo 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 

Ahora, ([[1,1] [1,0]])^n-1 se puede calcular en tiempo O (log (n)) usando exponentiation by squaring. Por lo tanto, puede calcular el n-ésimo término de k-fibonacci usando como máximo log (n) multiplicaciones de matrices. Usando la multiplicación directa de la matriz, esto nos da una complejidad de O (k^3 * log (n)).

Editar:

Aquí hay algo de código en Python Pirateé juntos para ilustrar lo que quiero decir mejor:

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

La multiplicación de la matriz es incorrecta y la multiplicación de la matriz requiere al menos 'O (k^2.3)' (este es el algoritmo más conocido), el ingenuo toma 'O (k^3)'. Entonces la complejidad es mayor que 'O (k^2 * log (n))' – JPvdMerwe

+0

@JPvdMerwe: Gracias. Corregí mi respuesta. – MAK

7

Si lo que desea es resolver para un valor (es decir fibonnaci(n,k)), a continuación, una la forma más eficiente es usar una recurrencia lineal, que será O(k^3 log(n)) (el factor k^3 se puede mejorar con un mejor algoritmo de multiplicación de matrices).

Básicamente, la forma en que esto funciona es que expresas el vector F(n), F(n-1) ... F(n-k) como matriz multiplicada por el vector F(n-1), F(n-2) ... F(n-k-1). Entonces dado que la multiplicación de la matriz es asociativa, puede elevar la matriz a una potencia y multiplicar esto por un vector inicial F(k), F(k-1) ... F(0).

La exponenciación se puede hacer en O(log(n)) usando la exponenciación por cuadratura.

Por ejemplo, para el k = 3 caso, tendremos:

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

manera de resolver para F (n), que acaba de encontrar

[F(n+2)] [1 1 1]^n [F(2)] 
[F(n+1)] = [1 0 0] [F(1)] 
[F(n) ] [0 1 0] [F(0)] 
1

Para el ejercicio de la misma, Implementé esto en Haskell. Así es como fib se escribe normalmente como una lista por comprensión:

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

Generalizando a los términos 'k' es difícil porque el zip requiere dos argumentos. Hay un zip3, zip4, etc. pero ningún general zipn. Sin embargo, podemos eliminar la técnica de crear pares y, en su lugar, generar "todos los extremos de la secuencia" y sumar los primeros k miembros de esos. Aquí es cómo que busca la k = 2 caso:

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

Generalizando a cualquier 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] 
1

Otra log (n) solución a continuación.
Source and explanation here.
Puede almacenar en caché las soluciones si se realizan muchas llamadas.

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

Las personas ya han mencionado las soluciones O (logN). No muchas personas entienden cómo se formaron las constantes en la matriz que se expondrá. Si quieres un análisis detallado de cómo utilizar matrices para resolver recurrencias lineales, echar un vistazo a Code Overflow.

0

solución simple fuerza bruta

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

'solución' en un formalismo que no vale la pena mencionar. Mientras veo '(formula * 2-fib [i-k])' como una adición válida a las respuestas existentes en el momento de agregar esto: ¿qué magia hace que '1000000007' se vuelva feo? – greybeard

+0

disculpa por ese error tipográfico –

0

He aquí una solución de forma eficiente, conciso y exacto cerrada.

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

Aquí está la salida:

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 

El método está calculando eficazmente X^(n + k) en el anillo de polinomios Z [X]/(X^kX^(k-1) - X^(k-2) -...- 1) (donde el resultado del término constante en el polinomio final es algo sorprendentemente fibk (n, k)), pero usando un número entero suficientemente grande A en lugar de X para realizar el cálculo en los enteros.