问题描述

有一楼梯共M 级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第 M 级，共 有多少种走法？

输入

输入数据首先包含一个整数 N，表示测试实例的个数，然后是 N 行数据，每行包含一个整数 M（1<=M<=40）,表示楼梯的级数。

输出量

对于每个测试实例，请输出不同走法的数量

样本输入

2
2
3

样本输出

1
2

代码

#include <iostream>
using namespace std;
int way(int a){
    int res;
    if(a==1){
        return 0;
    }
    if(a==2){
        return 1;
    }
    if(a==3){
        return 2;
    }
    else{
        return way(a-1)+way(a-2);
    }
}
int main(){
    int n;
    int floor;
    cin>>n;
    while(n--){
        cin>>floor;
        cout<<way(floor)<<endl;
    }
    return 0;
}