Fibonacci Coding | To limit on the largest Fibonacci number to be used ; Array to store fibonacci numbers . fib [ i ] is going to store ( i + 2 ) 'th Fibonacci number ; Stores values in fib and returns index of the largest fibonacci number smaller than n . ; Fib [ 0 ] stores 2 nd Fibonacci No . ; Fib [ 1 ] stores 3 rd Fibonacci No . ; Keep Generating remaining numbers while previously generated number is smaller ; Return index of the largest fibonacci number smaller than or equal to n . Note that the above loop stopped when fib [ i - 1 ] became larger . ; Returns pointer to the char string which corresponds to code for n ; allocate memory for codeword ; index of the largest Fibonacci f <= n ; Mark usage of Fibonacci f ( 1 bit ) ; Subtract f from n ; Move to Fibonacci just smaller than f ; Mark all Fibonacci > n as not used ( 0 bit ) , progress backwards ; additional '1' bit ; return pointer to codeword ; Driver Code
N = 30 NEW_LINE fib = [ 0 for i in range ( N ) ] NEW_LINE def largestFiboLessOrEqual ( n ) : NEW_LINE fib [ 0 ] = 1 NEW_LINE fib [ 1 ] = 2 NEW_LINE INDENT i = 2 NEW_LINE while fib [ i - 1 ] <= n : NEW_LINE INDENT fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] NEW_LINE i += 1 NEW_LINE DEDENT return ( i - 2 ) NEW_LINE DEDENT def fibonacciEncoding ( n ) : NEW_LINE INDENT index = largestFiboLessOrEqual ( n ) NEW_LINE codeword = [ ' a ' for i in range ( index + 2 ) ] NEW_LINE i = index NEW_LINE while ( n ) : NEW_LINE INDENT codeword [ i ] = '1' NEW_LINE n = n - fib [ i ] NEW_LINE i = i - 1 NEW_LINE while ( i >= 0 and fib [ i ] > n ) : NEW_LINE INDENT codeword [ i ] = '0' NEW_LINE i = i - 1 NEW_LINE DEDENT DEDENT codeword [ index + 1 ] = '1' NEW_LINE return " " . join ( codeword ) NEW_LINE DEDENT n = 143 NEW_LINE print ( " Fibonacci ▁ code ▁ word ▁ for " , n , " is " , fibonacciEncoding ( n ) ) NEW_LINE