algorithme pour k-Fibonacci

Question

Nous savons tous fibonacci série, lorsque k = 2.

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

Mais c'est le 2-fibonacci. Comme cela, je peux compter le troisième fibonacci:

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

Et le 4-fibonacci:

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

... et ainsi se passe

Ce que je demande est un algorithme pour calculer un élément 'n' à l'intérieur d'une série de k-fibonacci.

Comme ceci: si je demande fibonacci(n=5,k=4), le résultat devrait être: 8, c'est-à-dire le cinquième élément de la série 4-fibonacci.

Je ne l'ai trouvé nulle part web. Une ressource pour aider pourrait être mathworld

Quelqu'un? Et si vous connaissez python, je préfère. Mais sinon, n'importe quel langage ou algorithme peut aider.

Astuce Je pense que cela peut aider: Analysons la série k-fibonacci, où k sera vont de 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, ... 

L'analyse, nous pouvons voir que le tableau [0: k] sur la série k-fibonacci est égale à la précédente série de fibonacci , et elle continue jusqu'à k = 1

ie (je vais essayer de montrer, mais je ne trouve pas la bonne façon de le dire):

k fibonacci series 

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

J'espère avoir aidé d'une manière ou d'une autre à résoudre ce problème.

[SOLUTION en python (si quelqu'un a besoin)]

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

Voici un bâtiment de solution itérative sur 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 ressemble à ceci:

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

     } 
    } 
} 

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

Answer 2

Je suppose que vous avez besoin de quelque chose qui est mieux que O(nk).
Pour O(nk), vous pouvez simplement le calculer naïvement.
Dans le cas où vous avez une limite supérieure sur n <= N et k <= K, vous pouvez également créer une matrice NxK une fois et l'interroger chaque fois que vous avez besoin de la valeur.

EDIT
Si vous voulez creuser plus loin en mathématiques, vous pouvez essayer de lire this paper on Generalized Order-k Pell Numbers.

Answer 3

Comme avec 2-fibonacci, la programmation dynamique est la voie à suivre. Mémoisez les valeurs de k s pour calculer rapidement les plus récentes, en O(n).

Une autre optimisation que vous pouvez utiliser pour améliorer la vitesse pour les grandes valeurs de k est au lieu d'ajouter f(n-k) par f(n-1) pour obtenir f(n), il suffit d'utiliser à la place (2*f(n-1)) - f(n-k-1).Puisque cela utilise seulement 2 recherches, 2 ajouts, et une multiplication, il est largement supérieur aux recherches k et k ajoute quand k devient grand (mais c'est toujours O(n), juste un plus petit multiplicateur constant).

Answer 4

La façon simple est d'ajouter tout simplement les derniers k termes pour obtenir le terme courant à chaque fois. Cela nous donne un runtime O (n * k).

Une autre façon serait d'utiliser l'exponentiation matricielle. Pour k = 2, vous pouvez modéliser la situation en utilisant une matrice. De (Fn-1, Fn-2) on peut dériver (Fn, Fn-1) par calcul (Fn-1 + Fn-2, Fn-1).

Ainsi, la multiplication de la matrice coloumn

[ 
Fn-1 
Fn-2 
] 

avec la matrice carrée

[ 
1 1 
1 0 
] 

rendements

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

nous donnant ainsi la valeur de Fn.

Bien sûr, ce n'est pas vraiment mieux que O (n * k) pour le moment. Nous aurions toujours une boucle/récursion O (n) pour obtenir le nième terme.

Observe que (j'écris des vecteurs de Coloumn horizontalement pour plus de commodité maintenant, mais ils sont coloumns encore)

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

Maintenant, ([[1,1] [1,0]])^n-1 peut être calculé en O (log (n)) en utilisant exponentiation by squaring. Ainsi, vous pouvez calculer le nième terme de k-fibonacci en utilisant au plus des multiplications matricielles log (n). En utilisant la multiplication directe de la matrice, cela nous donne une complexité de O (k^3 * log (n)).

Edit:

Voici un code en Python je piraté ensemble pour illustrer ce que je dis mieux:

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

Si vous voulez juste résoudre pour une valeur (c.-à-fibonnaci(n,k)), alors Le moyen le plus efficace est d'utiliser une récurrence linéaire, qui sera O(k^3 log(n)) (le facteur k^3 peut être amélioré avec un meilleur algorithme de multiplication matricielle).

Fondamentalement, la façon dont cela fonctionne est que vous exprimez le vecteur F(n), F(n-1) ... F(n-k) comme matrice fois le vecteur F(n-1), F(n-2) ... F(n-k-1). Puis, comme la multiplication matricielle est associative, vous pouvez augmenter la matrice à une puissance, et la multiplier par un vecteur initial F(k), F(k-1) ... F(0).

L'exponentiation peut être faite en O(log(n)) en utilisant l'exponentiation par équerrage.

Par exemple, pour k = 3 cas, nous aurons:

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

afin de résoudre F (n), vous trouverez juste

[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

Pour l'exercice de celui-ci, Je l'ai implémenté dans Haskell. Voici comment fib est habituellement écrit comme la compréhension de la liste:

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

Généralisation à des termes « k » est difficile parce que le zip nécessite deux arguments. Il y a un zip3, zip4, etc. mais pas de général zipn. Cependant, nous pouvons nous débarrasser de la technique de création de paires, et générer à la place «toutes les queues de la séquence», et en additionner les premiers membres de ceux-ci. Voici comment qui cherche k = 2 cas: solution

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 autre journal (n) ci-dessous:

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

Généraliser à tout k.
Source and explanation here.
Vous pouvez mettre en cache les solutions si un grand nombre d'appels sont effectués.

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

Les personnes ont déjà mentionné les solutions O (logN). Peu de gens comprennent comment les constantes de la matrice exponentielle sont apparues. Si vous voulez une analyse détaillée de la façon d'utiliser des matrices pour résoudre des récurrences linéaires, jetez un oeil à Code Overflow.

Answer 9

solution simple force brute

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

est ici un moyen efficace, laconique et une solution de forme exacte fermée.

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

Voici la sortie:

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 

La méthode calcule efficacement X^(n + k) dans l'anneau de polynômes Z [X]/(X^kX^(k-1) - X^(k-2) -...- 1) (où le résultat du terme constant dans le polynôme final est quelque peu étonnamment fibk (n, k)), mais en utilisant un entier assez grand A au lieu de X pour effectuer le calcul dans les entiers.