请用c++帮我写一个程序,要求如下:有一楼梯共M级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第M级,共有多少种走法?输入时,输入数据首先包含一个整数N,表示测试实例的个数,然后是N行数据,每行包含一个整数M(1<=M<=40),表示楼梯的级数,,对于每个测试实例,请输出不同走法的数量
时间: 2023-06-18 16:02:43 浏览: 45
以下是用动态规划的思想,用C++编写的程序,可以满足您的需求:
```c++
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int n;
cin >> n;
while (n--) {
int m;
cin >> m;
if (m == 1) cout << 1 << endl;
else if (m == 2) cout << 2 << endl;
else {
long long dp[m+1];
memset(dp, 0, sizeof(dp));
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= m; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
cout << dp[m] << endl;
}
}
return 0;
}
```
程序的思路是,先判断输入的楼梯级数是否为1或2,如果是,则直接输出相应的结果;否则,定义一个长整型数组dp,其中dp[i]表示走到第i级楼梯的不同走法数量。显然,走到第1级楼梯只有1种不同走法,走到第2级楼梯有2种不同走法,因此先将dp[1]和dp[2]初始化为1和2。然后,从第3级楼梯开始,每次计算dp[i]的值都是dp[i-1]和dp[i-2]的和,最终得到dp[m]即为走到第m级楼梯的不同走法数量。