Every non-negative integer can be represented as the sum of distinct positive Fibonacci numbers. (As a warmup exercise, prove this claim!) In other words, instead of a string of bits, we can represent any non-negative integer as an string of fits, where the $i$th least significant fit indicates whether the sum includes the Fibonacci number $F_i$. For example, the fitstring $101110_F$ represents the number $F_6+F_4+F_3+F_2 = 8+3+2+1 = 14$.
Describe algorithms to increment and decrement a fitstring in constant amortized time. That is, starting with the all-zero fitstring, your algorithms must execute any intermixed sequence of $n$ increments and $m$ decrements in $O(n+m)$ time, yielding a fitstring with value $n-m$.
[Hint: Most numbers can be represented by more than one fitstring!]
Posted: Jun 06 '12
Seen: 73 times
Last updated: Jun 06 '12
