从楼上走到楼下共有h个台阶,每一步有3种走法:走1个台阶;走2个台阶;走3个台阶。 问可走出多少种方案?c语言
时间: 2024-02-18 18:05:59 浏览: 38
这是一道典型的动态规划问题,可以使用递推算法实现。以下是 C 语言的代码实现:
```c
#include <stdio.h>
int main()
{
int h, i;
long long f[101];
scanf("%d", &h);
f[0] = 1;
for (i = 1; i <= h; i++) {
f[i] = f[i-1];
if (i >= 2) f[i] += f[i-2];
if (i >= 3) f[i] += f[i-3];
}
printf("%lld\n", f[h]);
return 0;
}
```
其中,`f[i]` 表示到第 i 个台阶的方案数。根据题目要求,`f[i]` 可以由 `f[i-1]`、`f[i-2]` 和 `f[i-3]` 转移而来。需要注意的是,由于题目保证了楼上到楼下的台阶数不超过 100,因此我们需要使用 `long long` 类型来存储方案数,以避免溢出。
相关问题
多组输入,每组一行,为一个正整数h(h<=30),表示从楼上走到楼下共有h个台阶。从楼上走到楼下共有h个台阶,每一步有3种走法:走1个台阶;走2个台阶;走3个台阶。 问可走出多少种方案?
这是一个典型的动态规划问题,可以使用递推的方式求解。设f[i]表示走到第i个台阶的方案数,则有:
f[i] = f[i-1] + f[i-2] + f[i-3]
初始条件为f[1]=1, f[2]=2, f[3]=4。最终答案为f[h]。
以下是完整的代码实现:
#include <iostream>
using namespace std;
int main() {
int h;
cin >> h;
int f[31] = {0, 1, 2, 4};
for (int i = 4; i <= h; i++) {
f[i] = f[i-1] + f[i-2] + f[i-3];
}
cout << f[h] << endl;
return 0;
}
楼上走到楼下共有n个台阶,每一步有三种走法,走1个台阶,走2个台阶,走3个台阶。问可走出多少种方案?希望用递归思想来编程。 首先定义: (1)Try(i,s)为站在第i级台阶上往下试走第s步的过程; (2)j为在每一步可以试着走的台阶数,j=1, 2.3; (3)take[s]为存储第s步走过的台阶数。 如果i<j,说明第i级台阶已比要走的j级台阶小,j不可取。 如果i>j ,说明站在第i级台阶上可试走j个台阶为一步。 如果i==j,说明这一步走完后已到了楼下,这时一条下楼方案已试成,即可输出这方案,用c语言表达
可以使用以下递归函数来实现:
```c
#include <stdio.h>
#define MAX_STEPS 100
#define MAX_TAKE 100
void Try(int i, int s, int n, int take[MAX_TAKE])
{
int j;
if (i < s) {
return;
} else if (i == s) {
take[s] = i;
printf("方案: ");
for (j = 1; j <= s; j++) {
printf("%d ", take[j]);
}
printf("\n");
return;
} else {
for (j = 1; j <= 3; j++) {
take[s] = i - j;
Try(i - j, s + 1, n, take);
}
}
}
int main()
{
int n, take[MAX_TAKE];
printf("请输入楼梯台阶数:");
scanf("%d", &n);
Try(n, 1, n, take);
return 0;
}
```
该递归函数接受四个参数:当前所在的台阶数i,当前走的步数s,总台阶数n以及一个存储走过的台阶数的数组take。
在递归函数中,首先判断如果当前所在的台阶数i小于当前走的步数s,则说明已经走到了比要走的步数更低的位置,这种情况下应该直接返回。
如果当前所在的台阶数i等于当前走的步数s,则说明已经到了楼下,这时候就可以输出这条下楼的方案,即输出数组take中存储的走过的台阶数。
如果当前所在的台阶数i大于当前走的步数s,则说明可以试着往下走1、2、3个台阶。在循环中,依次尝试往下走1、2、3个台阶,对于每一种尝试,都将当前所在的台阶数i减去走过的台阶数j,并将这个走过的台阶数j存储到数组take中。然后递归调用Try函数,继续向下走下一步。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)