用c++帮助老师排座位（优化）
2025-01-09 20:38:44
发布于：北京
120阅读
0回复
0点赞
最近有一件事使我的班主任十分苦恼，许多同学总会在课上交头接耳，为了避免这种情况，我们敬爱的班主任在每周排座位时就会将交头接耳的同学分开。
可是交头接耳的同学人数众多，为了将他们全部分开，班主任每周都要花大量时间排座位。
为了帮助我们可怜的班主任，我决定完成一个程序，帮助班主任排座位
很快我就完成了
（我们班一共31人，学号为1-32，没有19号，座位5x6，座位从左往右第二列有7个人）
#include <iostream>
#include <vector>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
int s[7][6]; // 座位
vector<pair<int, int>> c; // 交头接耳的学生对
map<int, pair<int, int>> p; // 学生的座位
bool v[33]; // 记录学生是否已安排
int T; // 交头接耳的学生对数
// 判断学生能否坐在(i, j)位置
bool can(int st, int i, int j) {
for (auto& x : c) {
int a = x.first, b = x.second; // a 和 b 为学生对中的两位学生
if (a == st || b == st) {
if (p.count(a)) {
int rr = p[a].first, cc = p[a].second;
if (rr == i || cc == j) return false; // 冲突
}
if (p.count(b)) {
int rr = p[b].first, cc = p[b].second;
if (rr == i || cc == j) return false; // 冲突
}
}
}
return true;
}
// 尝试为学生安排座位
bool dfs(int k) {
if (k > 32) return true; // 所有学生已安排
if (k == 19) return dfs(k + 1); // 19号学生跳过
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 6; j++) {
if ((i == 6 && j != 1) || s[i][j] != 0) continue; // 排除无效座位
if (can(k, i, j)) {
s[i][j] = k; // 安排座位
p[k] = {i, j}; // 记录座位
if (dfs(k + 1)) return true; // 递归尝试下一个学生
s[i][j] = 0; // 回溯
p.erase(k); // 回溯
}
}
}
return false; // 当前路径无解
}
int main() {
cout << "交头接耳的学生对数：";
cin >> T;
c.resize(T);
for (int i = 0; i < T; i++) {
cout << "第" << i + 1 << "组学生：";
cin >> c[i].first >> c[i].second;
}
memset(s, 0, sizeof(s));
memset(v, false, sizeof(v));
if (dfs(1)) {
cout << "座位安排：" << endl;
// 输出座位安排
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 6; j++) {
if ((i == 6 && j == 0) || (i == 6 && j != 1)) {
cout << " "; // 留空座位
} else if (s[i][j] != 0) {
cout << s[i][j] << " ";
if (s[i][j] < 10) cout << " "; // 对齐数字
}
}
cout << endl;
}
} else {
cout << "无法安排座位！" << endl;
}
return 0;
}
虽然排好的座位确实分开了交头接耳的学生，但是我写完代码运行的时候又发现一个很严重的问题，太有序了！
你运行一些代码就知道我在说什么了
由于是1-32顺序遍历学号并尝试填充，所以只要当前遍历到的学生不是交头接耳的学生，那么座位就是有序的！
于是我打乱了遍历学号的顺序，代码成了这样
#include <iostream>
#include <vector>
#include <map>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
int s[7][6]; // 座位
vector<pair<int, int> > c; // 交头接耳的学生对
map<int, pair<int, int> > p; // 学生的座位
int v[33]; // 记录学生是否已安排
int T; // 交头接耳的学生对数
vector<int> students; // 存储学生学号，用于打乱顺序
// 判断学生能否坐在(i, j)位置
bool can(int st, int i, int j) {
for (size_t k = 0; k < c.size(); ++k) {
int a = c[k].first, b = c[k].second; // a 和 b 为学生对中的两位学生
if (a == st || b == st) {
if (p.count(a)) {
int rr = p[a].first, cc = p[a].second;
if (rr == i || cc == j) return false; // 冲突
}
if (p.count(b)) {
int rr = p[b].first, cc = p[b].second;
if (rr == i || cc == j) return false; // 冲突
}
}
}
return true;
}
// 尝试为学生安排座位
bool dfs(int idx) {
if (idx >= students.size()) return true; // 所有学生已安排
int st = students[idx]; // 当前学生的学号
if (st == 19) return dfs(idx + 1); // 19号学生跳过
// 打乱尝试为学生安排座位的顺序
vector<pair<int, int> > seats;
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 6; j++) {
if ((i == 6 && j != 1) || s[i][j] != 0) continue; // 排除无效座位
seats.push_back(make_pair(i, j));
}
}
// 随机打乱座位顺序
srand(time(0)); // 初始化随机种子
for (int i = 0; i < seats.size(); i++) {
int j = rand() % seats.size();
swap(seats[i], seats[j]);
}
for (size_t i = 0; i < seats.size(); ++i) {
int i_ = seats[i].first, j = seats[i].second;
if (can(st, i_, j)) {
s[i_][j] = st; // 安排座位
p[st] = make_pair(i_, j); // 记录座位
if (dfs(idx + 1)) return true; // 递归尝试下一个学生
s[i_][j] = 0; // 回溯
p.erase(st); // 回溯
}
}
return false; // 当前路径无解
}
int main() {
cout << "交头接耳的学生对数：";
cin >> T;
c.resize(T);
for (int i = 0; i < T; i++) {
cout << "第" << i + 1 << "组学生：";
cin >> c[i].first >> c[i].second;
}
memset(s, 0, sizeof(s));
memset(v, 0, sizeof(v));
// 初始化学生学号并随机打乱顺序
students.clear();
for (int i = 1; i <= 32; i++) {
if (i != 19) { // 19号学生跳过
students.push_back(i);
}
}
// 随机打乱学生的顺序
srand(time(0)); // 初始化随机种子
for (int i = 0; i < students.size(); i++) {
int j = rand() % students.size();
swap(students[i], students[j]);
}
if (dfs(0)) {
cout << "座位安排：" << endl;
// 输出座位安排
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 6; j++) {
if ((i == 6 && j == 0) || (i == 6 && j != 1)) {
cout << " "; // 留空座位
} else if (s[i][j] != 0) {
cout << s[i][j] << " ";
if (s[i][j] < 10) cout << " "; // 对齐数字
}
}
cout << endl;
}
} else {
cout << "无法安排座位！" << endl;
}
return 0;
}
有帮助，赞一个