链接：https://ac.nowcoder.com/acm/challenge/terminal
来源：牛客网

题目描述

今天是Tabris和mengxiang000来到幼儿园的第3天，mengxiang000接到了一个布置会场的任务。

他需要将贵宾观众席的椅子排成一排，一共需要N个。

幼儿园只有两种椅子，所以他也只能使用两种椅子。（A类型和B类型）并且假设每种椅子的数量都是无限的。

而其如果想要摆置一个B类型的椅子，对应就需要必须有连续两个一起布置。换句话说，就是如果出现了B类型的椅子，其必须且只有两个连着B类型的椅子。

mengxiang000突然想知道对应N个椅子排成一列，他能够有多少种布置的方式.

输入描述:

本题包含多组输入第一行输入一个整数t，表示测试数据的组数
每组测试数据包含一行，输入一个整数N，表示一共需要摆放的椅子数量
t<=30
1<=N<=30

输出描述:

每组测试数据输出包含一行，表示一共有多少种布置的方式。
示例1

输入

复制 
2
2
4

输出

复制 
2
5

说明

第一个样例，AA，BB两种方案。
第二个样例，AAAA,BBBB,AABB,ABBA,BBAA五种方案  对于ABBB 因为有连续3个B类型椅子所以不可行


算下前5个样例得到斐波那契数列
1 2 3 4 5
1 2 3 5 8
#include<bits/stdc++.h>
using namespace std;
long long f[50];
int main()
{
    f[1] = 1;
    f[2] = 2;
    for(int i = 3; i < 50; i++)
        f[i] = f[i - 1] + f[i - 2];
    int N;
    cin >> N;
    while(N--)
    {
        int n;
        cin >> n;
        cout << f[n] << endl;
    }
    return 0;
}
View Code