Discussion:Suite de Fibonacci

Cas de base (IMPORTANT)

Faites bien attention au choix de base, les premiers éléments sont : F₀=0, F₁=F₂=1, …
On pourrait choisir autre chose mais c'est cela qui a été choisi (et personnellement je trouve que c'est ce qu'il faut faire). Je corrigerai l'article lorsque j'en aurai le temps si ce n'est pas fait d'ici là. --OPi (d) 25 mars 2009 à 20:01 (CET)
(suite A000045 de l'OEIS) --OPi (d) 28 mars 2009 à 14:57 (CET)

aka

Bonjour,

Est ce que quelqu'un sait ce que signifie en anglais aka et ca dans :

Leonardo de Pisa aka. Fibonacci (ca. 1200) ?

aka=alias ?

COLETTE 7 avr 2003 à 11:45 (CEST)

Bonjour,

aka = "also known as", aussi connu sous le nom de...

Yendred 7 avr 2003 à 11:49 (CEST)

AKA = Alias Rinaldum...

Merci bien

Lillejul 31 jan 2005 à 11:27 (CEST)

"ca." en anglais, ainsi que dans plusieurs autres langues (en tous cas Allemand, Suédois et Italien) est l'abréviation pour "circa" qui veut dire "environ"

Démonstrations

Personnellement, je trouve que les démonstrations alourdissent l'article. De plus, elles ne sont que partiellement justes (récurrence forte, récurrence limitée). Je tente des mises en boites et des corrections, mais cela va prendre du temps.HB 25 juillet 2005 à 12:13 (CEST)

ca y est (ouf!). J'ai corrigé les démonstrations fausses (récurrence simple au lieu d'une récurrence d'ordre 2) Modifié certaines, déplacé quelques propriétés, en ai supprimé une (mal écrite et sans intérêt) et tout mis dans des boites (ce qui hélas empêche la jolie présentation en tableau). Le tout est à relire par quelqu'un de courageux. Personnellement je pense que toutes ces propriétés (et leurs démonstrations) n'ont pas vraiment leur place dans l'article (on n'écrit pas un traité sur la suite de Fibonacci, seulement un article) mais j'attends d'autres avis. HB 25 juillet 2005 à 19:41 (CEST)

Je me permets d'intervenir pour signaler que la démonstration du corollaire de la propriété 2, n'est pas complète. Ce n'est pas très grave mais cela choque un peu mon oeil... En effet, il est étrange que le cas n=4 n'apparaisse pas dans la démonstration. Fm|Fn ne contredit l'hypothèse que Fn est premier que dans le cas ou Fm =/= 1. Et Fm = 1 pour m = 1 ou m = 2. Ceci a des répercussion sur les n possibles. Je n'ai pas trop le temps de rédiger une correction, si quelqu'un à le temps de le faire avant moi, merci d'avance. Sinon article très intéressant. --Paradoxal (d) 14 novembre 2009 à 15:29 (CET)

j'intervient ici juste pour dire qu'en tant que non connaisseur je trouve les démontration utiles car expliquant le pourquoi du comment de la Suite de Fibonacci --PierreB49 12 janvier 2006 à 18:37 (CET)

Je trouve l'apport des démonstrations très adapté. De plus les boites permettent le "non alourdissement" de l'article. Vraiment un article de toute beauté ;) Feeder Fan 21 mai 2006 à 03:34 (CEST)

Il me semblait que l'on considerait F0=1 et F1=1 pour initialiser cette suite ???

C'est parfois défini de la sorte. Plus souvent (il me semble) par F₀=0 et F₁=1 (ou de manière équivalente par F₁=F₂=1). Personnellement je préfère "centrer" la suite en F₀=0. En effet, cela se prolongement "naturellement" dans les négatifs et l'on obtient alors F_-n=(-1)ⁿ⁺¹F_n. --OPi (d) 21 janvier 2009 à 16:40 (CET)

La lettre $\Phi$

Je trouve juste étrange que dans cet article la lettre grèque $\phi$ soit en majuscule pour désigner le nombre d'or alors que l'article sur le Nombre d'or il est écrit en minuscule. Est-ce une erreur ou y arrait-il une raison ? --PierreB49 12 janvier 2006 à 18:37 (CET)

Entièrement d'accord avec PierreB49 pour passer dans cet article $\Phi$ en $\phi$ --Claudius 13 janvier 2006 à 23:37 (CET)

Modification effectuée mais en remplaçant $\Phi$ en $\varphi$ comme dans l'article du nombre d'or. HB 14 janvier 2006 à 11:50 (CET)

Knuth dans Mathématiques concrètes utilise un phi minuscule $\ \phi$ en écriture droite. Et plutôt qu'un phi' il utilise un phi chapeau.--OPi 3 septembre 2006 à 00:48 (CEST)

Programmes

Je ne vois pas l'intérêt de donner plusieurs programmes identiques pour le calcul de la suite de Fibonacci, sachant de plus, que ces programmes sont totalement inefficaces en temps de calcul. Le programme en Caml présente quant à lui l'inconvénient d'user d'un calcul approché en flottant alors que le calcul peut être mené de façon exacte sur les entiers. Il convient donc de les enlever et ne proposer qu'un seul algorithme efficace : celui utilisant une simple boucle itérative sur des entiers. Theon 29 janvier 2006 à 21:25 (CET)

Plusieurs des programmes indiqués sont récursifs terminaux et sont strictement équivalents à une boucle. YBM 21 avril 2006 à 11:08 (CEST)

Je confirme, l'exemple Scheme est bien terminal donc de complexité equivalente à la boucle du code en C. Maintenant, l'algo présenté dans l'article n'est pas performant du tout et peut être facilement optimisé, mais ici ce n'est pas le but recherché, tout du moins je n'en vois pas l'intérêt. Feeder Fan 21 mai 2006 à 03:50 (CEST)

De plus certains programmes sont écrits dans des langages peu intuitifs si on ne les connait pas. Voilà un exemple assez parlant en Caml pour la version efficace en temps linéaire (à la Kleene). Je la trouve plus évidente que la version Scheme avec notament des notations préfixes pour les opérateurs binaires usuels. Tom 14 septembre 2006 à 15:54 (CEST)

let fibo n =
  let rec f a b = function
  | 0 -> a, b
  | n -> f b (a + b) (n - 1)
in fst (f 1 1 n);;

Pour la version « naïve » c'est encore plus intuitif en Caml :

let rec fibo = function
| 0 | 1 -> 1
| n -> fibo(n - 1) + fibo(n - 2);;

Ainsi celui qui comprend les équations récursives mathématiques comprend le programme, et vice versa. Tom 14 septembre 2006 à 15:56 (CEST)

Algorithmes de calcul des nombres de Fibonacci

je cite :

"Calculer exactement les nombres de Fibonacci à partir des puissances du nombre d'or n'est pas pratique du tout, sauf pour les petites valeurs de n, puisque les erreurs d'arrondis s'accroissent et les nombres réels flottants n'ont habituellement pas assez de précision."

JE trouve cette remarque vraiment trop peu nuancée.

Déjà, le calcul de la puissance du nombre d'or est pratique justement ! puisqu'on obtient le nombre de Fibonacci uniquement par un calcul direct, sans passer par un calcul itératif (ou programmation d'une boucle) forcément long (surtout à la main). C'est à dire, qu'avec une calculatrice de poche on peut connaître directement les valeurs que prend les nombres de Fibonacci. Si cela n'est pas pratique ! alors...?

Ensuite, la deuxième partie de l'argumentation sur la précision due aux erreurs d'arrondis, est juste, mais... il faut tout même préciser, qu'avec les 16 décimales et le système de notations scientifiques (un peu près identique pour tout PC, ou calculette) ; l'erreur commise commence qu'à partir de F(71) et "finit" à F(79) en ne dépassant jamais une différence de 2. JE dis que l'erreur fini à F(79) car ensuite le nombre de Fibonacci est trop grand, et est donc tronqué quelle que soit la méthode utilisée.

En conclusion, je pense qu'il faudrait être plus informatif (et objectif) sur le calcul avec le nombre d'or. Et préciser sa limite due aux erreurs d'arrondis. Car évacuer ce principe de calcul "d'un revers de main" alors qu'il représente le calcul le plus simple... je trouve que cela est gênant.

Je proposerai peut-être la prochaine fois une reformulation sur ce point. En attendant d'avoir des réactions polémiques ou approbatives...

Amicalement, Us.

Pour corriger les erreurs d'arrondis il peut être intéressant d'utiliser le fait que F(n) est pair ssi n est multiple de 3.

Je cite : L'implémentation récursive naïve de la relation de définition de la suite de Fibonacci n'est pas non plus judicieuse, puisque l'on calculerait de nombreuses fois les mêmes valeurs, ce qui conduit à un temps de calcul exponentiel.
Il suffit que la fonction renvoie F(n) et F(n+1). Par exemple en Scheme :

 (define (fibo n)
   (if (= n 0)
       (cons 0 1)
       (let ((fn-1 (fibo (- n 1)))
             (fn 0))
         (set! fn (cdar fn-1))
         (set! fn-1 (car fn-1))
         (cons fn (+ fn fn-1)))))

Je ne ne suis pas sur ma machine là, je le testerai plus tard, mais l'idée y est, l'algorithme est linéaire (si on ne tient pas compte des opérations faites sur les entiers bien sûr).

Je cite : ${\mathcal {F}}_{2k}={\mathcal {F}}_{k}^{2}+2{\mathcal {F}}_{k}{\mathcal {F}}_{k-1}$
${\mathcal {F}}_{2k+1}={\mathcal {F}}_{k}^{2}+{\mathcal {F}}_{k+1}^{2}$
Le temps de calcul est alors proportionnel au logarithme de n. Voici un exemple de programme en Maple.
Il faut appliquer la même idée, ainsi on obtient un algorithme de complexité logarithmique. --OPi 3 septembre 2006 à 01:17 (CEST)

Les programmes en Maple et Python qui prétendent effectuer un calcul en temps logarithmique sont en réalité de linéraires (et donc pas meilleurs que les programmes Java/Scheme/PHP qui précèdent). Pour obtenir une complexité logarithmique, il faut vraiment exploiter l'idée d'exponentiation efficace et non pas simplement les deux équations qui en sont dérivées juste après. Je peux proposer un code (ou pseudo-code correct) si les auteurs des codes Maple et Python sont d'accord avec moi. --Backtracking 15 mars 2007 à 22:04 (CET)

Primalité des nombres de Fibonacci

Attention aux cas limites ! "Si F(n) est premier alors n est premier" comporte une exception. En effet si F(n) = 3 alors n = 4. --OPi 3 septembre 2006 à 01:29 (CEST)

En effet, si n = 4 = 2 × 2 alors F(4) est divisible par F(2) mais comme F(2) = 1, être divisible par 1, c'est relativement facile... En revanche, pour n > 4, n non premier ==> n possède un diviseur strict d supérieur à 2. Comme F(d) divise F(n) et que 1< F(d) <F(n), on peut affirmer que F(n) est non premier. Par contraposée : pour tout n > 4, si F(n) est premier alors n est premier.

Article corrigé en conséquence. Merci. HB 2 octobre 2006 à 19:25 (CEST)

Généralisations

En conservant la relation de récurrence la suite s'étend naturellement aux entiers négatifs. On a alors F(-n) = -(-1)ⁿ F(n). --OPi 3 septembre 2006 à 01:29 (CEST)

C'est bien dit (mieux que moi), mais... JE tiens à faire une remarque sur la présentation de la suite concernant le niveau de lecture !

• On part d'un problème concret de Lapins, et en moins deux, on écrit des formules de matheux... Sans compter qu'à la fin de "Expression fonctionnelle" on reprend la présentation générale de la suite... c'est méli-mélo. Pour rajouter, je vois (entre autre), que dans "Bases et espaces vectoriels" on tombe sur "suite de Fibonacci généralisée" qui fait écho à la fin de l'article "Fibonacci généralisée".

• En somme, je dénonce un problème d'organisation.

• Je propose une réorganisation, suivant un plan plus progressif. Partons du problème concret, vers une présentation simple (je veux dire par là, avec un niveau de lecture et de généralité assez faible, compréhensible pour un large public), avant de passer vers les premières formules...

Je pense le faire, un peu plus tard, si personne de le fait d'ici là. En attendant des remarques polémiques ou pas...

Amicalement, Us.

pas de remarque polémique de ma part mais un franc encouragement. Réorganise, si tu vois comment faire (moi, j'en ai abandonné l'idée depuis longtemps) tant que cette réorganisation ne fait pas perdre du contenu. Bon courage --HB 26 novembre 2006 à 22:19 (CET)

Article de qualité

Pensez-vous que l'article est mûr pour passer en article de qualité? Moi je pense que oui. Valvino 1 octobre 2006 à 11:38 (CEST)

vu le caractère très sélectif des passages en article de qualité, je pense qu'il a peu de chance de jamais passer. Probablement trop technique avec de trop nombreuses formules ou démonstrations, des algorithmes qui soulèvent quelques doutes. Tout en ne sachant pas comment l'améliorer, je ne voterais surement pas pour lui. HB 1 octobre 2006 à 13:25 (CEST)

PS : L'article, très long, est incomplètement vérifié (voir dernière correction de l'erreur pourtant signalée depuis près d'un mois). HB 2 octobre 2006 à 19:27 (CEST)

Concernant:

int fibo(int n){

  if(n < 2) return n;
  return fibo(n-1) + fibo(n-2);
}

Ne serait-il pas plus judicieux d'utiliser des unsigned int? Un terme négatif n'étant pas défini...

PS: Excuser moi pour la mise en forme du code (je n'ai pas trouvé le moyen de la mettre en forme)

Exemples d'implémentation..

Bonjour, Je vois dans l'article qu'il y a des exemples dans différents langages mais ça n'apporte rien à part alourdir la page ! Exemple du PHP... Sachant qu'il y a juste au dessus un exemple en C/C++/Java, c'est presque identique, sauf qu'on a des variables $a à la place de a... Je suis pour qu'on le supprime. On va pas s'amuser à donner des exemples dans tous les langages... Dans le cas de la page Hello World, ça se comprend mais là...

Ensuite, il y avait un exemple en tcl, je l'ai commenté car il était recursif (non terminal) et il était dans la partie Algo Linéaire. Si vous n'êtes pas d'accord, libre à vous de le décommenter (mais j'aimerais en connaitre la raison). --Max81 (d) 1 mai 2008 à 15:20 (CEST)

Il faut supprimer tous les exemples, sauf un. Cette collection de programmes dans divers langages tourne au ridicule. Theon (d) 1 mai 2008 à 18:34 (CEST)

Je pense qu'une telle collectiion de programme a plutôt sa place dans un livre d'algorithimque dans wikilivre, mais pas dans wikipedia. Oxyde (d) 1 mai 2008 à 20:45 (CEST)

On est d'accord. J'ai donc supprimé les exemples en php et tcl. J'ai hésité pour Scheme. Je vous laisse le soins de prendre la décision (j'ai rien compris au code donc je sais pas si ça apporte quelque chose ou non). --Max81 (d) 2 mai 2008 à 17:47 (CEST)

Qualité du code

Je trouve que ce code pourrait servir d'exemple d'un code pas propre :

int F(int n) {
  int a;
  int b;
  int c;
  int i;
  
  a = 0;
  b = 1;

  if (n <= 1) {
    return n;
  } else {
    i = 1;
    while (i < n) {
      c = a + b;
      a = b;
      b = c;
      i = i + 1;
    }
  }
  return c;
}

Les noms de variables ne sont absolument pas explicites et il n'y a aucun commentaire. Si quelqu'un se sent inspiré pour donner des noms plus sympas... Qu'il ne se gène pas ! Personnellement, j'avoue que ce n'est pas mon point fort donc je passe mon tour :). --Max81 (d) 2 mai 2008 à 19:45 (CEST)

Choix du Python...

J'ai vu que OPi avait changé tous les exemples donnés en C ou Java vers le Python. J'aimerais bien savoir pourquoi !!! On va pas se lancer dans une guerre du quel langage est le mieux mais là je comprend pas l'intéret de la modification. Le C a quand même l'avantage d'être connu de beaucoup plus de monde que le Python (j'ai rien contre le Python). Je ne comprend pas... Le mieux serait sans doute de se limiter à du pseudo-code qui a l'avantage d'être plus pédagogique qu'une implémentation dans tel ou tel langage. --Max81 (d) 18 août 2008 à 03:32 (CEST)

