[已解决]C++

黎子卿

描述
错排问题：编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法。

走楼梯时，每次能跨一级、二级、……、n级，但I级能且仅能跨一次，且要求第i次跨步的大小不能是i级楼梯。n*（n+1）/2级楼梯有几种走法，输出所有的走法

输入
一个正整数n（n<10）
输出
多行，每行表示一种走楼梯的方法
样例输入
3
样例输出
231
312

最佳答案

月排行榜 / 总排行榜

isdkz

2023-11-22 08:09:18

这是一个经典的错排问题和楼梯走法问题。下面是C++的解决方案：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. // 错排问题
   
7. int derangement(int n) {
   
8.     if (n == 1) return 0;
   
9.     if (n == 2) return 1;
   
10.     return (n - 1) * (derangement(n - 1) + derangement(n - 2));
    
11. }
    
12. 
    
13. // 楼梯走法问题
    
14. void dfs(vector<int>& path, vector<vector<int>>& result, int n) {
    
15.     if (path.size() == n) {
    
16.         result.push_back(path);
    
17.         return;
    
18.     }
    
19.     for (int i = 1; i <= n; ++i) {
    
20.         if (find(path.begin(), path.end(), i) == path.end()) {
    
21.             if (path.empty() || abs(i - path.back()) != path.size() + 1) {
    
22.                 path.push_back(i);
    
23.                 dfs(path, result, n);
    
24.                 path.pop_back();
    
25.             }
    
26.         }
    
27.     }
    
28. }
    
29. 
    
30. int main() {
    
31.     int n;
    
32.     cin >> n;
    
33. 
    
34.     // 错排问题
    
35.     cout << derangement(n) << endl;
    
36. 
    
37.     // 楼梯走法问题
    
38.     vector<vector<int>> result;
    
39.     vector<int> path;
    
40.     dfs(path, result, n);
    
41.     for (const auto& r : result) {
    
42.         for (int i : r) {
    
43.             cout << i;
    
44.         }
    
45.         cout << endl;
    
46.     }
    
47.     return 0;
    
48. }
    

复制代码

这段代码首先计算了错排问题的解，然后使用深度优先搜索（DFS）计算了楼梯走法问题的解。

跳转到最佳答案楼层

isdkz

这是一个经典的错排问题和楼梯走法问题。下面是C++的解决方案：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <algorithm>
   
4. using namespace std;
   
5. 
   
6. // 错排问题
   
7. int derangement(int n) {
   
8.     if (n == 1) return 0;
   
9.     if (n == 2) return 1;
   
10.     return (n - 1) * (derangement(n - 1) + derangement(n - 2));
    
11. }
    
12. 
    
13. // 楼梯走法问题
    
14. void dfs(vector<int>& path, vector<vector<int>>& result, int n) {
    
15.     if (path.size() == n) {
    
16.         result.push_back(path);
    
17.         return;
    
18.     }
    
19.     for (int i = 1; i <= n; ++i) {
    
20.         if (find(path.begin(), path.end(), i) == path.end()) {
    
21.             if (path.empty() || abs(i - path.back()) != path.size() + 1) {
    
22.                 path.push_back(i);
    
23.                 dfs(path, result, n);
    
24.                 path.pop_back();
    
25.             }
    
26.         }
    
27.     }
    
28. }
    
29. 
    
30. int main() {
    
31.     int n;
    
32.     cin >> n;
    
33. 
    
34.     // 错排问题
    
35.     cout << derangement(n) << endl;
    
36. 
    
37.     // 楼梯走法问题
    
38.     vector<vector<int>> result;
    
39.     vector<int> path;
    
40.     dfs(path, result, n);
    
41.     for (const auto& r : result) {
    
42.         for (int i : r) {
    
43.             cout << i;
    
44.         }
    
45.         cout << endl;
    
46.     }
    
47.     return 0;
    
48. }
    

复制代码

这段代码首先计算了错排问题的解，然后使用深度优先搜索（DFS）计算了楼梯走法问题的解。