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)