フィボナッチ列のO(1)時間生成について(<小特集>LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
スポンサーリンク
概要
- 論文の詳細を見る
部分列11を含まない0と1からなる文字列をすべて並べるとき,その総数はフィボナッチ数に一致する.以下,この文字列をフィボナッチ列と呼ぶことにする.本論文では,すべてのフィボナッチ列を一つずつ含むようなリストを生成する方法について考える.本論文で定義されるリスト上の連続するフィボナッチ列は1文字だけが異なるように並ぶ.このようなリストを再帰的に生成する方法は既にHsu[5]やSquire[11]によって示されたが,逐次的にどの文字列もO(1)時間で生成する方法は知られていない.リストの構造を表す木を反復的に走査する高岡の方法[12]を改良し,リストの各文字列を最悪の場合でもO(1)時間で生成する方法を与える.この方法はO(n)記憶容量だけを必要とする.
- 社団法人電子情報通信学会の論文
- 2002-02-01
著者
関連論文
- Generation of $k$-permutations in $0$(1) time per permutation by reversing sublists (Models of Computation and Algorithms)
- 自然数の組成のO(1)時間生成について (計算機科学基礎理論の新展開)
- たかだか4文字の交換による撹乱順列の生成について(LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集)
- フィボナッチ列のO(1)時間生成について(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 反復型アルゴリズムによるフィボナッチ列の生成について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 部分リストの反転によるk-順列の生成について(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- 高々2回の交換によるカッコ列の高速生成法 (アルゴリズムと計算の理論)
- 組合せ問題の論理関数による解法について(計算機構とアルゴリズム)
- ネットワーク上のバックトラックアルゴリズム(計算理論とその応用)
- ブール処理のパズルへの応用(アルゴリズムと計算量理論)
- チェス盤上の配置問題について(計算量理論)