C++
描述错排问题：编号是1、2、…、n的n封信，装入编号为1、2、…、n的n个信封，要求每封信和信封的编号不同，问有多少种装法。
走楼梯时，每次能跨一级、二级、……、n级，但I级能且仅能跨一次，且要求第i次跨步的大小不能是i级楼梯。n*（n+1）/2级楼梯有几种走法，输出所有的走法
输入
一个正整数n（n<10）
输出
多行，每行表示一种走楼梯的方法
样例输入
3
样例输出
231
312 这是一个经典的错排问题和楼梯走法问题。下面是C++的解决方案：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 错排问题
int derangement(int n) {
if (n == 1) return 0;
if (n == 2) return 1;
return (n - 1) * (derangement(n - 1) + derangement(n - 2));
}
// 楼梯走法问题
void dfs(vector<int>& path, vector<vector<int>>& result, int n) {
if (path.size() == n) {
result.push_back(path);
return;
}
for (int i = 1; i <= n; ++i) {
if (find(path.begin(), path.end(), i) == path.end()) {
if (path.empty() || abs(i - path.back()) != path.size() + 1) {
path.push_back(i);
dfs(path, result, n);
path.pop_back();
}
}
}
}
int main() {
int n;
cin >> n;
// 错排问题
cout << derangement(n) << endl;
// 楼梯走法问题
vector<vector<int>> result;
vector<int> path;
dfs(path, result, n);
for (const auto& r : result) {
for (int i : r) {
cout << i;
}
cout << endl;
}
return 0;
}
这段代码首先计算了错排问题的解，然后使用深度优先搜索（DFS）计算了楼梯走法问题的解。
页:
[1]