031402313 黄志明 031402431 章鼎
github链接:
问题重述
编码实现一个毕设导师的智能匹配的程序。提供输入包括：30个老师（包含带学生数的要求的上限，单个数值，在[0,8]内），100个学生（包含绩点信息），每个学生有5个导师志愿（志愿的导师可以重复但不能空缺）。实现一个智能自动分配算法，根据输入信息，输出导师和学生间的匹配信息（一个学生只能有一个确认导师，一个导师可以带少于等于其要求的学生数的学生）及 未被分配到学生的导师 和 未被导师选中的学生。
问题分析
共有一百名学生需要选择三十名导师中五位作为自己的志愿，学生中比较有说服力的一项指标是绩点，所以我们先用
一开始的想法是按绩点排名来决定分配导师次序，即绩点绩点高低来排名100位学生。排名靠前的学生先分配导师，绩点越靠后的同学越后分配导师，但是这样一来就会出现一个问题——大部分成绩靠后的同学很难选到自己想要的导师，这对他们存在着一些不公平，谁说成绩不好的同学中没有某方面的强项呢？经过与队友讨论，我们决定将绩点排名的前20%以及后20%单独划分出来进行导师分配，方法是先按绩点排名相反次序先后来分配后20%的学生，再用绩点排名次序先后来分配后20%的学生。分配完成后，余下的60%的学生，也就是绩点排名在中间的学生，我们采用由两端向中心夹逼的分配方法，即排名第21的同学最先分配，然后是排名第80的同学，再然后是排名第22的同学······直到第50、51名同学完成分配。 这样的分配方法既能保证成绩优异同学选到自己想要的导师，又能兼顾成绩较差的同学不会一大片的落选。
代码分析
基本数据结构
#include#include #include #include #include #include using namespace std;//学生结构体struct stu { int num; //学号 double c; //绩点 bool chose; //是否被选择 int teacher[6]; //所选择的导师数组};//导师所拥有学生的结构体struct stu2 { int num; double c;};//导师结构体struct tea { vector student; //所拥有的学生结构体向量组 int o; //当前所拥有的学生数 int up_limit; //所能带学生的最大数量 int chosen[9]; //最终所选择的学生数组};
随机数据生成
srand(time(0)); int ini = 313; int t[tno]; for (int i = 1; i <= tno; i++) t[i] = i; fprintf(fout,"%d\n",sno); for (int i = 0; i < sno; i++) { ini++; double c = 2.5; string s="031402"; cout << s << ini << " "; c += (rand() % 10) / 10.0; cout << c << " "; int o1, o2, o3, o4, o5; o1 = rand() % tno; o2 = rand() % tno; o3 = rand() % tno; o4 = rand() % tno; o5 = rand() % tno; if(t[o1]>tno||t[o1]<0) t[o1]=tno; if(t[o2]>tno||t[o2]<0) t[o2]=tno; if(t[o3]>tno||t[o3]<0) t[o3]=tno; if(t[o4]>tno||t[o4]<0) t[o4]=tno; if(t[o5]>tno||t[o5]<0) t[o5]=tno; cout << t[o1] << " " << t[o2] << " " << t[o3] << " " << t[o4] << " " << t[o5]; cout << endl; } 分配算法
//绩点靠后的20%先排序，按排名先后相反次序进行分配 for (int i = snum - 1; i > snum - (snum / 5); i--) { for (int j = 0; j < 5; j++) { int tno = S[i].teacher[j]; //tno为导师编号 //判断该导师还有没有剩余名额，有的话将自己注册进去 if (T[tno].o < T[tno].up_limit) { int to = T[tno].o; T[tno].chosen[to] = S[i].num; T[tno].o++; count++; S[i].chose = true; break; } //若果该学生的第一志愿导师满了的话，就跳到第二志愿去选导师，以此类推 else continue; } } //前20%学生排序，按排名正向先后分配 for (int i = 0; i < snum / 5; i++) { for (int j = 0; j < 5; j++) { int tno = S[i].teacher[j]; if (T[tno].o < T[tno].up_limit) { int to = T[tno].o; T[tno].chosen[to] = S[i].num; T[tno].o++; count++; S[i].chose = true; break; } else continue; } } int p = snum / 5; int k = (snum * 4) / 5; snum为学生总人数，每位学生按志愿先后顺序来进行导师分配，若第一志愿导师人数未达到上限，则将该学生分配进去，若第一志愿导师人数已满，则自动换到第二志愿分配，以此类推，如果直到第五志愿导师都被报满，则跳出循环。
//接下来进行排名居中的60%的同学选导师，分为两个部分，同时进行，选择原理相似 for (int i = 0;; i++) { //从21%往后选到50% for (int j = 0; j < 5; j++) { int tno = S[p].teacher[j]; if (T[tno].o < T[tno].up_limit) { int to = T[tno].o; T[tno].chosen[to] = S[p].num; T[tno].o++; count++; S[p].chose = true; break; } else { continue; } } p++; if (p - 1 == k) break; //从79%往前选择到50% for (int j = 0; j < 5; j++) { int tno = S[k].teacher[j]; if (T[tno].o < T[tno].up_limit) { int to = T[tno].o; T[tno].chosen[to] = S[k].num; T[tno].o++; count++; S[k].chose = true; break; } else continue; } k--; if (p > k) break; } 进行排名居中的60%的同学选导师，分为两个部分，同时进行，分配原理与上面相似
结果分析
测试数据例子
输入：
输出：
输出结果分析
随机生成了十组数据，平均中选人数为97.1人，还是比较好的。
再随机生成了十组数据来统计前20%，后20%，以及中间60%的人的中选人数
发现，只有中间的人选不中导师，说明此算法比较成功的保护了排名靠前跟靠后的同学
小结与感受
章鼎
本次实验看似类似C++编程题，但要考虑的点却相当复杂，如怎么分配学生才可以让未选到导师的学生尽可能少？如何做到对“热门”导师和“冷门”导师的合理分配？什么样的分配是公平公正可以深得同学们人心？考虑的越多就越不知该如何下手，经过不断讨论，我们决定采用这种“朴素”的算法来解决这些问题，让成绩优异的同学如愿以偿的选到理想导师的同时，兼顾成绩落后的同学，减少他们选不到导师的可能，虽说这种做法“牺牲”了中间一小部分同学的利益，但是从分析结果来看效果还是不错的。
经过几天的摸索和学习，感觉收获还是挺多的，从中学到如何先倾听队友的思路，再加上自己的想法，不急着打断队友，学会倾听下一步才是合作。
黄志明
考虑到实际情况，在没见过学生的情况下，导师选择学生一般是根据两点：1.绩点排名 2.志愿顺序 。这就导出了我们的算法，一般情况下，绩点比较低的学生，很容易在绩点排序的情况下，一轮轮地被刷下来，直到五个志愿都选完了都还没选到导师。所以，我们的算法要照顾绩点靠后的同学，保证绩点靠前的同学，让他们先选，中间的同学就算个别没选到一般情况下也不会有太大抱怨，这种算法反而会给靠后的同学带来惊喜。写了好几天的代码，文件的输入输出，大一的C++忘光了，可是用刚学的JAVA很多也是不会，只能重新拿起C++，一点一点地写。写完测试以后，感觉挺有成就感的，测试结果还不错，配对成功率很高！