Information on Fibonacci Sequences

A Fibonacci sequence is a recursive sequence which has starting values F0 = 1 and F1 = 1, and 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 occur at 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) order or 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.




It was last updated .