Fibonacci Coding | C ++ program for Fibonacci Encoding of a positive integer n ; 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 function
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  30 NEW_LINE int fib [ N ] ; int largestFiboLessOrEqual ( int n ) { fib [ 0 ] = 1 ; fib [ 1 ] = 2 ; int i ; for ( i = 2 ; fib [ i - 1 ] <= n ; i ++ ) fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] ; return ( i - 2 ) ; } char * fibonacciEncoding ( int n ) { int index = largestFiboLessOrEqual ( n ) ; char * codeword = ( char * ) malloc ( sizeof ( char ) * ( index + 3 ) ) ; int i = index ; while ( n ) { codeword [ i ] = '1' ; n = n - fib [ i ] ; i = i - 1 ; while ( i >= 0 && fib [ i ] > n ) { codeword [ i ] = '0' ; i = i - 1 ; } } codeword [ index + 1 ] = '1' ; codeword [ index + 2 ] = ' \0' ; return codeword ; } int main ( ) { int n = 143 ; cout << " Fibonacci ▁ code ▁ word ▁ for ▁ " << n << " ▁ is ▁ " << fibonacciEncoding ( n ) ; return 0 ; }