用C++编写“输入包含若干行,每行包含一个正整数N,代表楼梯级数,1 <= n<= 50,最后一行为0,表示测试结束,输出:不同的走法数,每一行输入对应一行输出”
时间: 2023-06-15 07:07:34 浏览: 100
以下是用C++编写的程序:
```c++
#include <iostream>
using namespace std;
int dp[55]; // dp数组,记录走到每个台阶的走法数
int main() {
int n;
dp[0] = dp[1] = 1; // 初始化dp数组
for (int i = 2; i <= 50; i++) {
dp[i] = dp[i-1] + dp[i-2]; // 状态转移方程
}
while (cin >> n && n) {
cout << dp[n] << endl; // 输出不同的走法数
}
return 0;
}
```
程序中使用了动态规划的思想,dp数组记录了走到每个台阶的不同走法数,其中dp[0] = dp[1] = 1是初始状态,表示走0或1个台阶的走法数都是1。接下来用循环计算dp数组的值,状态转移方程为dp[i] = dp[i-1] + dp[i-2],表示走到第i个台阶的不同走法数等于走到第i-1个和第i-2个台阶的走法数之和。最后通过循环读入每个测试数据,输出对应的不同走法数即可。
阅读全文