Fibonacci coding
From CodeCodex
Code for encoding and decoding integers using Fibonacci coding.
Python[edit]
Print the encodings (and subsequent decodings) of the numbers one through twenty. This program assumes that the function fibonacci(n) is available and returns the nth number in the fibonacci sequence.
def encode(x): "Returns the fibonacci encoding of the integer `x'" R = [] i = 0 while fibonacci(i) < x: i += 1 while x > 0: if fibonacci(i) <= x: R.append(i) x -= fibonacci(i) i -= 1 retv = "" for i in range(max(R) + 1): if i in R: retv += '1' else: retv += '0' retv += '1' return retv def decode(x): "Returns the fibonacci decoding of the string `x'" retv = 0 for i in range(len(x) - 1): if x[i] == '1': retv += fibonacci(i) return retv if __name__ == "__main__": for i in range(1,21): f = encode(i) j = decode(f) print "%2d %-8s %2d" % (i, f, j)