求解递归问题
组长很喜欢爬楼梯，但是由于其腿不够长，每次最多只能一步跨越两个阶梯。比如他初始在楼底，跨越一个阶梯到达 1 号阶梯，或者跨越两个阶梯到达 2号阶梯。由于他非常无聊，想把所有不同的到达楼顶的方式都尝试一遍。
但是他又很懒，不想自己计算，因此请你帮他算一算，对于一共有 n 个阶梯的楼梯，一共有多少总方法从楼底到达楼顶。
由于最后答案可能很大，输出最后的答案对 100007 取模的结果。
本帖最后由 sfqxx 于 2023-4-15 19:53 编辑
可以使用动态规划来解决这个问题。对于第 i 个楼梯（从第 0 个开始计数），设 s 表示从楼底到达该楼梯的所有方法的数量。则有 s=1，s=1，s=2，对于 i>2，有以下转移方程：
s = (s + s) % 100007
最终答案为 s，其中 n 为楼梯总数。下面是具体的 Python 代码实现：MOD = 100007
def climb_stairs(n):
if n == 0 or n == 1:
return 1
if n == 2:
return 2
s = * (n+1)
s = 1
s = 1
s = 2
for i in range(3, n+1):
s = (s + s) % MOD
return s
# 测试样例
print(climb_stairs(3)) # 输出为 3
在上面的代码中，MOD 是取模的数。当 n=0 或 n=1 时，只有一种到达楼顶的方法，因此直接返回 1；当 n=2 时，有两种到达楼顶的方法，直接返回 2。对于 i>2，使用循环计算 s 数组并利用取模运算避免答案过大的问题。最后返回 s 即可。
有用请设置最佳答案 这个问题可以用递归或者动态规划来求解。由于递归可能会产生很多重复计算，我们选择使用动态规划方法。这里是一个Python程序，可以求解这个问题：
def climb_stairs(n):
if n <= 2:
return n
dp = * (n + 1)
dp = 1
dp = 2
for i in range(3, n + 1):
dp = (dp + dp) % 100007
return dp
n = int(input("请输入楼梯的阶梯数: "))
result = climb_stairs(n)
print("一共有 %d 种方法到达楼顶。" % result)
使用这个程序，你可以计算出对于给定楼梯数 n 的情况下，有多少种不同的方式到达楼顶。最后的答案会对 100007 取模。
isdkz 发表于 2023-4-15 19:51
这个问题可以用递归或者动态规划来求解。由于递归可能会产生很多重复计算，我们选择使用动态规划方法。这里 ...
这是C语言版本：
#include <stdio.h>
// 计算有多少种方法到达楼顶的函数
int climb_stairs(int n) {
if (n <= 2) {
return n;
}
int dp; // 定义动态规划数组
dp = 1;
dp = 2;
// 从第3阶开始，计算到达每个阶梯的方法数
for (int i = 3; i <= n; i++) {
dp = (dp + dp) % 100007; // 更新动态规划数组，取模100007防止整数溢出
}
return dp;
}
int main() {
int n;
printf("请输入楼梯的阶梯数: ");
scanf("%d", &n);
int result = climb_stairs(n);
printf("一共有 %d 种方法到达楼顶。\n", result);
return 0;
}
isdkz 发表于 2023-4-15 19:53
这是C语言版本：
这是递归版本：
#include <stdio.h>
// 计算递归方法的函数
int climb_stairs_recursive(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
// 递归调用
return (climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)) % 100007;
}
int main() {
int n;
printf("请输入楼梯的阶梯数: ");
scanf("%d", &n);
int result = climb_stairs_recursive(n);
printf("一共有 %d 种方法到达楼顶。\n", result);
return 0;
}
isdkz 发表于 2023-4-15 19:51
这个问题可以用递归或者动态规划来求解。由于递归可能会产生很多重复计算，我们选择使用动态规划方法。这里 ...
我希望得到用c或c++写的代码,动态管理不懂，递归最好 白痴爱面包 发表于 2023-4-15 20:03
我希望得到用c或c++写的代码,动态管理不懂，递归最好
我在最后面发了一个递归版本 #include <bits/stdc++.h>
using namespace std;
const int mod = 100007;
int climb(int stair){
if(stair <= 1) return 1;
// 递归边界, 小于 1 就只有一种方法了
return (climb(stair - 1) + climb(stair - 2)) % mod;
// 走到这个台阶的方法数是 stair-1 阶方法数 + stair-2 阶方法数
}
int n;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
cout << climb(n);
return 0;
}
页:
[1]