Ajout a propos du choix du python :

Je trouve en effet que le python n'est pas le plus approprié pour les calculs de ce genre. Le C/Java non plus d'ailleur. Un "meilleur" language serait :un language fonctionnel, tel que le OCaml ou le Haskell. En effet, ces languages se rapprochent beaucoup plus de mathematiques.

Exemple du calcul de la suite de Fibonacci en Haskell (equivalent du premier exemple en python):

fib n 
  | n == 1 = 1
  | n == 2 = 1
  | otherwise =  (fib (n-2)) + (fib (n-1))

Pas très lisible pour les non-connaisseurs de Haskell. Que veut dire "n == 1 = 1" ? Mieux vaut du pseudo-code. Ou Python. Ou OCaml: function 0 -> 0 | 1 -> 1 | n -> fib (n-2) + fib (n-1) ...FvdP (d) 25 mars 2009 à 20:36 (CET)

il me semble au contraire que les versions procédurales sont moins proches des concepts mathématiques et ne nous obligent pas à faire l'effort de penser comme un ordinateur. Ne pourriez-vous pas proposer chacune des approches? ( C et Ocaml, python et haskell, perl et miranda ... peu importe du moment ou on ne se limite pas à un paradigme en pensant qu'il est le plus naturel) ?

voila ce pour quoi je milite ! (et pourquoi j'ai mis du forth!)

Oublié que c'est du Python et prenez le pour du pseudo-code. Il me semble que c'est parfaitement clair pour tout qui connait un langage ou l'autre. Non ? … J'ai pris le soin de commenter chaque exemple, ce qui n'était pas fait avant. Et j'ai surtout pris l'initiative de changer les programmes parce que (comme je l'ai stipulé plus haut il y a longtemps déjà, mais il est vrai pas assez explicitement) le prétendu algorithme logarithmique ne l'était pas. Dans la foulée j'ai harmonisé le tout. En ce qui me concerne je considère que tous les codes en C que j'ai vu étais ridicules car n'utilisant que les entiers primitifs du langage (unsigned int) et donc très très vite la taille de la variable est trop petite pour contenir le nombre de Fibonacci. En C l'unique code à considérer est une table de pré-calcul.
Pour ce qui est des langages fonctionnels je trouve que c'est moins clair pour les non spécialistes. De plus comme c'est presque une réécriture de la formulation mathématique je trouve cela totalement inutile.
En résumé, vous faites comme vous voulez mais je crois (présomptueusement) que vous ne ferez pas plus clair en changeant de langage. Mais surtout si vous faites des changements veillez à ce que les nouveaux algos correspondent à leur objectif. Obtenir un algo. logarithmique est un peu plus subtil que ce à quoi on pourrait s'attendre au premier abord.

