用C++写N(N为偶数)个高矮不同的人排成两排照相,要求每一排都是从矮到高排列,而第二排每个人比第一排对应的人要高,列出所有可能的结果。
时间: 2023-11-27 10:53:25 浏览: 60
这道题可以使用递归的思路来解决,具体思路如下:
1. 定义递归函数:函数参数包括两个vector<int>类型的数组,分别表示当前已排好的两排人员,以及还未排列的人员。另外还需要一个bool类型的变量,表示当前排列是第一排还是第二排。
2. 递归终止条件:当未排列的人员数组为空时,将两排人员排列输出,并返回。
3. 对于未排列的人员数组,遍历其中的每一个人员,分别尝试将其加入第一排或第二排,并调用递归函数处理剩余的人员。
4. 在递归函数中,需要判断当前排列是否满足题目要求。如果不满足,则直接返回。
下面是具体的代码实现:
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void printResult(const vector<int>& a, const vector<int>& b) {
for (int i = 0; i < a.size(); ++i) {
cout << a[i] << " ";
}
cout << endl;
for (int i = 0; i < b.size(); ++i) {
cout << b[i] << " ";
}
cout << endl;
}
void arrange(vector<int> a, vector<int> b, vector<int> rest, bool isFirst) {
if (rest.empty()) {
printResult(a, b);
return;
}
for (int i = 0; i < rest.size(); ++i) {
int cur = rest[i];
if (isFirst && (a.empty() || cur < a.back())) {
continue;
}
if (!isFirst && (b.empty() || cur < b.back())) {
continue;
}
vector<int> rest2 = rest;
rest2.erase(rest2.begin() + i);
if (isFirst) {
vector<int> a2 = a;
a2.push_back(cur);
arrange(a2, b, rest2, false);
} else {
vector<int> b2 = b;
b2.push_back(cur);
arrange(a, b2, rest2, true);
}
}
}
int main() {
int n;
cin >> n;
vector<int> rest(n);
for (int i = 0; i < n; ++i) {
rest[i] = i + 1;
}
vector<int> a, b;
arrange(a, b, rest, true);
return 0;
}
```
阅读全文