The Fibonacci Word may be created in a manner analogous to the Fibonacci Sequence as described here:
- Define F_Word1 as 1;
- Define F_Word2 as 0;
- Form F_Word3 as F_Word2 concatenated with F_Word1 i.e “01”
- Form F_Wordn as F_Wordn-1 concatenated with F_wordn-2
For this task we shall do this for n = 37. You may display the first few but not the larger values of n, doing so will get me into trouble with them what be (again!).
Instead create a table for F_Words 1 to 37 which shows:
- The number of characters in the word
- The word’s Entropy.
#include <string> #include <map> #include <iostream> #include <algorithm> #include <cmath> #include <iomanip> double log2( double number ) { return ( log( number ) / log( 2 ) ) ; } double find_entropy( std::string & fiboword ) { std::map<char , int> frequencies ; std::for_each( fiboword.begin( ) , fiboword.end( ) , [ & frequencies ]( char c ) { frequencies[ c ]++ ; } ) ; int numlen = fiboword.length( ) ; double infocontent = 0 ; for ( std::pair<char , int> p : frequencies ) { double freq = static_cast<double>( p.second ) / numlen ; infocontent += freq * log2( freq ) ; } infocontent *= -1 ; return infocontent ; } void printLine( std::string &fiboword , int n ) { std::cout << std::setw( 5 ) << std::left << n ; std::cout << std::setw( 12 ) << std::right << fiboword.size( ) ; std::cout << " " << std::setw( 16 ) << std::setprecision( 13 ) << std::left << find_entropy( fiboword ) ; std::cout << "\n" ; } int main( ) { std::cout << std::setw( 5 ) << std::left << "N" ; std::cout << std::setw( 12 ) << std::right << "length" ; std::cout << " " << std::setw( 16 ) << std::left << "entropy" ; std::cout << "\n" ; std::string firststring ( "1" ) ; int n = 1 ; printLine( firststring , n ) ; std::string secondstring( "0" ) ; n++ ; printLine( secondstring , n ) ; while ( n < 37 ) { std::string resultstring = firststring + secondstring ; firststring.assign( secondstring ) ; secondstring.assign( resultstring ) ; n++ ; printLine( resultstring , n ) ; } return 0 ; }
- Output:
N length entropy 1 1 -0 2 1 -0 3 2 1 4 3 0.9182958340545 5 5 0.9709505944547 6 8 0.954434002925 7 13 0.9612366047229 8 21 0.9587118829771 9 34 0.9596868937742 10 55 0.9593160320544 11 89 0.9594579158387 12 144 0.959403754221 13 233 0.959424446956 14 377 0.9594165437404 15 610 0.9594195626031 16 987 0.9594184095152 17 1597 0.9594188499578 18 2584 0.959418681724 19 4181 0.9594187459837 20 6765 0.9594187214387 21 10946 0.959418730814 22 17711 0.959418727233 23 28657 0.9594187286008 24 46368 0.9594187280783 25 75025 0.9594187282779 26 121393 0.9594187282017 27 196418 0.9594187282308 28 317811 0.9594187282197 29 514229 0.9594187282239 30 832040 0.9594187282223 31 1346269 0.9594187282229 32 2178309 0.9594187282227 33 3524578 0.9594187282228 34 5702887 0.9594187282227 35 9227465 0.9594187282227 36 14930352 0.9594187282227 37 24157817 0.9594187282227
Content is available under GNU Free Documentation License 1.2.