--OPi (d) 29 août 2008 à 15:59 (CEST)

mouais, ben j'ai quand meme mis un exemple en forth, chaque langage a sa manière d'être apréhender et penser, ne mettre que du python c'est un peu fasciste...

Voilà une illustration classique du défaut qui consiste à présenter un programme : aujourd'hui c'est du forth, demain ce sera du C, ensuite du perl ensuite..... Dans de nombreux articles présentant un algorithme, on s'est entendu pour présenter un pseudo-code sans privilégier de langage. Ce serait mon souhait ici ==> si quelqu'un est capable de présenter un pseudocode universel, il a ma bénédiction. HB (d) 5 octobre 2011 à 14:47 (CEST)

ah ben je suis partant (btw c'est moi le forth), tu as un lien vers la syntaxe de ce pseudo code ? 15:53 le meme jour

pour une partie en pseudo-code, qui se veut le plus proche possible du langage "naturel". Cela vous convient-il ? Pour rappel, il n'existe pas de syntaxe précise pour écrire un algorithme, sinon, ça s'appelle un langage informatique... ---- El Caro ^bla 5 octobre 2011 à 16:42 (CEST)

ah, donc y a pas de nomenclature posé -ce serait a faire- mais dans le cas présent, la creation d'un meta/pseudocode langage "naturel" equivaudrait a reecrire des phrases(un peu comme ce qu'on eu certains bac+2 info/fr/), ce qui sortirait du but de cette section "algorithme linéaire" qui me semble être une demonstration claire de ce qui est linéaire. Sachant que tout le monde ne pense pas de la meme facon, il me semble juste que tout ne soit pas posé suivant la codification de pensée style Python. un peu plus tard, meme jour

Il se trouve qu'ici le rédacteur a soigneusement commenté son code python de façon que ce soit à mon avis tout aussi lisible que du pseudo-code (qui n'a pas de syntaxe bien définie, et j'en ai vu de bien moins lisible). Son but est manifestement de présenter les algorithmes de façon claire, pas d'imposer python. Il n'existe pas de pseudo-code universel, très souvent c'est du pseudo C. On peut écrire du pseudo-python, mais c'est d'un intérêt limité. A mon avis ce qui importe c'est que le but du programme soit de rendre compréhensible l'algorithme. Des langages de script modernes à la python ou ruby, avec entier de longueur arbitraire, peuvent convenir dans certains cas. On peut améliorer peut-être les commentaires, préciser les entrées par exemple. L'avantage du code c'est que ça se vérifie en s'exécutant.

Le forth, qui est particulièrement illisible, c'est je suppose une incompréhension du but d'un tel article, ou une plaisanterie (à proscrire évidemment, ce n'est pas avec forth qu'on explique un algorithme). Proz (d) 6 octobre 2011 à 23:29 (CEST)

C'est moi qui avais écrit les algorithmes en Python, je m'en étais expliqué plus haut. C'est réexpliqué dans le message qui précède. J'avais choisi Python parce que parmi les langages que j'utilise c'est un langage très courant, qui me semble clair de lui-même. L'algorithme naïf qui a été remplacé par du pseudo-code m'arrache les yeux. Je ne suis a priori pas contre l'usage d'un pseudo-code mais là c'est trop verbeux, je crois que se serait illisible dès qu'il s'agirait d'un algorithme un peu moins simple. Et quand bien même vous vous accorderiez sur un pseudo-code élégant il restera le problème qu'il ne sera pas coloré syntaxiquement, qui pour moi est éliminatoire. --OPi (d) 7 octobre 2011 à 07:55 (CEST)

Il y a dans les principes fondateurs de wikipedia ce qu'on appelle la neutralité de point de vue. Cette "neutralité" pose que Python, s'il est très respectable, ne l'est pas assez pour "écraser" d'autres langages comme le C, javascript, Java, voire php ou autres, donc écrire un "algorithme" dans un tel langage ne peut qu'amener des guerres d'édition inextricables. Tôt ou tard, quelqu'un viendra toujours contester Python ou ajouter son langage préféré.

Ecrire un algorithme en "pseudo-code", ce n'est jamais que l'écrire en français, langue dans laquelle est écrite cette wikipedia. ---- El Caro ^bla 7 octobre 2011 à 08:34 (CEST)

Praz, ce n'est la qu'une situation vue par deux points de vue, le code python m'est incomprehensible, celui en forth oui, je rejoindrais El Caro pour ne plus avoir que du pseudo code (page plus lisible?), mais dans l'idéal, un langage par pile, un langage procedural histoire d'envisager le probleme sous deux angles. Bon mon but n'est pas de faire la guerre, donc tant pis que Praz est enlevé le forth mais je le deplore... le lendemain, 12:00 ouais en plus Proz (pas praz désolé), vous avez enlevé le forth avant pendant la discussion, je dirais meme au tout debut, si c'est pas fasciste.. bref je modifie plus cette page, et mon point, c'est le meme que la personne qui a dit "procédurales sont moins proches des concepts mathématiques", en gros ca rejoint ma vision qui n'est pas la meme que la votre et ainsi, qu'on pense pas tous identique!

Je maintiens que de décrire l'algo. forth en langue naturelle ne changera rien sur le fond : c'est hors sujet sur cet article, où on ne demande même pas au lecteur d'avoir compris le principe de la pile_(informatique).

