Nombre d'or

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 :wink:).

D'avance merci....

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

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

Citation:

---

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

---

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ï

Regarde les puissances de
0 1
1 1

:wink: