Itératif Version Modifiée suite de Fibonacci

Je viens de passer par la version itérative de l'algorithme de la série de fibonacci. J'ai trouvé ce code suivant

int Fibonacci(int n)
{
   int f1 = 0;
   int f2 = 1;
   int fn;
   for ( int i = 2; i < n; i++ )
   {
      fn = f1 + f2;
      f1 = f2;
      f2 = fn;
   }
}

Un idiot en question soulevée dans mon esprit. La fonction ci-dessus ajoute deux nombres précédents et renvoie le troisième et ensuite obtenir des variables prêt pour la prochaine itération. Si ce serait quelque chose comme ceci. "De retour d'un numéro de série qui est la somme de trois nombres" comment on peut changer le code ci-dessus pour trouver un tel numéro.u

euh... f = (f - 1) + (f - 2) + (f - 3) qui se résume à de l'algèbre: f = (3*f) - 6
Ce que vous avez écrit ci-dessus est vrai, mais la notation est faux. La récurrence f(n) = f(n - 1) + f(n - 2) + f(n - 3), qui ne peut être simplifiée de la façon dont vous avez décrit.
c'est la partie facile. comment nous les valeurs de la f1,f2,f3 pour être prêt pour la prochaine itération?

OriginalL'auteur talhaMalik22 | 2012-06-18

c++fibonacci java math sequence

6

Comme un soupçon, notez que l'algorithme ci-dessus fonctionne par "le vélo" les chiffres par le biais de certaines variables. Dans le code ci-dessus, à chaque point que vous stockez
```
 F_0    F_1
  a      b
```
Vous puis "shift" sur un pas dans la boucle:
```
 F_1    F_2
  a      b
```
Vous puis "shift" de nouveau dans la prochaine itération de boucle:
```
 F_2    F_3
  a      b
```
Si vous souhaitez mettre à jour l'algorithme de somme de la dernière trois valeurs, pensez à les stocker comme ceci:
```
 T_0    T_1    T_2
  a      b      c
```
Puis maj:
```
 T_1    T_2    T_3
  a      b      c
```
Puis maj:
```
 T_2    T_3    T_4
  a      b      c
```
De la conversion de cette intuition dans le code est un bon exercice, je vais donc laisser ces détails pour vous.

Qui dit - on est beaucoup, beaucoup moyen plus rapide pour calculer le n-ième terme de Fibonacci et "Tribonacci" séquences. Cet article décrit une très astuce en utilisant la matrice de multiplication pour calculer des termes plus rapidement que le dessus de la boucle, et il est le code disponible ici qui implémente cet algorithme.

Espérons que cette aide!

Vous droite sur la place. en fait, c'était la partie la plus délicate, la façon dont il réaffectation des valeurs à des variables. Il est de travail. Merci et bien fait.

OriginalL'auteur templatetypedef

J'aime la récursivité. Appelez-moi un sadique.

static int rTribonacci (int n, int a, int b, int c) {
    if (n == 0) return a;
    return rTribonacci (n-1, b, c, a + b + c);
}

int Tribonacci (int n) { return rTribonacci(n, 0, 0, 1); }

OriginalL'auteur jxh

3

Je n'ai pas l'habitude de répondre à des questions qui "sentent" comme des devoirs, mais puisque quelqu'un d'autre déjà répondu c'est ce que je ferais:
```
int Tribonacci(int n)
{
    int last[3] = { 0, 0, 1 }; //the start of our sequence

    for(int i = 3; i <= n; i++)
        last[i % 3] = last[i % 3] + last[(i + 1) % 3] + last[(i + 2) % 3];

    return last[n % 3];
}
```
Il peut être amélioré un peu pour éviter tous les laides de l'arithmétique modulaire (que j'ai laissé à faire de la nature circulaire de la [dernière] tableau clair) par la modification de la boucle à ceci:
```
    for(int i = 3; i <= n; i++)
        last[i % 3] = last[0] + last[1] + last[2];
```
Il peut être optimisé un peu plus et franchement, il y a beaucoup de meilleures façons de calculer de telles séquences, comme templatetypedef dit.

OriginalL'auteur Nik Bougalis

Si vous souhaitez utiliser la récursivité, vous n'avez pas besoin d'autres paramètres:

int FibonacciN(int position)
{   if(position<0) throw new ArgumentException("invalid position");
    if(position==0 || position ==1) return position;
    return FibonacciN(position-1) + FibonacciN(position-2);
}

OriginalL'auteur AdrianM

Vous devez vous connecter pour publier un commentaire.