Algoritmo per la k-Fibonacci

Question

Sappiamo tutti fibonacci serie, quando k = 2.

cioè .: 1,1,2,3,5,8,13

Ma questo è il 2-Fibonacci. In questo modo, posso contare il terzo Fibonacci:

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

E il 4 Fibonacci:

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

... e così va avanti

Quello che sto chiedendo è un algoritmo calcolare un elemento 'n' all'interno di una serie k-fibonacci.

In questo modo: se chiedo il fibonacci(n=5,k=4), il risultato dovrebbe essere: 8, ovvero il quinto elemento all'interno della serie 4-fibonacci.

Non l'ho trovato da nessuna parte sul web. Una soluzione per aiutare potrebbe essere mathworld

Chiunque? E se conosci Python, preferisco. Ma se no, qualsiasi linguaggio o algoritmo può aiutare.

Tip penso che può aiutare: Analizziamo la serie K-Fibonacci, dove k sarà vanno da 1 a 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, ... 

Analizzando questo, possiamo vedere che l'array [0: k] su la serie k-fibonacci è uguale alla serie precedente di fibonacci e va avanti fino al k = 1

ie (proverò a mostrare, ma non sto trovando il modo giusto per dirlo):

k fibonacci series 

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

Spero di aver contribuito in qualche modo a risolvere questo.

[SOLUZIONE in python (se qualcuno ha bisogno)]

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

Answer 1

Ecco un edificio soluzione iterativa su 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); 
    } 
} 

Un test simile a questa:

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 stampe

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

Answer 2

Credo che avete bisogno di qualcosa che è meglio di O(nk).
Per O(nk), puoi semplicemente calcolarlo in modo ingenuo.
Nel caso in cui si abbia un limite superiore su n <= N e k <= K, è anche possibile creare una matrice NxK una volta e interrogarla ogni volta che è necessario il valore.

EDIT
Se si vuole scavare ulteriormente in matematica, si può provare a leggere this paper on Generalized Order-k Pell Numbers.

Answer 3

Come con 2-fibonacci, la programmazione dinamica è la strada da percorrere. Memorizza i valori dei precedenti k s per calcolare rapidamente quelli successivi, nel tempo O(n).

Un'altra ottimizzazione che è possibile utilizzare per migliorare la velocità per grandi valori di k è invece l'aggiunta di f(n-k) attraverso f(n-1) per ottenere f(n), invece basta usare (2*f(n-1)) - f(n-k-1).Poiché utilizza solo 2 ricerche, 2 aggiunte e una moltiplicazione, è di gran lunga superiore alle ricerche e aggiunge quando k diventa grande (ma è ancora O(n), solo un moltiplicatore costante più piccolo).

Answer 4

Il modo più semplice è quello di aggiungere semplicemente su gli ultimi k termini per ottenere il termine corrente ogni volta. Questo ci dà un runtime O (n * k).

Un altro modo sarebbe utilizzare l'esponenziazione della matrice. Per k = 2, puoi modellare la situazione usando una matrice. Da (Fn-1, Fn-2) possiamo derivare (Fn, Fn-1) calcolando (Fn-1 + Fn-2, Fn-1).

Così, moltiplicando la matrice colonnina

[ 
Fn-1 
Fn-2 
] 

con la matrice quadrata

[ 
1 1 
1 0 
] 

rendimenti

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

dando così noi il valore di Fn.

Naturalmente, questo non è davvero migliore di O (n * k) ancora. Saremmo ancora in esecuzione un ciclo O/ricorsione per ottenere il n-esimo termine.

osservare che (sto scrivendo vettori coloumn orizzontale per comodità ora, ma sono ancora 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 

Ora, ([[1,1] [1,0]])^n-1 può essere calcolato in O (log (n)) utilizzando exponentiation by squaring. Quindi, puoi calcolare il n-esimo termine di k-fibonacci usando al massimo molte moltiplicazioni di matrici log (n). Usando la moltiplicazione di matrici dirette, questo ci dà una complessità di O (k^3 * log (n)).

Edit:

Ecco un po 'di codice in Python ho messo insieme per illustrare quello che sto dicendo meglio:

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) 

Answer 5

Se si vuole solo risolvere per un valore (cioè fibonnaci(n,k)), poi un un modo più efficiente consiste nell'utilizzare una ricorrenza lineare, che sarà O(k^3 log(n)) (il fattore k^3 può essere migliorato con un algoritmo di moltiplicazione della matrice migliore).

Fondamentalmente, il modo in cui questo funziona è che si esprime il vettore F(n), F(n-1) ... F(n-k) come matrice volte il vettore F(n-1), F(n-2) ... F(n-k-1). Quindi poiché la moltiplicazione della matrice è associativa, è possibile aumentare la matrice a una potenza e moltiplicarla per un vettore iniziale F(k), F(k-1) ... F(0).

L'esponenziazione può essere eseguita in O(log(n)) utilizzando l'elevazione a potenza di squadratura.

Ad esempio, per il k = 3 caso, avremo:

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

in modo da risolvere per la F (n), basta trovare

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

Answer 6

Per l'esercizio di esso, L'ho implementato in Haskell. Ecco come fib ordinariamente scritto come una lista di comprensione:

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

Generalizzando a patti 'K' è difficile, perché il zip richiede due argomenti. C'è un zip3, zip4, ecc. Ma non è un numero generale zipn. Tuttavia, possiamo eliminare la tecnica della creazione di coppie e generare invece "tutte le code della sequenza" e sommare i primi membri di k. Ecco come che cerca il k = 2 casi:

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

Generalizzando a qualsiasi 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] 

Answer 7

Un'altra log (n) soluzione qui di seguito.
Source and explanation here.
È possibile memorizzare nella cache le soluzioni se vengono effettuate molte chiamate.

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

Answer 8

Le persone hanno già menzionato le soluzioni O (logN). Non molte persone capiscono come sono nate le costanti nella matrice che è esponenziata. Se si desidera un'analisi dettagliata di come utilizzare matrici per risolvere ricorrenze lineari, dare un'occhiata a Code Overflow.

Answer 9

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

Answer 10

Ecco una soluzione sotto forma efficace, concisa e precisa chiuso.

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

Ecco l'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 

Il metodo è efficace calcolando X^(n + k) nell'anello polinomiale Z [X]/(X^kX^(k-1) - X^(k-2) -...- 1) (dove il risultato del termine costante nel polinomio finale è in qualche modo sorprendentemente fibroso (n, k)), ma usando un numero intero abbastanza grande A invece di X per eseguire il calcolo nei numeri interi.