Suite de Fibonacci

Ecrire un programme intitulé SUITE_FIBONACCI, qui calcule les N premiers termes de la suite de Fibonacci. N est une valeur entiére donnée par l'utilisateur.
Une suite de Fibonacci est une suite dans laquelle chaque élément est la somme des deux elements qui le précèdent:
Fi = Fi-1 + Fi-2 avec F1=F2=1.

Voici une ilustration pratique pour ce problèmes, on suppose que les lapins ne meurent pas :

lamia a écrit:Ecrire un programme intitulé SUITE_FIBONACCI, qui calcule les N premiers termes de la suite de Fibonacci. N est une valeur entiére donnée par l'utilisateur.
Une suite de Fibonacci est une suite dans laquelle chaque élément est la somme des deux elements qui le précèdent:
Fi = Fi-1 + Fi-2 avec F1=F2=1.

Autres questions d'enrichissement:

1. indiquer l'ordre de l'algorithme récurrent quicalcule la suite de fibonacci.
2. développer une solution récursive.
3. existe-t-il une solution ni récurrente, ni récursive?

Merci manianis pour cette illustration, ca permet de comprendre plus le probleme.
Et merci pour toi aussi methodiX pour ces questions d'enrechissement.

methodiX a écrit:...
3. existe-t-il une solution ni récurrente, ni récursive?

Trés bonne question si vous en avez la réponse merci de me l'envoyer par Message Privé. Moi je ne sais pas y répondre.

J'ai fait une version récurrente et une autre récursive, mais je sais pas s'il existe une autre solution ni récurrente ni récursive.



Dans le probleme de la suite de Fibonacci je trouve deux versions:

• F1=F2=1
  
  Fi = Fi-1 + Fi-2 (i>=3)
  

(Dans ce cas le terme F0 est défini ou non?)

• F0=F1=1
  
  Fi = Fi-1 + Fi-2 (i>=2)
  

Quelle version faut adopter???

Il suffit de donner la valeur de deux termes consécutifs de la suite pour pouvoir calculer tous les autres termes par récurrence. Donc, aucun problème particulier ne se pose dans le cas de "F0 défini".

methodiX m'avait donné une indication concernant la méthode ni récurrente, ni récursive. Il avait dit qu'il faudra chercher une suite en fonction de n et qui dépend du nombre d'or : Phi = (1+sqrt(5))/2

Ma question là, lim Un+2/Un pour n-->+oo = Phi

manianis a écrit:methodiX m'avait donné une indication concernant la méthode ni récurrente, ni récursive. Il avait dit qu'il faudra chercher une suite en fonction de n et qui dépend du nombre d'or : Phi = (1+sqrt(5))/2

Ma question là, lim Un+2/Un pour n-->+oo = Phi

la limite cherchée est lim Un+1/Un pour n-->+oo = Phi, non?

Lamia : Je voudrais dire qu'il s'agit seulement de limite qui peut être retrouée de plusieurs façon càd il peut exister plusieurs fonctions qui possèdent la même limite.

Donc, méthodiX donnez-nous la formule en fonction de Phi, je n'arrive pas à la retrouver. Merci.

Salut à tous,
Intéressante la discussion.
En fait, pour une suite récurrente, il faut connaitre certaines choses.
1. Comprendre la notion d'Ordre de Récurrence.
2. Savoir qu'il est possible de trouver une forme fonctionnelle de la suite


J'explique...
1. Notion d'ordre de Récurrence
On dit qu'une suite est récurrente F d'ordre k si le calcul de F(n) exige la connaissance des k derniers termes qui précèdent F(n) çàd:
F(n) = fonction de (F(n-1), F(n-2), ....., F(n-k))
Ainsi la suite de Fibonacci est une suite récurrente d'ordre 2 puisque
F(n+2) = F(n+1) + F(n).
Notez bien qu'on peut contruire une suite de Fibonacci d'ordre k>2.
Elle est dite la suite de Fibonacci Généralisée:
F(n+k) = F(n+k-1) + F(n+k-2) .... + F(n).

2. Calcul de la forme fonctionnelle d'une suite récurrente
La forme fonctionnelle d'une suite F permet de calculer directement F(n) pour tout n, sans préalable connaissance des F(n-i).
Exemple: F(n) = n + 5 (ou aussi F(n+1) = F(n) + 5 et F(0)=5)
Les transformations Récurrente->Fonctionnelle et Fonctionnelle->Récurrente ne sont pas toujours possibles à ma connaissance.
La question qui se pose à ce niveau est:

Comment, à partir d'une forme récurrente, déterminer la forme fonctionnelle d'une suite?

.... à suivre

J'ai essayé de comprendre un peut comment faut procéder mais c'est un peu flou pour moi vu que je n’ai pas fait d'études approfondies en maths (et c'est différent de ce que j'ai étudié en bac math et mes études universitaires maintenant n’ont aucune relation avec les maths)



Bon j’ai fait une petite recherche pour comprendre et ca a donné:


Comme la suite de Fibonacci est récurrente d’ordre deux, on peut écrire son équation caractéristique. On obtient une équation du second degré :

.
Le calcul du discriminant de cette équation donne les deux solutions du polynôme:


et
.
( est le nombre d'or, et l'opposé de la section dorée).
Les suites et engendrent alors l'espace vectoriel des suites vérifiant Un+2 = Un+1 + Un. Il en résulte que :

( et sont des constantes à déterminer à partir de et .)
Les conditions initiales conduisent au système suivant :


Ce qui donne le résultat suivant :


et
.
Nous obtenons finalement l'expression fonctionnelle recherchée, qui porte le nom de formule de Binet:

.

C'est exactement ça lamia.
Merci NabiL pour l'explication. Elle est méthodique (methodiX)

Merci Lamia. J'ai dû jeter un coup d'oeil dans Wikipedia. En tous cas, je met le lien pour permettre d'enrichir la discution (discussion).

http://fr.wikipedia.org/wiki/Suite_de_Fibonacci