C++程序实现爬楼梯并输出所有结果 |21xrx.com

C++程序实现爬楼梯并输出所有结果

2023-06-23 14:43:54 深夜i 38 0

C++程序爬楼梯输出结果

爬楼梯是一个经典的算法问题，可以有不同的解法和实现方式。在本文中，我们将介绍如何使用C++程序实现爬楼梯并输出所有结果。

首先，让我们来看一下爬楼梯问题的具体要求。假设有n级楼梯需要爬，每次只能爬1级或2级，问有多少种不同的方法可以爬到楼顶。

这个问题可以使用递归或动态规划两种方法来解决。其中，递归方法比较简单，但是可能会因为重复计算而导致时间复杂度较高；而动态规划方法可以通过记录中间结果来减少不必要的计算，从而提高效率。

接下来，我们将介绍如何使用动态规划方法来解决爬楼梯问题。

首先，我们可以定义一个数组dp，其中dp[i]表示到达第i级楼梯的不同方法数量。根据题目要求，dp[1]=1，dp[2]=2。对于i>2的情况，我们可以使用递推公式dp[i]=dp[i-1]+dp[i-2]来计算。最终，dp[n]就是到达第n级楼梯的不同方法数量。

下面是具体的C++代码实现：

#include <iostream>
#include <vector>
using namespace std;
int climbStairs(int n) {
  vector<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;
  cout << "The number of different ways to climb " << n << " stairs is " << climbStairs(n) << endl;
}

运行以上代码，将会输出如下结果：

The number of different ways to climb 5 stairs is 8

以上代码仅仅计算了到达第n级楼梯的不同方法数量，如果需要输出所有方案，则需要对代码进行修改。具体方法可以参考以下代码：

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> climbStairs(int n) {
  vector<vector<int>> res;
  vector<int> path;
  dfs(n, path, res);
  return res;
}
void dfs(int n, vector<int>& path, vector<vector<int>>& res) {
  if (n == 0) {
    res.push_back(path);
    return;
  }
  if (n >= 1) {
    path.push_back(1);
    dfs(n-1, path, res);
    path.pop_back();
  }
  if (n >= 2) {
    path.push_back(2);
    dfs(n-2, path, res);
    path.pop_back();
  }
}
int main() {
  int n = 5;
  auto res = climbStairs(n);
  cout << "The number of different ways to climb " << n << " stairs is " << res.size() << endl;
  for (auto path : res) {
    for (auto step : path) {
      cout << step << " ";
    }
    cout << endl;
  }
}

以上代码中，我们新增了一个函数dfs来进行搜索，并返回所有路径。具体做法是从n开始，依次减去1或2，直到减到0为止。在减的过程中，我们记录下已经走过的路径，最终将所有路径存入res中。最后，我们输出所有路径即可。

运行以上代码，将会输出如下结果：

The number of different ways to climb 5 stairs is 8 1 1 1 1 1 1 1 1 2 1 1 2 1 1 2 1 1 1 2 2 2 1 1 1 2 1 2 2 2 1

以上代码实现了C++程序实现爬楼梯并输出所有结果。通过掌握这个经典问题，我们可以更好地理解动态规划和搜索算法，从而提高算法编程能力。

上一篇: idea打包java可执行jar包

下一篇: 如何使C++代码运行？

评论区

相似文章