01串

01 串

描述:

ACM的zyc在研究01串,他知道某一01串的长度,但他想知道不含有“11”子串的这种长度的01串共有多少个,他希望你能帮帮他。

注:01串的长度为2时,有3种:00,01,10。

输入:

第一行有一个整数n(0< n <=100),表示有n组测试数据;
随后有n行,每行有一个整数m(2<=m<=40),表示01串的长度;

输出:

输出不含有“11”子串的这种长度的01串共有多少个,占一行。

样例输入:

2
2
3

样例输出:

3
5

#include <iostream>
#include <cstdio>
#include <map>
using namespace std;

/**
 * 递归求解 01 组
 * int num 0/1 数
 * int times 递归次数
 * int sum 最终结果
**/
int pack(int num, int times, int sum){
    if(times == 1) return 1;

    // num = 1 时,只有一种情况
    if(num==1){
        times = times - 1;
        return pack(0,times, sum);
    }

    // 为零时,返回 0 和 1 的情况和。
    else if(num==0){
        times = times - 1;
        return pack(0,times, sum) + pack(1,times, sum);
    }
}

int main()
{
    // 测试数据数量
    int testNum = 0;

    scanf("%d",&testNum);
    while(testNum--)
    {
        // 递归深度
        int times = 0;

        scanf("%d",&times);
        printf("%d", pack(0,times+1,0));
    }

    return 0;
}