Information on Fibonacci Sequences
A Fibonacci sequence is a recursive sequence which has starting
values F0 = 1 and F1 = 1,
recursive formula Fn = Fn - 1 + Fn -
2. It is usually represented by a 0-1
string where the substring 11 cannot occur. This is the first
representation given by COS. The second representation we call the
Stair-Stepping representation. Each of the outputs in the second
representation corresponds to a series of 1 or 2 steps taken on n +
1 stairs. The third representation in COS gives Reflection
diagrams which represent the different ways in which a beam of light can
reflect through two panes of glass placed back to back. A reflection may
the edge of the glass, or it may occur where the panes meet, but the beam
cannot reflect where the panes meet twice in a row. Thus, this
corresponds to the 0-1 strings.
COS can generate Fibonacci sequences in either lexicographic(lex)
in a Gray Code order. To generate in lex order, input a value for n and
none for k. To generate in a Gray Code order, input a value for n and a
nonzero value for k.
The algorithm used by COS is a recursive backtracking algorithm.
The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 4041 visitors to this page since May 16, 2000
©Frank Ruskey, 1995-2003.