AnO(1) time algorithm for generating Fibonacci strings
Kenji Mikawa, Ichiro Semba · Electronics and Communications in Japan (Part II Electronics) · 2005
When all strings composed of 0 and 1 which do not contain a substring 11 are considered, their total number is equal to a Fibonacci number. In this paper, these strings are called Fibonacci strings. This paper discusses the generation of a list which is composed of all Fibonacci strings. In the list defined in this paper, the adjacent Fibonacci strings differ by only a character. Methods of generating such a list recursively have already been presented by Hsu [5] and Squire [11], but no method is yet known by which any string can be generated sequentially in O(1) time. In this paper, Takaoka's method [12], in which the tree representing the list structure is iteratively scanned, is improved, and a method is presented by which each string of the list can be generated in O(1) time in the worst case. This method requires a memory capacity of order O(n). © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 88(9): 67–72, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20209