読み方 ： フィボナッチすうれつ

概要

名称は13世紀イタリアの数学者、レオナルド・フィボナッチ（Leonardo Fibonacci）に由来する。彼が1202年に著した『Liber Abaci』（算盤の書）の中で、ウサギの繁殖を題材にした問題を解く過程でこの数列を紹介したことで広まった。ただし、同じ数列はそれ以前にインドの詩律論の研究者によっても発見されていた記録がある。

この数列の定義は漸化式で表される。F（1） = 1、F（2） = 1とし、n≧3 のとき F（n） = F（n-1） + F（n-2） である。ビネの公式によって一般項を式で表すこともでき、定数 φ = （1+√5）/2 （これを黄金比という）を使って F（n） = （φⁿ - （-φ）⁻ⁿ） / √5 と書ける。隣り合う項の比 F（n+1） / F（n） は、nが大きくなるにつれ黄金比 φ = 1.618… に収束する。

自然界では、ヒマワリの種の螺旋の本数、松ぼっくりの鱗の並び、花びらの枚数などにフィボナッチ数が現れることが観察されている。これは成長過程で隣接する要素が最も効率よく充填される配置が自然に生まれることに起因すると説明されている。

コンピュータ科学の分野では、フィボナッチ数列の計算がアルゴリズムの学習教材として定番の題材となっている。単純な再帰実装では同じ計算が指数的に繰り返されるため、メモ化や動的計画法によって計算済みの値を再利用する手法の説明によく使われる。また、「フィボナッチヒープ」と呼ばれるデータ構造はダイクストラ法などのグラフアルゴリズムで用いられ、特定の操作の計算量を抑えられることが知られている

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。