probleme autour un algo.

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 .

Citation:

---

Envoyé par 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 .

---

Bonsoir,

tu as pensé à la récursivité?

Code:

---

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.

Citation:

---

Envoyé par acacia

Bonsoir,

tu as pensé à la récursivité?

Code:

---

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:

---

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ï

Citation:

---

Envoyé par 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 .

---

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