La neutralité de point de vue serait en cause s'il s'agissait d'imposer partout le même langage. Le risque me semble faible. Il n'interdit pas de se poser la question au cas par cas, il y aurait ici (illustration d'un article de math., algo très simples, fonction à croissance exponentielle) d'autres choix mais Opi a déjà donné les arguments qui font qu'aucun de ceux énumérés par El Caro ne convient, dans ce cas particulier.

L'argument "quelqu'un viendra toujours contester Python ou ajouter son langage préféré" n'est pas à négliger, on se serait peut-être épargné ce débat. Je constate quand même que depuis 3 ans ça n'a pas été le cas, et qu'il y avait des arguments immédiats de lisibilité pour l'intervention qui l'a suscité.

Il me semble que la bonne question à se poser c'est : l'algorithme est-il présenté de façon lisible et compréhensible ? Elle se pose aussi pour du pseudo-code. Ici il me semble que le but est atteint (et on peut au moins reconnaître que c'est fait proprement et dans ce sens). Evidemment ce n'est pas la seule façon possible, et si les algo. étaient décrits de façon lisible en langue naturelle, je ne verrai pas plus l'intérêt de changer. Probablement peut-on encore améliorer (par exemple pour l'algo naïf, ne suffit-il pas d'écrire un programme équationnel et de bien mettre en évidence le double appel récursif ?). A titre de comparaison : des exemples de code javascript et python qu'il ne faudrait pas inclure dans l'article correspondant ne serait-ce qu'à cause de la gestion des entrées/sortie hors sujet, qui le resterait en pseudo-code) dans Discussion:Algorithme_d'Euclide_étendu.

Je suggère de parenthéser également les couples dans le dernier programme python : je ne suis pas sûr que sinon, x, y = ... soit bien clair. Proz (d) 8 octobre 2011 à 12:44 (CEST)

Merci Proz. En effet, si je me suis permis d'intervenir dans l'article alors que la discussion avait lieu, c'était pour montrer par l'exemple l'intérêt d'écrire un algorithme en "pseudo-code", ce qui est plus rapide et efficace que de l'expliquer par écrit. Je ne l'ai fait que sur un algorithme, pour que chacun puisse juger si ça vaut le coup de passer tout l'article sous cette forme.

Plutôt que "pseudo-code", je pense qu'il faut écrire les algorithmes en français, tout simplement. On peut encore améliorer l'exemple donné, c'est certain. Le choix des // pour les commentaires peut surprendre qui n'a jamais programmé, par exemple. A mon avis, l'idéal est de décrire un algorithme de telle façon que tout lecteur parlant un français correct puisse le comprendre. L'inconvénient de Python ou de tout autre langage est qu'on s'adresse uniquement aux personnes qui ont pratiqué la programmation informatique. ---- El Caro ^bla 8 octobre 2011 à 13:28 (CEST)

Algorithme "linéaire"

L'algorithme "linéaire" de calcul de la suite de Fibonacci n'est pas réellement linéaire. Il n'est linéaire que si on considère que les opérations arithmétiques sont en temps constant, ce qui est faux en pratique dès que les nombres deviennent un peu gros. Il serait plus correct de donner une vraie complexité, basé sur les complexité des opérations sur les grands nombres, qui soit correcte pour tous les nombres de la suite et pas seulement les 79 premiers. Bluestorm (d) 12 août 2010 à 09:09 (CEST)

Algorithme "logarithmique" matriciel

Pour la nature réellement "logarithmique" des algorithmes proposés, cf. ma remarque précédente.

Une version simple d'obtenir un algorithme logarithmique à partir de la forme matricielle est d'utiliser l'algorithme d'exponentiation rapide. Cette approche ne dépend pas de spécificités de la suite, et s'adapte à de nombreux autres problèmes (par exemple les recherches de plus court chemin dans un graphe). Il serait intéressant de la développer un peu plus. Bluestorm (d) 12 août 2010 à 09:11 (CEST)

Curiosité algorithmique

Des références viennent d'être demandées pour cet ancien ajout. Je demande en plus, s'il vous plait, des explications, car je ne comprends pas le "si on le multiplie itérativement par la première fraction qui redonne un résultat entier". Anne Bauval (d) 27 septembre 2010 à 16:21 (CEST)

Quand Théon a ajouté cette section, je l'ai vérifiée et je n'ai pas jugé nécessaire, à ce moment là, de demander des sources. Maintenant la curiosité, quoique vraie, est-elle encyclopédique ? C'est là que des sources seraient nécessaires. L'algorithme en est effectivement un peu compliqué : partant d'un nombre $U_{n}=2^{F(n)}3^{F(n+1)}$, on regarde, dans la liste, la première fraction qui multipliée par U_n donne un nombre entier, il s'agit de 35/2 si F(n)>0 ou 7 si F(n)=0, on pose alors $U_{n,1}=U_{n}\times 35/2$(ou 7). On regarde de nouveau dans la liste la première fraction qui multipliée par U_{n,1} donne un entier , ce sera 11/14 si F(n)>1 ou 13/7 sinon, on pose alors $U_{n,2}=U_{n,1}\times 11/14$(ou 13/7). Et on recommence jusqu'à ce que l'on arrive à un produit d'une puissance de 2 par une puissance de 3. Le rangement astucieux des fractions et leurs numérateurs et dénominateurs respectifs permettent de transformer les puissances de 2 en puissances de 5, puis les puissances de 3 en puissances de 10 et enfin les puissances de 5 en puissances de 3.HB (d) 19 octobre 2010 à 00:00 (CEST)

Ah ! merci beaucoup. Je n'avais pas lu assez attentivement mais tant mieux car avec tes explications c'est 2 fois plus clair et ça peut servir à d'autres. Je crois que la suite suivante de fractions (plus simple) marche aussi (on change les 2 en 5 et les 3 en 7, on pose une balise alternative, puis on change les 5 en 3 et les 7 en 6) :

${\frac {3\times 13}{5\times 11}},{\frac {3\times 11}{5\times 13}},{\frac {6\times 13}{7\times 11}},{\frac {6\times 11}{7\times 13}},{\frac {1}{11}},{\frac {1}{13}},{\frac {5}{2}},{\frac {7}{3}},11$

On peut aussi optimiser en panachant les 2 méthodes. Mais à quoi bon modifier l'exemple si c'est un TI voué à la purge ? Ce n'est pas moi qui ai posé ce refnec. Je suis tiraillée ici entre l'intransigeance encyclopédiste et le plaisir mathématique. Anne Bauval (d) 22 octobre 2010 à 13:24 (CEST)

Je serais pour mettre simplement une référence à la page FRACTRAN, puis rajouter sur FRACTRAN l'exemple de cet algo, car tout ceci ne me semble avoir aucun lien essentiel avec Fibonacci. Saros (d) 5 novembre 2010 à 01:39 (CET)

Je ne sais pas trop comment mettre cet ajout en forme. L'article FRACTRAN nécessiterait, pour y insérer cet exemple, d'être étoffé, mais le principal problème est que l'algorithme décrit ici (on s'arrête dès que l'entier obtenu n'a que de des 2 et des 3) ne correspond pas exactement à celui décrit sur la page FRACTRAN en anglais (on s'arrête seulement quand on n'arrive plus à obtenir un nouvel entier). Anne Bauval (d) 5 novembre 2010 à 17:59 (CET)

Je partage l'avis de Saros : une allusion ici et un renvoi sur FRACTRAN(à développer) devrait suffire. En fait, il suffit simplement de ne pas s'arrêter dès que... mais de remarquer que dans la suite d'entiers obtenue, ceux dont la décomposition en facteurs premiers ne comprend que des 2 et des 3 ont pour exposant des nombres de Fibonacci. L'article anglais présente une suite d'entiers dans laquelle les puissances de deux obtenues ont toujours pour exposant des nombres premiers. Ce résultat me semble encore plus surprenant que celui de Fibonacci... 5 novembre 2010 à 18:21 (CET)

