Discussion :

[le marocain]

bonjour ,
j'ai probleme avec cette suite U1=0 , U2=1 et Un= 3*Un-1 + 2*Un-2 (n>=3)
je veux écrire un algo qui demande à l'utilisateur de saisir un nombre n et calcule le néme terme de la suite de Fibonacci définie par la suite précéfente
malheureusement je n'est pas trouvé une maniére pour écrire cet algo .

[acacia]

bonjour ,
j'ai probleme avec cette suite U1=0 , U2=1 et Un= 3*Un-1 + 2*Un-2 (n>=3)
je veux écrire un algo qui demande à l'utilisateur de saisir un nombre n et calcule le néme terme de la suite de Fibonacci définie par la suite précéfente
malheureusement je n'est pas trouvé une maniére pour écrire cet algo .

Bonsoir,

tu as pensé à la récursivité?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
suite_fibo(n)
 
Begin
 
  si (n = 0) ou (n = 1) alors 
résultat =1
 
sinon
 
résultat= suite_fibo(n-1) + suite_fibo(n-2)
 
end

mais dès que n devient grand, cette solution devient très couteuse en temps.

[Jedai]

Bonsoir,

tu as pensé à la récursivité?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
suite_fibo(n)
 
Begin
 
  si (n = 0) ou (n = 1) alors 
résultat =1
 
sinon
 
résultat= suite_fibo(n-1) + suite_fibo(n-2)
 
end

mais dès que n devient grand, cette solution devient très couteuse en temps.

Je dirais même que cette solution n'est utilisable que pour les n extrèmement petit, la complexité étant exponentielle alors que le problème est en O(log n) en réalité.
Mais il est déjà extrêmement simple d'en revenir à une complexité linéaire, que ce soit en récursif ou en impératif.
Par exemple avec une récursion terminale :

Code Haskell :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
fib_auxiliaire 1 u u' = u'
fib_auxiliaire n u u' = fib_auxiliaire (n-1) (3*u+2*u') u
 
fib n = fib_auxiliaire n 1 0

--
Jedaï

[alex_pi]

bonjour ,
j'ai probleme avec cette suite U1=0 , U2=1 et Un= 3*Un-1 + 2*Un-2 (n>=3)
je veux écrire un algo qui demande à l'utilisateur de saisir un nombre n et calcule le néme terme de la suite de Fibonacci définie par la suite précéfente
malheureusement je n'est pas trouvé une maniére pour écrire cet algo .

Regarde les méthode de calcul de la suite de fibonnacci sur wikipedia et inspire-t-en. En gros il y a trois méthode.

La mauvaise : la récurcivité qui a pour complexité la suite de Fibo justement (soit une complexité exponentielle).

Il y a ensuite la méthode linéaire, qui a deux sous méthodes.
Celle que plein de gens pratiquent qui consiste à remplir un tableau.
Celle un peu plus maline (car constante en utilisation mémoire) qui consiste à passer du couple (u_n, u_n+1) au couple (u_n+1, u_n+2).

Et enfin la méthode logarithmique qui consiste à remarquer que dans la méthode précédante, le passage d'un couple au suivant est une multiplication matricielle, et que l'on peut faire une exponentiation rapide.

Have fun