C++: Fibonacci Word

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```

SOURCE

Content is available under GNU Free Documentation License 1.2.