首页 > 代码库 > 求斐波那契单词的第n个字符

求斐波那契单词的第n个字符

2024-07-07 11:32:07   213人阅读

定义【摘抄自Wiki】

Let be "0" and be "01". Now (the concatenation of the previous sequence and the one before that).

The infinite Fibonacci word is the limit 

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, ...

Problem:

求斐波那契单词的第n个字符。即写如下函数：
char f(index)

思路：
初始条件：f(0)=0, f(1)=1
斐波那契单词分为两部分，Sn-1和Sn-2。
假设index >= length(Sn-1)，那么f(index) = f(index-length(Sn-1))。
不断递减index直到index <= 1为止，那么即可得出f(index)的值。

C++代码如下：

#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;
}


联系
我们