En effet ! ok (mais pas volontaire pour m'y coller) Anne Bauval (d) 5 novembre 2010 à 19:12 (CET)

Une modification simple de l'algo permet de retomber dans la version de l'article anglais. Il suffit d'ajouter un signal pour transférer les puissances de 2 en puissances de $5\cdot 7$, de la même façon que les 6 premières fractions. Ça donnerait genre un truc qui passe de $2^{a}3^{b}27$ à $2^{b}3^{a+b}$. Ceci dit ça n'ajoute pas grand-chose à ce qui est déjà présenté. Je veux bien me coller à la traduction de l'article FRACTRAN anglais, qui avait l'air pas trop mal. Saros (d) 6 novembre 2010 à 15:48 (CET)

Si je ne m'abuse, ces algorithmes sont loin d'être efficaces, et heureusement sont loin d'être également ceux qu'on utilise pour déterminer ce type de calcul dans le monde scientifique ! En réalité, comme pour Pi d'ailleurs, l'écriture sous forme binaire, nous fait entrevoir qu'il existe une suite logique pour déterminer les nombres de Fibonacci. je tente une explication pour ce qui ne maitrise pas bien l'informatique à ce niveau :

Nombre Fibo en binaire (pour plus de compréhension j'ai rajouté des 0) 1 0000000000000001 2 0000000000000001 3 0000000000000010 4 0000000000000011 5 0000000000000101 6 0000000000001000 7 0000000000001101 8 0000000000010101 9 0000000000100010 10 0000000000110111 11 0000000001011001 12 0000000010010000 13 0000000011101001 14 0000000101111001 15 0000001001100010 16 0000001111011011 17 0000011000111101 18 0000101000011000 19 0001000001010101 20 0001101001101101 21 0010101011000010 22 0100010100101111 23 0110111111110001 24 1011010100100000

si vous regardez simplement le dernier digit du nombre binaire sans vous soucier des autres pour le moment vous vous apercevrez qu'il varie de façon simple à partir de fibo 3 il fait "zéro, un, un, zéro, un, un etc." on dit dans ce cas que sa valeur a un cycle de 3. Ensuite regardez la valeur du digit qui précéde il suit un cycle de 6 (un, un, zéro, zéro, zéro, zéro etc.) , celle du précédent suit un cycle de 12 valeurs et celle du précédent encore suit un cycle de 24 valeurs et 2*24 pour le précédent etc. Vue qu'un ordinateur ne sait rien faire excepté ajouté ou soustraire des nombres (fermer ou ouvrir des portes logique), vous comprendrez qu'il est très facile de faire faire ce genre de calculs à un superordinateur et c'est la méthode qu'on utilise et que généralement on programme en Assembleur... --Haugure (d) 16 décembre 2011 à 11:35 (CET)

Calcul "à la louche" de F50

Faudrait détailler pourquoi c'est exactement cette précision-là (ni plus, ni moins) qu'on a besoin sur phi, car c'est assez choquant d'arrondir "à l'entier le plus proche" qui ici est supérieur, alors que d'après la formule de Binet pour n pair, F50 devrait être inférieur. Anne Bauval (d) 18 octobre 2010 à 21:50 (CEST)

pour n=50, le terme en (1/phi)^n est parfaitement négligeable (de l'ordre de 10^{-11}). L'erreur significative provient de l'arrondi sur phi qui est conduit à une erreur sur phi^50 de l'ordre de $50.\varphi ^{49}.10^{-14}$ nettement inférieur à 1/2, ce qui permet de dire que la valeur exacte correspond bien à l'entier le plus proche. Dans le cas de l'exemple, la valeur approchée de phi est par défaut donc le résultat pour phi^{50} sera inférieur à l'entier recherché. La question est "est-ce nécessaire de présenter ces calculs abscons et ne suffit-il pas de dire que l'on a pris assez de chiffres pour que, même élevé à la puissance 50, on reste proche du résultat final ?" HB (d) 19 octobre 2010 à 00:28 (CEST)

Merci beaucoup pour ces explications (j'ai honte de ne pas avoir fait ça toute seule), je pense qu'un lien suffit plutôt que ces calculs en effet "abscons". J'ai remanié un chouia dans ce sens, en déplaçant un commentaire du paragraphe "limite des quotients" vers le paragraphe contenant cette formule de Binet. Si tu veux remodifier, pas de pb. Anne Bauval (d) 19 octobre 2010 à 14:37 (CEST)

à propos des applications en musique

Je trouve la section 'applications en musique' plus qu'incomplète. Le Credo de Bach et d'autres de ses oeuvres sont partiellement construites sur cette suite, Stockhausen l'a utilisée, Xenakis, les proportions de la grille de Blues reposent sur cette suite, bref, la liste des exemples à travers l'histoire de la musique doit être assez longue pour qu'on approfondisse un peu le sujet. Sujet que je ne maîtrise pas assez pour apporter un contribution vraiment enrichissante et mathématiquement avérée, mais il faudrait que quelqu'un s'en charge!

83.201.19.203 (d) 30 janvier 2011 à 11:56 (CET)

Suite de Graham

Quand l'OEIS dit, pour  A083103, « It has not been verified », ça ne veut pas dire que ça n'a pas été vérifié, mais qu'il a été détecté que c'est faux : « Graham made a mistake in the calculation that was corrected by D. E. Knuth in 1990. » Il vaudrait peut-être mieux donner  A083104 qui, si je comprends bien, est la suite de Graham de 64 telle que rectifiée par Knuth en 90 (dans son article de 90, Knuth en a par ailleurs proposé une « meilleure », au sens où les deux premiers termes sont plus petits :  A083105). Anne (d) 28 septembre 2012 à 18:39 (CEST)

D'accord pour supprimer  A083103 qui est fausse . Mais pas d'opinion sur le remplacement par  A083104 ou  A083105 . J'ai du mal à comprendre quel pourrait être le critère de choix des exemples de suites ne donnant aucun nombre premier. En fait, je doute que les gens lise jusqu'au bout les nombres initiaux présentés et me demande si on ne pourrait pas se contenter de donner le numéro OEIS. En revanche si  A083103 est fausse, est-ce raisonnable d'écrire que l'on connait depuis 1964 des suites ne contenant pas de nombre premier ? HB (d) 29 septembre 2012 à 09:12 (CEST)

Bravo pour la modification apportée, je me creusais la tête en vain pour chercher à mettre un ordre dans les exemples. Maintenant l'exposé m'en semble plus clair. HB (d) 29 septembre 2012 à 19:18 (CEST)

Merci ! la seule info "perdue" est la factorisation des 2 premiers termes des suites de Graham et de Wilf. Je les dépose ici :

 A083103 : $2521\cdot 49993\cdot 14177095479037851751198481,3\cdot 5\cdot 84089\cdot 73919059\cdot 150031897\cdot 75754002239$

 A083216 : $2\cdot 5\cdot 5623\cdot 366~631~232~537,3\cdot 1~264~921~787~189~171$

Anne, 29/9/2012

Ce § ayant été copié-collé sans crier gare (fin 2012) dans Nombre premier de Fibonacci, je viens d'assurer la maintenance là-bas et de le remplacer ici par une loupe. Anne, 5/1/2016

Introduction

février 2013: J'ai été un peu frustré de ne pas trouver dans l'article en français, ce qu'on trouve dans les premières lignes de l'article en anglais, à savoir:

1,1,2,3,5,8,13,21,34,55,89,144,...

By definition, the first two numbers in the Fibonacci sequence are 0 and 1 (alternatively, 1 and 1), and each subsequent number is the sum of the previous two.

C'est l'information que j'étais venu chercher, rien d'autre. Et probablement beaucoup de gens venant consulter la page n'ont pas besoin d'autre chose.

Je ne tiens pas à toucher à la page moi-même, parce que les mathématiques ne sont pas mon rayon, mais ne serait-il pas préférable d'introduire de la même façon, droit au but et concis?— Le message qui précède, non signé, a été déposé par l'IP 82.226.138.116 (discuter), le 8 février 2013 à 20:46‎

Effectivement, il serait souhaitable qu'apparaissent les premiers termes de la suite dans l'introduction, ainsi que le mode de construction en langage naturel. Si pas d'avis contraire, je modifierai l'intro demain. HB (d) 8 février 2013 à 20:54 (CET)

Fait. HB (d) 9 février 2013 à 08:11 (CET)

Explications

Quelqu'un pourrait il avoir la gentillesse de nous expliquer ce que le film Jean de Florette à a voir avec la suite de Fibonacci ? Ainsi que les autres films d'ailleurs Loupiat (d) 11 avril 2013 à 16:12 (CEST)

Pas moi . Il est vrai que Jean de Florette pense devenir riche en élevant des lapins et rêve d'une croissance exponentielle de son élevage mais rien à mon souvenir sur Fibonacci. J'ai mis un bandeau demandant des sources. Et je compte supprimer dans un avenir plus ou moins proche tous les films pour lesquels on ne trouve aucune référence pour la présence de la suite de Fibonacci. HB (d) 11 avril 2013 à 19:26 (CEST)

Changement du temps d'un verbe

Dans le paragraphe "applications",dans le cadre démonstration, à côté de la spirale d'or, je propose "on considérera" à la place de "on considéra".--knifewaldo (discuter) 11 août 2013 à 13:07 (CEST)

C'est pas un changement justifiant un passage en page de discussion . Cela dit, j'ai changé la rédaction pour quelque chose de plus léger--Dfeldmann (discuter) 11 août 2013 à 14:02 (CEST)

Suite de Fibonacci dans les films (et autres)

Cette mini guerre d'édition [1], [2], [3] sur l'ajout d'un film dans lequel les suites de Fibonacci serait clairement évoquée de manière significative prouve bien que cette section sous cette forme n'a aucune raison de persister. Je pense donc que Dfeldmann (d · c · b) a eu raison de supprimer l'ajout : si on ne met pas de filtre rien n'empêche de voir la section enfler démesurément : à celui qui ajoute un film de mettre un lien vers une source justifiant sa présence. Un bandeau de demande de source est d'ailleurs apposé à cette section depuis avril 2013 et une remarque figure déjà plus haut dans la section Explications. Je compte donc supprimer de la section tous les films présentés sans source justifiant leur présence d'ici quelques jours. HB (discuter) 9 janvier 2014 à 07:50 (CET)

La véritable source n'est-elle pas le film lui-même (tout du moins lorsque la référence est explicite, ce qui est largement le cas dans Nymphomaniac)? Un film étant une oeuvre à part entière, entre dans le cadre des sources acceptables s'il est bien distribué. Vincent Lefèvre (discuter) 9 janvier 2014 à 09:40 (CET)

A mon avis non, un film est, pour le sujet, qui nous importe, une source primaire. Ainsi, figure dans la liste des films, Jean de Florette ((dans lequel on parle effectivement d'élevage de lapins mais qui, à ma connaissance ne relie pas cet élevage à la suite de Fibonacci). Qui pourra me départager face à celui qui a cru y voir la suite de Fibonacci ? Des sources secondaires.

En fait, concernant Nymphomaniac, on parle un peu pour rien car, comme tu l'as indiqué en commentaire de diff, on doit pouvoir trouver des sources secondaires pour indiquer l'importance que revet dans la peinture de Seligman, la suite de Fibonacci et comment cette intrusion dans le film semble peu appréciée par les critiques. Bref, au lieu d'un revert, une source aurait été plus judicieuse. HB (discuter) 9 janvier 2014 à 13:08 (CET)

Un autre prolème est la vérifiabilité. Dans le cas du film (contrairemnt à un roman) il n'est pas facile de contrôler la présence de la suite (sans même parler de son importance pour le scénario, ou pour le caractère de tel ou tel personnage). D'autre part, je le répète, le lecteur qui cherche des compléments sur la suite de Fionacci ne les trouvera pa, me semble-t-il, en allant voir le film, alors que le spetateur du film peut légitimement vouloir en savor plu long sur la suite ; c'est donc à Nymphomaniac que doit figuer le lien, et pas le contraire. J'ai ainsi le souvenir d'une exposition temporaire au Louvre où la suite était représentée par des tubes de néon (on y trouvait aussi des messages en toutes langues, des slogans, etc.). Si cette exposition avait eu droit à un article sur WP, il ne me serait pas venu à l'esprit de mettre un lien vers elle dans l'article sur la suite, alors que l'inverse n'aurait rien d'absurde...--Dfeldmann (discuter) 9 janvier 2014 à 13:19 (CET)

Effectivement c'est un autre point sur lequel je ne m'étais pas penchée: le pb de vérifiabilité doit être réglé par l'ajout de sources secondaires mais il reste en effet la question de pertinence. Et les arguments de Dfeldmann meritent réflexion, mais cela risque de nous entrainer loin, comma à la suppression de toutes les sections hommage dans tous les articles, si on ne définit pas des critères de pertinence assez consensuels. HB (discuter) 9 janvier 2014 à 13:31 (CET)

@HB Les sources secondaires ne sont pas forcément fiables, surtout que certains journalistes écrivent parfois des critiques de films sans avoir vu les films en question. Pourquoi tel média réputé aurait-il plus de fiabilité qu'un spectateur ayant vu le film? Pour départager, tout le monde peut rechercher sur Google, qui fournit un grand nombre de sources secondaires (pas forcément très intéressantes du point de vue contenu), et en regardant de plus près, on peut également voir qu'elles ne sont pas copiées les unes sur les autres (enfin, pour un sous-ensemble). Une source secondaire est surtout intéressante lorsqu'elle apporte des détails, afin de compléter Wikipédia. Mais je n'en avais pas trouvé. Maintenant, un nouvel article, qui aborde le côté mathématique du film et en particulier les nombres de Fibonacci (le genre d'article que je recherchais), vient de paraître sur Slate; je l'ai ajouté comme référence. Je précise qu'il correspond bien avec ce que j'ai vu dans le film (et je n'ai pas trouvé d'erreur avec ce que j'ai retenu).

@Dfeldmann Pour la vérifiabilité, roman ou film, c'est à peu près pareil: il suffit de lire/voir l'oeuvre, à condition que celle-ci soit bien diffusée, ce qui est le cas pour Nymphomaniac. Concernant les liens, ils doivent être dans les deux sens: quelqu'un intéressé par le traitement de la suite ou des nombres de Fibonacci dans les films (ou autres types d'oeuvres) se servira des liens se trouvant ici. Cependant je verrais bien un split de l'article comme sur la version anglaise, avec un nouvel article Nombres de Fibonacci dans la culture populaire, avec plus de détails qu'une simple liste d'oeuvres (comme dans la version anglaise).

Vincent Lefèvre (discuter) 11 janvier 2014 à 15:06 (CET)

Portail

Le portail maths a été remplacé par analyse le 18/5/10, et depuis le 18/10/10 il y a les deux. Je serais d'avis d'enlever celui d'analyse plutôt que celui de maths. Anne 13/11/14

Carrés de Fibonacci en spirale

Bonjour à tous, l'image qui présente les "Carrés de Fibonacci en spirale" juste au dessus du graphe "Approximation d'une spirale d'or" cloche en mon sens, car la spirale avec laquelle on détermine les Carrés de Fibonacci tourne dans l'autre sens... c'est certes peut être chipoter mais si le lecteur applique ce qui est expliqué dans la légende d'Approximation d'une spirale d'or il n'obtiendra pas le même dessin à moins qu'il ne tourne sa feuille de 180° . Pour aider à la compréhension du lecteur il serait peut être plus judicieux de les présenter dans le même sens que la spirale à la manière de l'article de langue anglaise. Ne pensez-vous pas ?--Haugure (discuter) 6 mai 2015 à 13:17 (CEST)

Euh, es-tu sûr de ce que tu dis ? la spirale sur (en) tourne dans le même sens que celle sur (fr), à savoir le sens trigonométrique, qui est bien celui usuel en maths. La seule différence est le temps d'arrêt. Kelam (mmh ?) 6 mai 2015 à 15:14 (CEST)

Euh tu as raison Kelam en réalité c'est juste un effet d'optique il manque 13 et 21 dans la représentation française ce qui m'a choqué au premier abord mais suite à ta remarque j'ai vérifié et je ne devais pas être bien attentif tout à l'heure ! merci de m'avoir lu --Haugure (discuter) 6 mai 2015 à 15:54 (CEST)

Développement binomial de la formule de Binet

J'aurais bien ajouté ça mais pas trouvé de source :

$\forall n\in \mathbb {N} \quad {\mathcal {F}}_{n}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)={\frac {1}{2^{n-1}}}\sum _{0\leq k\leq (n-1)/2}{n \choose 2k+1}5^{k}$.

Anne, 7/9/16

Décidément, comme on se retrouve (et au passage, bonne année, Anne)  : je me préparais à l'ajouter, ainsi que la formule analogue pour les nombres de Lucas :

$\forall n\in \mathbb {N} \quad {\mathcal {L}}_{n}=\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)={\frac {1}{2^{n-1}}}\sum _{0\leq k\leq n/2}{n \choose 2k}5^{k}$.

Mais elles devraient être dans Concrete Mathematics, non ? Bon, après contrôle, ta formule y est bien (chapitre 6, exercice 47, page 314), mais pas la mienne😕, et j'y ai appris au passage que Binet n'a fait que redécouvrir un résultat d'Euler de 1765 (E326, Opera Omnia, série 1, volume 15, pages 50-69).--Dfeldmann (discuter) 10 janvier 2017 à 22:46

Bonjour et bonne année ! Voici qq refs de plus : Vajda démos p. 68-69 ou Koshi exos p. 162 (F_n et L_n), Catalan exo p. 86 (F_n, avec un décalage d'indice). Benjamin et Quinn p. 130-131 (p. 131 hélas inaccessible) (F_n : identité 235, et — paraît-il — L_n identité 237) Anne, 11/1/17 à 3 h 11

Algorithme récursif terminale : le code donné est en n²/2

Bonjour, je ne sais ce que tente vraiment de montrer cette section, à part une manière qui marche pour calculer fibo(n), mais la phrase De manière équivalente a l'algorithme linéaire, on peut écrire une fonction récursive terminale. fait un peu flop car, si on lance ce code, en terme de temps de calcul on est en n²/2 (pour n=50, on appelle 1275 fois la méthode "fibonacci(int n, long a, long b)") ce qui est évidemment exécrable vu qu'on peut descendre en n étapes. Le soucis est dans l'enchaînement des trois méthodes. Si vous voulez tester (code caché sous cette boîte déroulante "Démonstration" car je sais plus comment on fait autrement ^^):

Démonstration

public class Fibonacci {

   public static int count = 0;                                // Test compteur

   // On affiche les 50 premiers termes
   public static void main(String[] args) {
       for (int i = 0; i < 50; i++) {
           System.out.println(fib_init(i));
       }
       System.out.println("le nombre de passage dans la méthode fibonacci(int n, long a, long b) est : "+count);   // Test compteur
   }

   // Algorithme récursif terminale
   public static long fibonacci(int n, long a, long b) {
       count++;                                                // Test compteur
       if (n > 0) {
           return fibonacci(n - 1, b, a + b);
       } else {
           return a;
       }
   }
   
   // On lance le calcul en initialisant 
   // les 2 premiers termes de la suite 0 et 1
   public static long fib_init(int n) {
       return fibonacci(n,0,1);
   }
   

}

Bon, on peut tenter d'améliorer le code (mettre l'affichage dans "fib_init(int n)" qui elle est bien linéaire) mais qu'est-ce qui est souhaité dans cette section ? --Epsilon0 ε₀ 5 janvier 2017 à 15:07 (CET)

Je pense qu'il vaut mieux se fier à une source (un livre par exemple), plutôt que d'essayer de réinventer la roue ici. J'ai modifié un peu cette section en faisant référence à Cormen et al. et Dasgupta et al. Si vous avez d'autres livres pour appuyer vos propos, n'hésitez pas à les ajouter ! Bonne soirée. Fschwarzentruber (discuter) 12 octobre 2019 à 22:28 (CEST)

Différences successives et transformation binomiale

Il ne me semble pas avoir vu dans l'article de mention sur les différences successives : il est facile de prouver que $(\Delta ^{k}{\mathcal {F}})_{n}={\mathcal {F}}_{n-k}$ et donc que la transformation binomiale de la suite de Fibonacci est $-{\mathcal {F}}$. Enfin si je ne me trompe pas.... Il serait peut-être intéressant de trouver une source et de mettre cela dans l'article. 78.250.217.201 (discuter) 28 mai 2018 à 15:51 (CEST)

Complexité des différents algorithme de calcul

Bonjour, Les complexités annoncées des algorithmes "linéaire" et "logarithmique" le sont effectivement en fonction de la représentation unaire de n, il ne serait pas plus juste de dire "exponentiel" et "linéaire" respectivement puisque en général n est codé en base non unaire ? — Le message qui précède, non signé, a été déposé par Wingx234 (discuter), le 29 octobre 2018 à 12:57‎.

n est codé en binaire dans ces algorithmes. Ces algorithmes sont donc exponentiels (mais c'est normal vu que le n-ème terme possède THETA(n) chiffres, donc... il faut le temps de les écrire. J'ai étoffé un peu cette partie. Fschwarzentruber (discuter) 12 octobre 2019 à 22:26 (CEST)

Définition plus générale...

«Elle commence par les termes 0 et 1 (on trouve des définitions[réf. nécessaire] qui la commencent avec 1 et 1)»

Je cite l'article. Mais il me semble que si l'on commence par deux nombres quelconques, mettons, 3 et 100, on obtient toujours une suite de Fibonacci; dans mon exemple: 3, 100,303, 403, 706, 1109, etc. Suite dont les propriétés sont les mêmes que celles de la suite commençant par 0 et 1. D'où je pense que la définition de la suite de F. devrait stipuler qu'elle peut commencer par deux nombres QUELCONQUES. Réflexion d'un petit matheux de base, qui attend de lire les uns et les autres et accepte les critiques ! Michel en Chautagne--84.4.2.222 (discuter) 18 octobre 2019 à 21:20 (CEST)

Avec Wikipédia, il faut toujours fournir des sources. Dans le cas où l'on part avec deux nombres quelconques, s'il y a des sources, ça passe. --Pierre de Lyon (discuter) 18 octobre 2019 à 21:35 (CEST)

Merci de votre réponse rapide ! Je n'ai pas de sources. Mais je me suis amusé, à partir, tenez, de mon exemple, 3 et 100, à calculer le rapport de deux nombres successifs et au fur et à mesure que l'on progresse, on aboutit inéluctablement à tendre vers le Nombre d'Or. Ça n'est pas une PREUVE mais un constat empirique ! La parole est maintenant aux vrais matheux. Bien à vous. Michel--84.4.2.222 (discuter) 18 octobre 2019 à 21:46 (CEST)

En fait, ce cas est traité dans wikipédia dans l'article Généralisations des nombres de Fibonacci section Modification des termes initiaux. --Pierre de Lyon (discuter) 18 octobre 2019 à 21:58 (CEST)

Merci ! je n'ai plus rien à ajouter. Michel--78.122.119.28 (discuter) 19 octobre 2019 à 08:05 (CEST)

Diagramme en barres

Bon, pour l'instant, j'ai supprimé Le diagramme en barre a été supprimé parce qu'on ne peut pas laisser subsister un diagramme faux et qu'il est clair que dans ce diagramme u_12 + u_13 ne donne pas u_14.

Mais d'autres problèmes apparaissent :

• en lecture u_9 vaut environ 20 alors que dans le tableau c'est u_8 qui vaut 21
• le titre devrait porter 2 majuscules : Suite de Fibonacci

Mais avant de demander à Florentin de retravailler son diagramme, je voudrais prendre le pouls de la communauté sur l'opportunité d'un tel diagramme. HB (discuter) 5 décembre 2019 à 21:06 (CET)

Il y a aussi une erreur dans le nom du fichier : "Suite_de_fibanacci". Un dessin pour illustrer la croissance exponentielle ça pourrait être bien, mais pas pour illustrer les valeurs puisque ça explose de suite. --OPi (discuter) 5 décembre 2019 à 21:58 (CET)

Même avis. De plus, ce sont les premières valeurs qui sont le plus utilisées. Quand on les voit apparaître dans une situation, on conjecture que la suite de Fibonacci n'est pas loin. Or le diagramme écrase ces premières valeurs. Theon (discuter) 6 décembre 2019 à 09:45 (CET)

Proposition d'anecdote pour la page d'accueil

Une anecdote basée sur cet article a été proposée ici (une fois acceptée ou refusée elle est archivée là). N'hésitez pas à apporter votre avis sur sa pertinence, sa formulation ou l'ajout de sources dans l'article.
Les anecdotes sont destinées à la section « Le Saviez-vous ? » de la page d'accueil de Wikipédia. Elles doivent d'abord être proposées sur la page dédiée.
(ceci est un message automatique du bot GhosterBot le 16 mai 2020 à 09:47, sans bot flag)

Date de la formule de Binet

Bon, l'information est peut-être dispensable, d'autant plus que l'article sur Binet (non sourcé) dit que la formule était déjà connue avant lui. Les dyslexiques sont de la partie avec un même site capable de donner sur la même page tantôt 1843, tantôt 1834[4].

Math doc cite

Binet J. [1843] Note sur la détermination de l'intégrale eulérienne binôme $\int _{0}^{1}x^{p-1}dx(1-x)^{q-1}$ dans le cas où l'un des arguments p ou q est un nombre rationnel. Comptes Rendus des Séances de l'Académie des Sciences. Paris. n°16, 377-381[5].

Mais le tome 16 qui figure sur Gallica (mal scanné) ne présente pas cette note de Binet mais une autre:

Mémoire sur l'intégration des équations linéaires aux différences finies d'un ordre quelconque, à coefficients variables

où apparait bien, page 563 la formule en question

Mathdoc ne donne aucun papier de Binet datant de 1834. Je continue à chercher... HB (discuter) 25 mai 2021 à 20:02 (CEST)

Propriétés: démonstrations ou liens consultables

Bonjour,

J'ai entrepris de vérifier que pour chaque propriété mentionnée dans le chapitre "propriétés", on puisse avoir soit (au moins) une démonstration explicite, soit un lien fonctionnel vers un ouvrage ou une référence en contenant une. Merci à Robert FERREOL d'avoir apposé un bandeau d'alerte, ce que j'avais oublié de faire.

Je fais mes modifications proposition par proposition pour permettre à chacun de les suivre, et éventuellement les commenter/rectifier/compléter. Olinone (discuter) 5 février 2023 à 11:04 (CET)

J'ai fini de vérifier que touts les propriétés sont bien accompagnées soit d'une démonstration , soit d'un lien opérationnel vers un démonstration réellement consultable. Olinone (discuter) 7 février 2023 à 16:30 (CET)

Divisibilité: compléments proposés

Bonjour, je propose de compléter le chapitre "divisibilité" par le contenu suivant (qui serait évidemment mis sous forme mathématique en cas d'accord), et constituerait un premier sous chapitre intitulé : "Propriétés simples et densité"

Voici le texte proposé :

"La propriété 6 montre que $F_{n}$ divise bien tous les $F_{nk}$.

Démontrons que la réciproque est vraie: $F_{p}$ n'est divisible par $F_{n}$que si $p=nk$.

Posons : $p=nk+r$, avec $0<=r<n$.

La propriété 2 donne: $F_{p}=F_{nk}*F_{r+1}+F_{nk-1}*F_{r}$.

Dire que F(n) divise F(p) revient à dire que F(p) divise F(nk-1)*F(r), car F(n) divise F(nk). Or, d'après la propriété 8 F(nk) et F(nk-1) sont premiers entre eux. Donc F(n) est premier avec F(nk-1). Il faut donc que F(p) divise F(r), qui est plus petit que lui. Donc F(r)=0 et r=0. Donc p=nk.

Conséquences sur la divisibilité au sein de (Fn): F(n) divise F(m) si et seulement si m=kn.

Conséquences sur la densité dans (Fn) :

F(3)=2, donc les seuls nombres pairs dans (Fn) sont ceux de rang n=3p et la densité de nombres pairs dans (Fn) est de 1/3 (contre 1/2 dans N)

F(4)=3, donc les F(n) avec n=4p sont les seuls multiples de 3 dans (F(n)) , et la densité de nombres multiples de 3 dans (Fn) est de 1/4 (contre 1/3 dans N)

F(5)=5, donc les F(n) avec n=5p sont les seuls multiples de 5 dans (F(n)) , et la densité de nombres multiples de 5 dans (Fn) est de 1/5 (comme dans N)

F(6)=8, donc les F(n) avec n=6p sont les seuls multiples de 8 dans (F(n)) , et la densité de nombres multiples de 8 dans (Fn) est de 1/6 (contre 1/8 dans N),

Et, plus généralement les seuls multiples de F(n) dans (Fn) sont les F(nk), et la densité des nombres multiples de F(n) dans (Fn) est de 1/n."

Le contenu actuel de la section deviendrait le deuxième sous chapitre intitulé "Propriétés générales"

Merci de votre avis avant action.

Cdlt Olinone (discuter) 9 février 2023 à 07:51 (CET)

La question posée par cette proposition est double

• Où s'arrêter dans la liste des propriétés?
• Quelle est la valeur des démonstrations personnelles sur WP ?

Sur le premier point, je crains une inflation dans cet article préjudiciable à sa lisibilité. J'ai, pour ma part, abandonné depuis longtemps le suivi de cet article: trop d'infos tue l'info. Et il suffit de voir l'index des sujets sur fq.math et leur liste de publications pour voir que, sans frein éditorial, on peut continuer à gonfler l'article ad libitum.

Sur le second point, je ne suis plus favorable à la présence des dems pour un pb de validation. Tout le monde peut commettre une erreur de raisonnement et nous sommes trop peu de personnes qualifiées (?) pour les relire.

La réponse à ces questions est simple: des sources. Parmi les milliers de propriétés concernant la suite de Fibonacci, quelles sont celles reprises par des ouvrages synthétiques secondaires? En se limitant à ces propriétés-là, on aurait alors une validation sur leur pertinence et sur leur exactitude. (Mais cela dépasse le cadre de ta simple proposition Olinone)

Ceci n'est qu'un avis en passant, puisque, comme annoncé plus haut, j'ai passé la main depuis longtemps sur cet article. HB (discuter) 9 février 2023 à 09:08 (CET)

Bien d'accord avec HB !

Le paragraphe Suite de Fibonacci#Divisibilité des nombres de Fibonacci est déjà assez indigeste !

Et je transférerais bien les propriétés 6,7, 8 du paragraphe sur les propriétés , qui est une peu un inventaire à la Prévert, en tête de ce paragraphe, puisque ce sont des propriétés de divisibilité, et mettrais la suite en boite déroulante comme compléments... Robert FERREOL (discuter) 9 février 2023 à 10:05 (CET)

Je comprends, et partage, le raisonnement de votre réponse sur les 2 points que vous évoquez.

Donc, sauf si je trouve une référence sur la divisibilité à m'intérieur de (F(n)), je n'introduirai pas la propriété de divisibilité que j'ai évoquée (pour éviter de ne se reposer que sur une démo "personnelle")

Sur le paragraphe propriétés, je suis d'accord pour ne pas participer à une inflation qui pourrait s'avérer contre-productive. Je propose de regrouper vos 2 ajouts dans la liste existante. Olinone (discuter) 11 février 2023 à 12:03 (CET)

Voilà, j'ai fait le regroupement annoncé. J'hésite à me lancer dans une restructuration plus importante de la section "Propriétés" car il y a des liens entre certaines des parties . Olinone (discuter) 12 février 2023 à 11:01 (CET)

Remplacer « terme » par « nombre »

@Fschwarzentruber @Robert FERREOL Je pense que remplacer « terme » par « nombre » aurait peut-être nécessité une discussion ici. Ça peut donner des expressions

• « le nombre général de la suite de Fibonacci s'exprime à l'aide du nombre d'or »
• « le nombre $F_{n}$ de la suite de Fibonacci est donné par $F_{n+2}=F_{n+1}+F_{N}$ ».

L'expérience personnelle ne remplace pas l'expérience collective et la discussion. Les mathématiciens ont parlé de terme générale d'une suite ou d'une série, avant que les logiciens emploient ce terme pour désigner une expression formelle. Pierre Lescanne (discuter) 23 septembre 2023 à 12:53 (CEST)

Je reste fidèle à l'idée d'une progressivité dans les difficultés et la technicité d'un article. Je trouve donc tout-à-fait bienvenue l'idée de déjargonniser le résumé introductif de l'article et de passer ensuite progressivement du mot «nombre» générique, au mot «terme» plus technique, même si une expression comme « chaque nombre est la somme des deux nombres qui le précèdent » parait bizarre à mes yeux de prof.

Je suis en revanche tout-à-fait défavorable à toute généralisation de remplacement de terme par nombre dans le corps de l'article comme celles que PIerre.Lescanne caricaturise à dessein. Mais je ne pense pas que ce soit le projet de Fschwarzentruber. HB (discuter) 23 septembre 2023 à 14:19 (CEST)

Bonjour, merci pour vos commentaires et merci pour avoir lancer la discussion. Le remplacement de "terme" par "nombre" ne concerne que le tout début du paragraphe introductif, afin de faciliter sa compréhension par tout le monde. En revanche, je suis aussi tout à fait défavorable à remplacer le mot "terme" par "nombre" dans le reste de l'article. Fschwarzentruber (discuter) 24 septembre 2023 à 08:57 (CEST)

Bonjour, Il me semble évident qu'il ne faut pas remplacer partout : on doit bien parler de « terme d'une suite », car « nombre d'une suite » n'a aucun sens, que je sache. Donc simplifier pour rendre accessible au pus grand nombre, je suis pour, mais pas au sacrifice du minimum de rigueur exigé. Kelam (discuter) 25 septembre 2023 à 09:43 (CEST)

Je souscrit à ce que vous avez écrit. Mais le débat permet de rendre les choses très claires. --Pierre Lescanne (discuter) 25 septembre 2023 à 12:15 (CEST)

Section « Applications → Linguisitque » (travail inédit)

En français, soit $n\in \mathbb {N} ^{*}$ le nombre de syllabes écrites finissant par un e caduc à la suite, le nombre de prononciations possibles sera $F_{n+2}$.

Par exemple, il y a 13 façons de prononcer la phrase « Il parlait de le redevenir. », qui en contient 5 :

Il parlait de le redevenir.
Il parlait de le redev_nir.
Il parlait de le red_venir.
Il parlait de le r_devenir.
Il parlait de le r_dev_nir.
Il parlait de l_ redevenir.
Il parlait de l_ redev_nir.
Il parlait de l_ red_venir.
Il parlait d_ le redevenir.
Il parlait d_ le redev_nir.
Il parlait d_ le red_venir.
Il parlait d_ le r_devenir.
Il parlait d_ le r_dev_nir.

Cette liste exclut des formes telles que « Il parlait de le r_d_venir. » dans lesquelles deux e caducs consécutifs sont omis, bien que techniquement prononçables en raison du fait que la lettre r ait des propriétés rendant l’enchainement -rdv- possible, contrairement à « Il parlait d_ l_ redevenir. », puisque l’enchainement -dlr- est impossible.

En suivant cette logique, la phrase hypothétique « Il pensait que de ne le redevenir l’aiderait. », qui contient 7 syllabes écrites finissant par un e caduc à la suite, peut être prononcée de 34 façons différentes, car $F_{7+2}=34$. Loÿs Lacroix (discuter) 27 décembre 2023 à 18:50 (CET)

Bonjour,

Oui, complètement inédit en tant qu'application linguistique. Mais noter qu'il y a une équivalence évidente avec le problème bien connu de l'escalier: là, là, là, et là, par exemple. Ici, la règle est qu'on ne peut pas sauter deux e consécutifs, et pour l'escalier, la règle est qu'on ne peut pas sauter deux marches consécutives.

Cordialement,

Vincent Lefèvre (discuter) 27 décembre 2023 à 21:25 (CET)

Et dans l'article actuel, c'est couvert par la section Interprétations combinatoires, qui donne 2 autres exemples équivalents à ces problèmes. — Vincent Lefèvre (discuter) 27 décembre 2023 à 21:47 (CET)

Mais oui ! Le lien est très clair, maintenant. Qui plus est, je connaissais déjà cette vidéo de Micmaths, et donc le problème de l’escalier. Merci ! Loÿs Lacroix (discuter) 29 décembre 2023 à 08:58 (CET)