楼梯上有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编写算法计算共有多少种不同的上楼梯方法,要求给出数学模型C语言
时间: 2024-09-28 22:15:03 浏览: 91
n阶楼梯上楼方法种数
5星 · 资源好评率100%
这个问题可以用动态规划的思想来解决。我们可以定义两个变量 `f[i]` 和 `g[i]`,分别表示走 i 阶台阶时,只允许一步一阶走和一步两阶走的不同方法数。
对于第 `i` 阶台阶,可以从第 `i-1` 阶和第 `i-2` 阶走过来,因此有:
- 如果一步一阶走,则 f[i] = f[i-1](从 i-1 阶直接走到)
- 如果一步两阶走,则 g[i] = g[i-2] + f[i-2](先走两步到 i-2 阶,再走一步到 i 阶)
最终的答案就是这两种情况下的方法总数,即总方法数为 `f[i] + g[i]`。
下面是对应的 C 语言代码实现:
```c
#include <stdio.h>
int climbStairs(int n) {
if (n <= 0) return 0;
int f[n+1], g[n+1];
f[0] = 1; // 只有一阶,一种方法
g[0] = 0;
f[1] = 1; // 两阶,一种方法
g[1] = 1;
for (int i = 2; i <= n; ++i) {
f[i] = f[i-2]; // 步两阶
}
return f[n] + g[n];
}
int main() {
int stairs = 5; // 替换为你需要计算的具体台阶数
printf("共有 %d 种不同的上楼梯方法.\n", climbStairs(stairs));
return 0;
}
```
阅读全文