Discussion :

[Invité]

Bonjour à tous,
Je suis actuellement en train de faire des exercices d'algorithmes et l'uns d'eux est l'affichage du nombre d'or en se basant sur la méthode de Fibonacci : Un=Un-1+Un-2 avec U1=1 et U2=1.

Rappel : Le nombre d'or correspond à (1+Racinecarrede5)/2=1,618033989

Sachant que le nombre d'or se trouve en fesant Un/(Un-1) et que l'on souhaite une précision de 0.000001 lors de l'afichage.

Cependant, je n'arrive pas à trouver la facon de m'y prendre. Quelqu'un pourrait-il m'indiquer la facon de raison, sans pour autant me donner tout l'algorithme bien-sûr (le but reste quand même que je puisse le faire moi-même ).

D'avance merci....

[Guigui_]

A priori ta suite doit être monotone (ou plutôt la suite abs(v(n+1) - v(n)) doit être décroissante et tendre vers 0 ou v est la suite qui tend vers le nombre d'or). Donc en calculant la différence de 2 termes consécutifs, dès que tu descend en dessous de 0.000001, tu peux t'ârrêter

[khayyam90]

bien le bonjour,

de par sa definition, la suite de fibonacci est tres simple a implementer de maniere recursive. Mais d'un point de vue purement pratique et economique, il est preferable de l'implenenter de maniere iterative pour ne pas avoir a calculer X fois chacne des termes.

Ainsi dans une boucle, il suffit de memoriser les 2 termes precedents. Et a chaque tour de boucle on calcule le nouvel element qui remplace le precedent. Ce precedent remplace l'avant dernier et cet avant dernier est oublie. C'est un decalage de variables

[Jedai]

bien le bonjour,

de par sa definition, la suite de fibonacci est tres simple a implementer de maniere recursive. Mais d'un point de vue purement pratique et economique, il est preferable de l'implenenter de maniere iterative pour ne pas avoir a calculer X fois chacne des termes.

Ainsi dans une boucle, il suffit de memoriser les 2 termes precedents. Et a chaque tour de boucle on calcule le nouvel element qui remplace le precedent. Ce precedent remplace l'avant dernier et cet avant dernier est oublie. C'est un decalage de variables

En fait tu peux tout à fait faire la seconde méthode en récursif (et il s'agit d'une récursion terminale, donc optimisée avec un bon langage). Par ailleurs, il y a une méthode encore plus rapide en O(log n), que tu retrouveras sans doute sur le Net.

--
Jedaï

[d-jo]

Regarde les puissances de
0 1
1 1