Qu'est-ce qu'une solution non récursive pour une séquence de type Fibonacci en Java?

Donné ce pseudo-code d'une fonction

f(0) = 1; 
f(1) = 3; 
f(n) = 3 * f(n - 1) - f(n - 2); //for n >= 2.

Est-il un non récursive façon de faire cela?

source d'informationauteur cclerville

12

Ici les réponses sont correctes, mais ils travaillent en O(n), alors vous pouvez le faire en O(log n), de façon exponentielle plus rapide. Observer que
```
[f(n)  ] = [3 -1] [f(n-1)]
[f(n-1)]   [1  0] [f(n-2)]
```
Let v_n être le vecteur [f(n), f(n-1)] et la matrice ci-dessus, de sorte que vous obtenez v_n = v_n-1donc v_n = A^n-1 v₁. Calculer (n-1)-ième puissance de la matrice A l'aide de l'exponentiation binaire et de le multiplier par v₁. Pour en savoir plus sur linéaire récidives voir ici.
10

Si votre question est de savoir si un équivalent non-définition récursive de la fonction peut être trouvé, vous devez rechercher les propriétés de la La suite de Fibonacci.

Votre séquence peut être constaté par écrit le Fibonacci (sans les 2 premiers chiffres) et la suppression de tous les 2ème numéro: 1, 3, 8, 21, 55, 144, ...
```
sqrt5 = sqrt(5)
phi = ( 1 + sqrt5 ) / 2
fibonacci(n) = round( power( phi, n ) / sqrt5 ) 
f(n) = fibonacci( 2*n + 2 )
```
7

C'est simple, en Java, la solution ressemble à ceci:
```
public int f(int n) {

      int tmp;
      int a = 3;
      int b = 1;

      for (int i = 0; i < n; i++) {
          tmp = a;
          a = 3 * a - b;
          b = tmp;
      }

      return b;

}
```
Tous récursive des solutions peut être transformé en itératif solutions (l'inverse est vrai aussi, voir ce post), mais c'est plus facile si la solution récursive c'est en queue-de-forme récursive.

L'algorithme ci-dessus peut être comprise comme une programmation dynamique de la solution à l'origine de la récursivité, c'est très efficace car il a seulement besoin de sauver les deux valeurs précédentes à chaque point dans l'itération.
2

[ Oups, je pensais que c'était un Perl question. Encore, le code doit être lisible suffisant pour un développeur Java. ]

C'est vraiment juste le déplacement de la récursivité à l'espace utilisateur, mais vous pouvez utiliser:
```
sub f { 
    my ($n) = @_;
    my @f = (1,3);
    $f[$_] = 3 * $f[$_-1]- $f[$_-2] for 2 .. $n;
    return $f[$n];
}
```
Bien sûr, cela pose pour la mise en cache. Il n'y a pas besoin de recalculer les valeurs que nous savons déjà.
```
my @f = (1,3);
sub f { 
    my ($n) = @_;
    $f[$_] = 3 * $f[$_-1]- $f[$_-2] for @f .. $n;
    return $f[$n];
}
```
2

La fonction est définie en fonction d'elle-même, donc dans un sens, toute mise en œuvre est récursive, à moins qu'un mathématicien vient et nous dit f(n) peut être évalué sans évaluation f(n-1) et f(n-2). Comme d'autres l'ont montré, il existe un moyen de le mettre en œuvre en Java fonction qui n'appelle pas lui-même.

def func(n):
    f= array(n+1)
    f[0]=1
    f[1]=3

    for i in 2:n :
        f[i] = 3*f[i-1]-f[i-2]
    return f[n]

1

La suite de Fibonacci de la séquence de nombres commence comme: 0,1,1,2,3,5,8,13,21,34,55....

cela peut être défini par une simple relation de récurrence F(n)=F(n-1)+F(n-2) pour n>1 et de deux conditions initiales F(0)=1 et F(1)=1

Algorithme De Fibonacci

//Calcule le n-ième nombre de Fibonacci

//Entrée: Un entier non négatif

//Sortie: Le n-ième nombre de Fibonacci
```
1. Begin Fibo
2. integer n, i;
3.    if n<=1 then
4.     return n;
5.  else
6.    F(0)<-0; F(1)<-1;
7.    for i<-2 to n do
8.     F(i)<-F(i-1)+F(i-2);
9.     F(i-2)=F(i-2);
10.    F(i-1)=F(i);
11. done
12. end if
13. end Fibo
```

Ici est simplement une fonction avec un minimum de ligne de code et un maximum de souplesse.

Vous pouvez ajouter toutes les "valeurs initiales" et de toute autre récursive de la fonction "" vous voulez tout simplement.

def fib(n):
  fibs = [1, 3]       # <--  your initial values here 
  if n == 1:
    return fibs[0]
  if n == 2:
    return fibs[:1]
  for i in range(2, n):
    fibs.append(3*fibs[-1] - fibs[-2])  # <-- your function here
  return fibs

Et le résultat est:

n=10
print(fib(n))

[1, 3, 8, 21, 55, 144, 377, 987, 2584, 6765]

Comme demandé par @paxdiablo je suis en train de faire cette réponse. C'est une relation de récurrence et peuvent être résolus de manière non-récursive, similaire à la séquence de fibonacci mentionné dans une autre réponse. Il s'avère être (Python notation).

def f(n):
    return int((13**0.5-3)/(2*13**0.5)*((3-13**0.5)/2)**n + (0.5+3/(2*13**0.5))*((3+13**0.5)/2)**n)

Cependant, ce forumula ne plus probablement pas travail pour n grand, en raison de son manque de précision. La version de python échoue pour n = 30:

>>> print ([f(n) == 3 * f(n-1) + f(n-2) for n in range(2, 30)])
[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, False]
>>> print([f(n) for n in range(30)])
[1, 3, 10, 33, 109, 360, 1189, 3927, 12970, 42837, 141481, 467280, 1543321, 5097243, 16835050, 55602393, 183642229, 606529080, 2003229469, 6616217487, 21851881930, 72171863277, 238367471761, 787274278560, 2600190307441, 8587845200883, 28363725910090, 93679022931153, 309400794703549, 1021881407041801]

Avertissement: j'ai utilisé un "+" au lieu de "-", de sorte que la formule est fausse. Voir les commentaires.

Vous devez vous connecter pour publier un commentaire.