由于学习需要，然后花费将近两天时间研究这个问题，然后用C++描述出来，具体内容看下面：
问题描述（见百度百科）：
https://baike.baidu.com/item/%E7%A8%B3%E5%AE%9A%E5%A9%9A%E5%A7%BB%E9%97%AE%E9%A2%98/12760040
为了解决稳定匹配问题（Stable Matching Problem），前辈们提出了GS算法。
下面就是博主使用GS算法完成的本题，同时在研究过程中发现了一个新的匹配思路，将会在下面发出来（不知道前辈们有没有提出过），大家可以积极提出宝贵意见：
问题分析：
1.首先输入男士（女士）人数，这里男士，女士人数相同并且要求最后每个人都有对象。
2.初始化所有男士，女士追求过对象人数better=0，对异性喜欢排名数组rank[],当前是否在约会状态Yuehui,以及现任为-1；
3.既然男的需要主动，那就让所有单身状态的男士向自己最喜欢的女士表白，不管结局成功与否，该男士追求过的人数都加1；
4.如果女士单身，那么两个人就暂时在一起先处着，更改两个人是否约状态为true，设置对方为自己的现任；
5.如果女士不是单身，此时就出现了小三，那么主动权就交给女士了,此时女士比较现任与小三，如果更喜欢现任。跳过当前追求者；如果更喜欢小三，抛弃现任，此时小三终于扬眉吐气成功上位，并与当前追求者结合成暂时情侣去约会。
6.判断是否全部找到对象，都找到了结束查找，否则重复步骤：2-5，直到全部由对象；
7.结束，输出；
程序设计
这里使用历史人物，（得到的最终匹配结果可能不与现实相同），男女各5名，对其进行编号。由编号代替其姓名。
各男士喜欢排名表：
（仅供实验参考，最终数据为自行输入）
各女士喜欢排名表：
（仅供实验参考，最终数据为自行输入）
定义人类（是人 类 ，类，类）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class People
{
private:
int better;
int rank[NUM];
bool Yuehui;
int present;
public:
People()
{
better = 0;
Yuehui = false;
present = -1;
}
void setRank(int mRank, int i);
int getRank(int i) { return rank[i]; };
void setYuehui(bool mYuehui);
bool getYuehui() { return Yuehui; };
void setBetter(int mBetter);
int getBetter() { return better; };
void setPresent(int mPressent);
int getPressent() { return present; };
};
|
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
| #include<iostream>
#include<cstring>
using namespace std;
const int NUM = 5;
int flag = 0;
class People
{
private:
int better;
int rank[NUM];
bool Yuehui;
int present;
public:
People()
{
better = 0;
Yuehui = false;
present = -1;
}
void setRank(int mRank, int i);
int getRank(int i) { return rank[i]; };
void setYuehui(bool mYuehui);
bool getYuehui() { return Yuehui; };
void setBetter(int mBetter);
int getBetter() { return better; };
void setPresent(int mPressent);
int getPressent() { return present; };
};
void People::setRank(int mRank, int i)
{
rank[i] = mRank;
}
void People::setYuehui(bool mYuehui)
{
Yuehui = mYuehui;
}
void People::setBetter(int mBetter)
{
better = mBetter;
}
void People::setPresent(int mPressent)
{
present = mPressent;
}
int main()
{
People man[NUM];
People lady[NUM];
for (int i = 0; i < NUM; i++)
{
for (int j = 0; j < NUM; j++)
{
int temp;
cout << "请输入第" << i+1 << "个人喜欢的第" << j+1 << "个人:";
cin >> temp;
man[i].setRank(temp, j);
}
}
cout << "男士初始化完毕" << endl;
for (int i = 0; i < NUM; i++)
{
for (int j = 0; j < NUM; j++)
{
int temp;
cout << "请输入第" << i + 1 << "个人喜欢的第" << j + 1 << "个人:";
cin >> temp;
lady[i].setRank(temp, j);
}
}
cout << "女士初始化完毕" << endl;
while (true)
{
flag = 1;
for (int i = 0; i < NUM; i++)
{
if (man[i].getYuehui() == false)
{
flag = 0;
int num_Y = man[i].getBetter();
int girl = man[i].getRank(num_Y);
man[i].setBetter(num_Y + 1);
if (lady[girl].getYuehui() == false)
{
man[i].setYuehui(true);
man[i].setPresent(girl);
lady[girl].setYuehui(true);
lady[girl].setPresent(i);
}
if (lady[girl].getYuehui() == true)
{
int before, now;
for (int j = 0; j < NUM; j++)
{
if (lady[girl].getRank(j) == i)
{
now = j;
}
if (lady[girl].getRank(j) == lady[girl].getPressent())
{
before = j;
}
}
if (before < now)
{
}
else if (before>now)
{
man[lady[girl].getPressent()].setYuehui(false);
man[lady[girl].getPressent()].setPresent(100);
man[i].setYuehui(true);
man[i].setPresent(girl);
lady[girl].setPresent(i);
}
}
}
}
if (flag == 1)
{
break;
}
}
for (int i = 0; i < NUM; i++)
{
cout << i << "和" << man[i].getPressent() << "在一起" << endl;
}
}
|
最后，看下结果吧～～
最最后，画了张图并结合上面三张表述我的新思路：
Tony-Chen
2017.10.25
心的强大因为鉴定！
