UVA11089 Fi-binary Number【数学规律】

A Fi-binary number is a number that contains only 0 and 1. It does not contain any leading 0. And also it does not contain 2 consecutive 1. The first few such number are 1,10,100,101,1000,1001,1010,10000,10001,10010,10100,10101 and so on. You are given n. You have to calculate the n-th Fi-Binary number.
Input
The first line of the input contains one integer T the number of test cases. Each test case contains one integer n.
Output
For each test case output one line containing the n-th Fi-Binary number.
Constraints
? 1 ≤ N ≤ 10^9
Sample Input
4
10
20
30
40
Sample Output
10010
101010
1010001
10001001

问题链接：UVA11089 Fi-binary Number
问题简述：（略）
问题分析：
????Fi-binary Number数定义为由0和1构成，开头不是0，且没有连续的两个1。该数的数列依次是1,10101,......。对于给定的n，计算该数列的第n项。
????该数列的长度个数正好呈现菲波那契数列特性，利用该特性进行计算。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序如下：

/* UVA11089 Fi-binary Number */

#include <iostream>

using namespace std;

const int N = 43;
int f[N + 1];

void setfib()
{
    f[0] = 1;
    f[1] = 1;
    for(int i = 2; i <= N; i++)
            f[i] = f[i - 2] + f[i - 1];
}

void solve(int n)
{
    n--;
    int k;
    for (k = 0; f[k] <= n; k++)
        n -= f[k];

    printf("1");
    while (k > 1) {
        if (n < f[k - 1]) {
            printf("0");
            k--;
        } else {
            printf("01");
            n -= f[k - 1];
            k -= 2;
        }
    }

    printf("%sn",k ? "0" : "");
}

int main()
{
    setfib();

    int t,n;
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);

        solve(n);
    }

    return 0;
}