可以一步一阶,也可以一步两阶,现有n阶台阶,一共有多少种办法,通过c语言编写程序解答
时间: 2024-01-01 09:05:42 浏览: 91
这是一个典型的斐波那契数列问题,可以使用递归或动态规划来解决。
以下是使用递归方式来解决该问题的C语言代码:
```c
#include <stdio.h>
int climbStairs(int n) {
if (n == 1 || n == 2) {
return n;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
int main() {
int n = 5;
printf("There are %d ways to climb %d stairs.\n", climbStairs(n), n);
return 0;
}
```
如果要计算n阶台阶的总共方案数,可以调用 `climbStairs(n)` 函数。
当然,递归方式可能会在计算过程中出现重复计算的问题,影响效率。因此,使用动态规划可能更加优化。以下是使用动态规划方式来解决该问题的C语言代码:
```c
#include <stdio.h>
int climbStairs(int n) {
if (n == 1 || n == 2) {
return n;
}
int dp[n+1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
int main() {
int n = 5;
printf("There are %d ways to climb %d stairs.\n", climbStairs(n), n);
return 0;
}
```
动态规划方式使用一个数组 `dp` 记录每个台阶的方案数,避免了重复计算。
阅读全文