We have:
0
01
010
01001
01001010
0100101001001
...
The first few elements of the infinite Fibonacci word are:
0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0,
0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ...
#include <vector>
#include <iostream>
#include <cassert>
char getCharInFibonacciWord(int index)
{
using namespace std;
assert(index >=0);
//
The 48th fibonacci number is already out of range of int.
static int fibs[48]
= {1,2,0};
while(
index > 1)
{
int i=0;
for(int i=1;
i<_countof(fibs); ++i)
{
if(fibs[i]
== 0)
fibs[i] = fibs[i-1] + fibs[i-2];
if(fibs[i]
> index)
{
index -= fibs[i-1];
break;
}
}
}
return (index
== 0) ? ‘0‘ : ‘1‘;
}
int _tmain(int argc,
_TCHAR* argv[])
{
for(int i=0;
i<100; ++i)
std::cout << getCharInFibonacciWord(i);
std::cout << std::endl;
return 0;
}
