An O(1) Time Algorithm for Generating Fibonacci Strings(<特集>Special Issue on Selected Papers from LA Symposium)
スポンサーリンク
概要
- 論文の詳細を見る
We discuss the problem of generating a list of all Fibonacci strings of length n which do not contain the substring 11. We show that the list contains all Fibonacci strings so that each string differ from its predecessor by a fixed number of bits. Hsu and Squire have developed recursive generation algorithms for such the list indepedently, but there is no algorithm in an iterative manner. We present an iterative algorithm which generates each string of the list in O (1) time in the worst case and requires only O (n) space. This algorithm can be adapted to other combinatorial generation problems.
- 社団法人電子情報通信学会の論文
- 2002-02-01
著者
-
Semba Ichiro
Department Of Computer Science Ibaraki University
-
Mikawa Kenji
Department Of Computer Science Ibaraki University
関連論文
- Immunohistochemical Analysis of Cell Proliferation and Suppression of Ameloblastoma with Special Reference to Plexiform and Follicular Ameloblastoma
- Genetic Controls of Susceptibility and Resistance to 4-Nitroquinoline 1-Oxide-induced Tongue Carcinomas in Rats
- Specificities of the Early Body Formation in the Lancelet Embryo
- Expressions of junB and c-fos are enhanced in 4-nitroquinoline 1-oxide-induced rat tongue cancers
- Generation of Permutations by Using an Input Restricted-deque or an Output Restricted-deque
- Generation of Stack Sequences in Lexicographical Order
- 10. BMP4 induce ectopic cartilage formation in the mouse embryonal mandibular process : BMP4 mediates Msx2 and Sox9 expression during chondrogenesis.
- Generation of Permutations by Using a Stack or a Queue
- An Efficient Algorithm for Generating all Partitions of the Set{1, 2, ..., n}
- A Note on Enumerating Combinations in Lexicographical Order
- Systematic Method for Determining the Number of Multiplications Required to Compute x^m, Where m is a Positive Integer
- On Generating and Counting All the Longest Increasing Subsequences
- An O(1) Time Algorithm for Generating Fibonacci Strings(Special Issue on Selected Papers from LA Symposium)
- Generation of Binary Trees from Stack Permutations