中兴捧月杯第一题初赛
一、标题：
数字化婚姻配对尝试
二、题目：
建立一个模型，来模拟推导社会男女择偶过程。
为了模型简化，一个人的特性指标有三个，这里假设为财富、样貌、品格，每个指标均可取值1-100之间任意数字。同样也对这3项指标有自己的需求。这3个需求值取值范围都在1-98间，当然三者的和必须为100.所以任意一个人可以用以下数组来表述：
G（A、B、C、A1、B1、C1）G代表男，M代表女。
举例G11（80、50、40、10、30、60），表示男11号，拥有财富80、样貌50、品格40，对异性品格的偏好为：财富在乎程度百分之10、样貌在乎程度百分之30、品格在乎程度百分之60。
同样为了模型简化，假设信息是完全对称的，即是说，每个人都能一眼就能看清楚任意一个人的财富、样貌、品格。
还是为了模型简化，我建模所用样本为男女各100个，即男女人数相同。
每个人对异性的满意度将如下定义：每个偏好指标与异性的对应的禀赋指标相乘，三个指标的乘积再相加，即他（她）对某个异性的满意度。
举例G11（80、50、40、10、30、60）对M（50、60、80、40、10、50）的满意度为：
（10*50+30*60+60*80）= 7100分
相对的 MM 对 GG的满意度则为：
（40*80+10*50+50*40） = 5700分
好了，配对活动开始，设计的配对法则如下：
1、100个男方，顺序，轮流从0号到99号女方中挑选自己最满意的一位，然后向她发出配对邀请。
2、接受邀请最多的女方开始行动，对这些邀请的男性中，选择最满意的一位。
3、那么这两位配对成功，剔除出样本，剩下的99对继续这样配对。
4、循环该配对法则，直到最后一对男女配对成功。
三、初赛阶段要求:
1、编程语言为java，C++或C语言任意一种；运行环境windows。
2、能让用户输入自己的参数以及对各项数值的偏好,然后随机生成100位男性100位女性（包括用户在内。如果用为男性则为99男100女），数值全部随机但需满足题设限制。按照上述规则给出一个匹配结果呈现给用户。
3、若采用c/c++,要输出可执行程序；若采用java，给出jar和bat。
4、在匹配时，如果发现有多个满意度相同的对象，要求自身三个属性(财富，外貌，品格)总和大的优先，如果再相同则id小的优先。如果有2位女士的选票相同，优先级规则同上。请把主角的id置为最小值，以便在前2个条件相同情况下，主角可以优先选择。
5、程序读取指定的配置文件，获取样本，然后根据指定的输入，输出结果。同时会给出一组源数据和标准答案给学生自测。最后再让学生根据不同的，指定的输入，给出考试答案。
请点击下载配置文件附件。附件中，male.txt,female.txt,players.txt 分别是男士样本、女士样本和主角样本各 100位。 男女样本中，每行都代表一位男士或女士的基本属性，从左到右依次是ID, 样貌,品格,财富 , 期望样貌,期望品格,期望财富，没有加入性别，需要在解析时手动添加，每个txt文本的性别都是一样的，请注意。另外，主角样本中没有ID属性，换成了性别属性，其中 0表示女性，1表示男性，其余属性依次为样貌,品格,财富,期望样貌 ,期望品格,期望财富。建议把主角的id都设置为 -1，以便满足优先选择的条件。
给出标准答案2组，用于考生自测:
1号主角(文本第一行)，选择的对象属性为(6,18,82,87,3,10)
2号主角(文本第二行)，选择的对象属性为(27,74,22,22,58,20)
同时要求考生输出9号主角(0,72,55,53,8,87,5),19号主角(0,11,4,63,22,60,18),47号主角(1,19,8,21,1,53,46),83号主角(1,23,11,17,58,31,11),99号主角(1,26,66,1,78,11,11)以及100号主角(0,68,28,19,43,11,46)的选择结果。
四、初赛阶段审核标准及评价细则
1. 功能分（40分）
如果学生最后答案错误，则该项得0分
如果答案正确，得40分
2. 代码质量分（30分）
可读性，整洁性，健壮性，可扩展性，封装性
3. 用户体验（10分）
界面美观,操作方便,有必要的信息提示
4. 代码文档质量（10分）
代码清晰，易读，注释完整
5. 单元测试（10分）
关键函数或容易出错部分应该有单元测试保证
#include <iostream> #include <fstream> #include <ostream> #include <vector> #include <algorithm> #include <ctime> #include <cstdlib> using namespace std; int M = 100; //表示匹配对数 //将人用类Person表示 struct Person{ int sex; int id; int fortune; int appearance; int character; int wFortune; int wAppearance; int wCharacter; int matchID; //匹配id号 int satisfyID; //当为男性是指最满意的对方id号，女性是指被邀请的数目 bool match; //是否成功，true表示已配对，false表示没有 Person(int s=0, int i=-2, int f=0, int a=0, int c=0, int wf=0, int wa=0, int wc=0, int mi=0, int si=0, bool m=false): sex(s),id(i),fortune(f),appearance(a),character(c), wFortune(wf),wAppearance(wa),wCharacter(wc),matchID(mi),satisfyID(si),match(m){} }; //为了在匹配时能唯一确定满意度顺序，定义了一个辅助类SatDegree用于重载">"运算符 struct SatDegree{ int satD; //对对方的满意度 int sum3; //对方三个属性的总和 int id; //对方的id号 SatDegree(int sd = 0, int s3 = 0, int i = -2):satD(sd), sum3(s3), id(i){} }; // 数据结构，男性、女性都按id+1依次存储，相当于hash表 vector<Person> male(M+1);//男性数组 vector<Person> female(M+1);//女性数组 //测试 vector<vector<int> > satm2fM(M+1,vector<int>(M+1,0)); vector<vector<int> > satf2mM(M+1,vector<int>(M+1,0)); vector<vector<int> > invitedM(M+1,vector<int>(2,0)); //重载">"号，当满意度相等时，其属性总和大的较大，但都相等时，id号小的大 bool operator >(const SatDegree& sd1, const SatDegree& sd2) { if (sd1.satD > sd2.satD) return true; else if (sd1.satD == sd2.satD) if (sd1.sum3 > sd2.sum3) return true; else if (sd1.sum3 == sd2.sum3) if (sd1.id <= sd2.id) //"=="号是考虑到自己同自己比较的情况 return true; else return false; else return false; else return false; } ostream& operator<<(ostream& os, const Person& p) { return os << p.fortune << \',\' << p.appearance << \',\' << p.character << \',\' << p.wFortune << \',\' << p.wAppearance << \',\' << p.wCharacter; } istream& operator>>(istream& is, Person& p) { char comma; return is >> p.id >> comma >> p.fortune >> comma >> p.appearance >> comma >> p.character >> comma >> p.wFortune >> comma >> p.wAppearance >> comma >> p.wCharacter; } int sum3(Person p) { return p.fortune+p.appearance+p.character; } SatDegree satisfy(Person p1,Person p2)//不同性别的p1对p2的满意度 { SatDegree SD; SD.satD = p1.wFortune*p2.fortune+p1.wAppearance*p2.appearance+p1.wCharacter*p2.character; SD.sum3 = p2.fortune+p2.appearance+p2.character; SD.id = p2.id; return SD; } void matching()//匹配过程 { int i = 0, j = 0, k = 0, l = 0, minID = M-1, //最小的未匹配的id号 satM2FID = -2, //男性最满意的女性的id satF2MID = -2, //女性最满意的男性的id invitedN = 0, //女性的被邀请数临时变量 matchedFID = -1, noMatchNo = M; //匹配成功的女性id号及配对数 SatDegree m2f, f2m,//男性对女性的满意度、女性对男性的满意度 satFD, satMD; //男性对女性的满意度及女性对男性的满意度的临时变量 //vector<int> atemp(M,-1), btemp(M,-1); for ( ; noMatchNo > 0; --noMatchNo) { //测试 //cout << "匹配第" << noMatchNo << "队情况：" << endl; for (i = 0; i<= M; ++i) //依次寻找未匹配男性i的最满意id号及获得对应的女性邀请数目 { if (!male[i].match && male[i].id >= -1) //male[0]存储的是主角或者空，空时不处理 { for (j = 0; j <= M; ++j) { if (female[j].id < -1)//female[0]存储的是主角或者空，空时不处理 continue; m2f = satisfy(male[i],female[j]); satm2fM[i][j] = m2f.satD; if (m2f > satFD && !female[j].match) { satM2FID = j-1; //id号是hash表序号-1 satFD = m2f; } //测试： //cout << "男性id=" << i-1 << ",女性id=" << j-1 << ",对女性的满意度" << m2f.satD << endl << endl; } ++female[satM2FID+1].satisfyID; //对应女性的被邀请数目加1 male[i].satisfyID = satM2FID; satFD.satD = 0; satFD.sum3 = 0; satFD.id = -2; //重置临时的男对女满意度 //测试： //if (noMatchNo == M) // cout << "男性id=" << i-1 << ",最喜欢的女性id=" << satM2FID << endl; } } //测试 //cout << endl << "寻找邀请数最多的女性：" << endl; for (k = 0; k <= M; ++k) //寻找邀请数最多的女性id { if (female[k].id < -1)//female[0]存储的是主角或者空，空时不处理 continue; if (!female[k].match) //k的id不小于matchedFID if ((female[k].satisfyID > invitedN) ||//k的选票大于matchedID的 ((female[k].satisfyID == invitedN) && //k的选票等于matchedID的 (sum3(female[k]) > sum3(female[matchedFID+1]))))//k的属性和大于matchedID的 { invitedN = female[k].satisfyID; matchedFID = k-1; } } invitedM[M-noMatchNo][0] = matchedFID; invitedM[M-noMatchNo][1] = invitedN; //测试 //cout << "邀请数最多的女性id=" << matchedFID << "，邀请数" << invitedN << endl // << endl << "寻找匹配的男性:" << endl; invitedN = 0; //被邀请数临时变量重置为0 for (l = 0; l <= M; ++l) //寻找匹配的男性 { if (male[l].id < -1) //male[0]存储的是主角或者空，空时不处理 continue; f2m = satisfy(female[matchedFID+1],male[l]);satf2mM[matchedFID+1][l] = f2m.satD; if (male[l].satisfyID == matchedFID && !male[l].match && f2m > satMD) { satF2MID = l-1; satMD = f2m; } } //测试 //cout << "匹配男性id=" << satF2MID << ",满意度" << satMD.satD << endl; male[satF2MID+1].match = true; male[satF2MID+1].matchID = matchedFID; satMD = 0;satMD.sum3 = 0;satMD.id = -2;//重置临时的女对男满意度 //测试 //atemp[satF2MID] = satF2MID; btemp[matchedFID] = matchedFID; //cout << noMatchNo << "," << satF2MID << "," << matchedFID << endl; minID = M; for (k = 0; k <= M; ++k)//删除未匹配的女性的邀请数且将matchedFID重置为未匹配女性中的最小id号 { if (female[k].id < -1)//female[0]存储的是主角或者空，空时不处理 continue; if (!female[k].match && k !=matchedFID+1 && female[k].satisfyID <= female[matchedFID+1].satisfyID) { female[k].satisfyID = 0; if ((k-1) < minID) minID = k-1; } } female[matchedFID+1].match = true; //删除匹配的女性 female[matchedFID+1].matchID = satF2MID; matchedFID = minID; } } int random(int x) { return rand()%x; } //随机初始化一个人的属性(ID除外） Person randPerson() { Person p; p.fortune = random(M)+1; p.appearance = random(M)+1; p.character = random(M)+1; p.wFortune = random(M-2)+1; p.wAppearance = random(M-p.wFortune)+1; p.wCharacter = M-p.wFortune-p.wAppearance; return p; } //随机生成数据、初始化并将其保存到对应的hash表中 void generateData(Person user) { vector<int> randSort1(M), randSort2(M); Person p1, p2; int i = 0; ofstream ofs1, ofs2; //任意排列0-M之间的数 for (i = 0; i<M; ++i) { randSort1[i] = i; randSort2[i] = i; } random_shuffle(randSort1.begin(),randSort1.end()); random_shuffle(randSort2.begin(),randSort2.end()); //随机生成男性和女性数据 ofs1.open("male1.txt",ios_base::out); ofs2.open("female1.txt",ios_base::out); for (i = 0; i<M; ++i) { p1 = randPerson(); p1.sex = 1;p1.id = randSort1[i]; if (1 == user.sex && 0 == randSort1[i]) //用户是男性则将其替换为生成的0号id数据 p1 = user; male[p1.id+1] = p1; ofs1 << p1.id << "," << p1 << endl; p2 = randPerson(); p2.sex = 0;p2.id = randSort2[i]; if (1 == user.sex && 0 == randSort2[i]) //用户是女性则将其替换为生成的0号id数据 p1 = user; female[p2.id+1] = p2; ofs2 << p2.id << "," << p2 << endl; } ofs1.close(); ofs2.close(); } //读入文本数据并初始化以及进行测试 void readData() { Person p1, p2; ifstream ifs1, ifs2; ifs1.open("male.txt",ios_base::in); ifs2.open("female.txt",ios_base::in); while((ifs1 >> p1) && (ifs2 >> p2)) { male[p1.id+1] = p1; female[p2.id+1] = p2; } ifs1.close(); ifs2.close(); } //将结果保存到文本文件中 void result() { int i = 0, j = 0; ofstream ofs1, ofs2, ofs3, ofs4; ofs1.open("satm2fM.txt",ios_base::out); //保存男对女的满意度矩阵 ofs2.open("satf2mM.txt",ios_base::out); //保存女对男的满意度矩阵 ofs3.open("matched.txt",ios_base::out); //保存匹配结果 ofs4.open("invitedM.txt",ios_base::out);//保存女性被邀请的最多的id号及次数 for (i = 0; i <=M; ++i) { for (j = 0; j <= M; ++j) { ofs1 << satm2fM[i][j] <<","; ofs2 << satf2mM[i][j] <<","; } ofs1 << endl << endl; ofs2 << endl << endl; } for (i = 0; i <= M; ++i) { ofs3 << i << ":" << male[i].id <<"," << male[i].matchID << endl; ofs4 << i << ":" << invitedM[i][0] <<"," << invitedM[i][1] << endl; } ofs1.close(); ofs2.close(); ofs3.close(); ofs4.close(); } //程序开始 void startProg() { char ch, //用于接收用户选项：是想测试还是直接计算 E = \'n\', //用于接收用户输入：是否退出程序 comma; int line = 0; //指定读入的行 Person user; ifstream ifs; cout << "===========数字化婚姻配对尝试仿真程序===========" << endl; cout << "主角的信息包括：性别,样貌,品格,财富,期望样貌,期望品格,期望财富：" << endl << "输入时请按该要求依次输入主角信息!" << endl << "示例1：1,80,5,29,25,62,13；示例2：0,1,99,78,84,14,2" << endl; cout << "您是想测试用例还是自己输入数据进行计算？（测试输入T/t,计算输入C/c）" << endl; cin >> ch; if (\'T\' == ch || \'t\' == ch)//测试 { ifs.open("players.txt",ios_base::in); ifs.seekg(0,ifs.end); int line_lenght = ifs.tellg()/M; //计算players.txt文件每一行的长度 while (E != \'Y\' && E != \'y\') { readData(); cout << "请输入所给用户示例文件players.txt中主角所在的行数："; cin >> line; ifs.seekg((line-1)*line_lenght,ifs.beg); ifs >> user.sex >> comma >> user.fortune >> comma >> user.appearance >> comma >> user.character >> comma >> user.wFortune >> comma >> user.wAppearance >> comma >> user.wCharacter; user.id = -1; cout << line << "号主角的信息为:" << endl; cout << user << endl; if (1 == user.sex) //主角是男性 { male[0] = user; matching(); cout << "与主角匹配的属性值为：" << female[male[0].matchID+1] << endl; } else//主角是女性 { female[0] = user; matching(); cout << "与主角匹配的属性值为：" << male[female[0].matchID+1] << endl; } result(); cout << "是否结束?(是Y/y)或(否N/n)："; cin >> E; } ifs.close(); } else if (\'C\' == ch || \'c\' == ch) //计算 { while (E != \'Y\' && E != \'y\') { cout << "请输入主角的属性值："; cin >> user.sex >> comma >> user.fortune >> comma >> user.appearance >> comma >> user.character >> comma >> user.wFortune >> comma >> user.wAppearance >> comma >> user.wCharacter; user.id = 0; generateData(user);//生成数据 matching(); if (1 == user.sex) //主角是男性 cout << "与主角匹配的属性值为：" << female[male[user.id+1].matchID+1] << endl; if (0 == user.sex) //主角是男性 cout << "与主角匹配的属性值为：" << male[female[user.id+1].matchID+1] << endl; result(); cout << "是否结束：是Y/y或否N/n："; cin >> E; } } else cout << "error!" << endl; } int main() { srand((int)time(0)); startProg(); return 0; }
View Code
版权声明：本文为lyfruit原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。