结对者：031402324 巫振格 031402338 解宇虹
一、作业的内容
编码实现一个毕设导师的智能匹配的程序。提供输入包括：30个老师（包含带学生数的要求的上限，单个数值，在[0,8]内），100个学生（包含绩点信息），每个学生有5个导师志愿（志愿的导师可以重复但不能空缺）。实现一个智能自动分配算法，根据输入信息，输出导师和学生间的匹配信息（一个学生只能有一个确认导师，一个导师可以带少于等于其要求的学生数的学生） 及 未被分配到学生的导师 和 未被导师选中的学生。
二、要求
1、输入的数据，另外写生成程序随机实现。
2、为输入输出设计标准化、通用化、可扩展的接口，为该智能匹配程序模块后期可能的整合入系统提供便利。
3、输入输出的格式，如采用文本文件或数据库的方式输入，可自由讨论确定，但需要明确，为后期可能的整合入系统提供便利。
4、需要为智能匹配算法确立几条分配或排序原则，比如 绩点优先、或其他、或其他等等，请你们结对讨论确定。
5、算法评价的目标是：对于同一组输入，输出的未被导师选中的学生数越少越好。
三、算法及代码实现过程
1、智能智能算法思想
算法思想一:权重值
权重值即将志愿与绩点，根据一个评价函数打分得到权重值，最后学生将根据权重值从大到小排序
#define p 0.5
w(v,s)=pv+(1-p)s//第p志愿，s为绩点
分析：
好处：绩点高的学生即便第五志愿也可能比绩点低的学生的第一志愿更有竞争力，保证了绩点高的学生的选择权
坏处：评价函数决定了最终的分配，但权重比例难以确定，而且绩点低的学生可竞争力更弱
由于权重比例难以确定，所以我们设定比例为p，然后去实验出一个较优的p，可以更加接近目标，最终我们算法确定p为0.5。
算法思想二:导师流行度
导师竞争度即某导师实际报的学生数与该导师满额人数之商，即竞争度 = 实报人数/满额人数，按照竞争度从小到大给老师排序。
cpt(m,n)=m/n //m为实报人数，n为满额人数
分析：
好处：导师流行度可以尽量使所有学生都选到导师
坏处：存在一种极端情况，当导师所带的学生名额很少，学生选择导师的数量多的情况下，这个导师很可能选不到学生，具体会在下文算法评价中指出。
经过讨论，我们将两个思想结合，兼顾所有学生，以相对的公平，保证他们选择心怡老师的权利。具体规则如下：
1）从志愿一开始筛选到志愿五，共五轮筛选，规则均相同；
2）计算每个导师的竞争度，按照竞争度从小到大排序，确定优先匹配的导师；
3）计算每个学生的权重值，按照权重值从大到小排序，确定被选择的优先权；
4）每一轮，从优先匹配的导师的角度出发，选择符合条件学生，如果一个导师带的学生有名额，就将选择这个导师的学生权重值从大到小筛选学生，若导师在本轮筛选中未选满所有名额，则按相同规则在下一轮继续筛选。
2、代码实现分析
1）用程序随机生成输入的数据
主要函数：
void srand(unsigned seed)：随机数发生器的初始化函数。
代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TEANUM 30
#define STUNUM 100
#define ASPIRATION 5
#define TXTNAME "data.txt"
int main()
{
FILE *f1;
if((f1 = fopen(TXTNAME,"w")) == NULL)
{
printf("无法打开文件!
");
return 0;
}
int i,j,tea[TEANUM];
srand((unsigned)time(NULL));//随机数种子初始化
while(1)
{
int sum = 0;
for(i = 0;i < TEANUM;i++)
{
tea[i] = rand() % 9;//随机生成导师所带人数
sum += tea[i];
}
if(sum >= STUNUM)break;
}
for(i = 0;i < TEANUM;i++)
fprintf(f1,"%d %d
",i,tea[i]);
fprintf(f1,"
");
for(i = 0;i < STUNUM;i++)
{
fprintf(f1,"%d %.3f ",i,rand() % 5000 / 1000.0);//随机生成学生绩点，保留三位小数
for(j = 0;j < ASPIRATION;j++)
fprintf(f1,"%d ",rand() % TEANUM);//随机生成志愿
fprintf(f1,"
");
}
return 0;
}
分析：这个程序随机生成导师所带的学生数，学生的绩点以及志愿；学生绩点需要保留三位小数，采用生成0-5000之间的随机数，再除以1000.0得到的。
2）输入输出的格式及实现语言
我们使用最熟悉的C语言编写程序，而且代码规范，可读性强；输入输出的格式，均采用文本文件，程序实现均用函数封装，具有标准化、通用化、可扩展的接口，为该智能匹配程序模块后期可能的整合入系统提供便利。
3）智能匹配算法程序实现
文件读入
void read(Teacher tea[],Student stu[][ASPIRATION],FILE *f1)
{
int i,j;
for(i = 0;i < TEANUM;i++)
{
fscanf(f1,"%d%d",&tea[i].teaNum,&tea[i].leadNum);
tea[i].popular = 0;
tea[i].full = false;
}
for(i = 0;i < STUNUM;i++)
{
fscanf(f1,"%d%lf",&stu[i][0].stuNum,&stu[i][0].score);
for(j = 1;j < ASPIRATION;j++)
stu[i][j].stuNum = stu[i][0].stuNum;
for(j = 0;j < ASPIRATION;j++)
{
fscanf(f1,"%d",&stu[i][0].aspiration[j]);
stu[i][0].evalScore[j] = 0;
stu[i][j].chosen = false;
}
stu[i][0].next = NULL;
}
}
评价函数
void evaluate(Student stu[][ASPIRATION])
{
int i,j;
for(i = 0;i < STUNUM;i++)
{
for(j = 0;j < ASPIRATION;j++)
stu[i][0].evalScore[j] = (j + 1) * (1 - SCORE_PERCENT) + stu[i][0].score * SCORE_PERCENT;
}
}
按照导师竞争度排序
void sort(Student *leadStu[],Teacher tea[])
{
int i,j;
for(i = 0;i < TEANUM;i++)
{
for(Student *p = leadStu[i];p;p = p->next)
{
tea[i].popular++;
}
if(tea[i].leadNum)
tea[i].popular /= (double)tea[i].leadNum;
else tea[i].popular = 0;
}
for(i = 0;i < TEANUM;i++)
{
for(j = i;j < TEANUM;j++)
{
if(tea[i].popular > tea[j].popular)
{
Teacher temp = tea[i];
tea[i] = tea[j];
tea[j] = temp;
}
}
}
}
导师选择学生
void teaSelect(Teacher tea[],Student *leadStu[],Student stu[][ASPIRATION])
{
int i,j,num;
for(i = 0;i < TEANUM;i++)
{
num = 0;
if(!tea[i].full)
{
//printf("%d ",i);
for(Student *p = leadStu[tea[i].teaNum];p && num < tea[i].leadNum;p = p->next)
{
if(p->chosen)continue;
tea[i].teaLeadStu[num++] = p->stuNum;
for(j = 0;j < ASPIRATION;j++)
{
stu[p->stuNum][j].chosen = true;
}
//printf("%d ",num);
}
if(num == tea[i].leadNum) tea[i].full = true;
tea[i].realNum = num;
//printf("
");
}
}
}
学生志愿与导师匹配
void stuChoose(Student stu[][ASPIRATION],Student *leadStu[])
{
int i,j,num;
for(i = 0;i < ASPIRATION;i++)
{
for(j = 0;j < STUNUM;j++)
{
num = stu[j][0].aspiration[i];
if(leadStu[num])
{
Student *p = leadStu[num]->next,*up = leadStu[num];
if(stu[j][0].evalScore[i] > leadStu[num]->evalScore[i])
{
stu[j][i].next = leadStu[num];
leadStu[num] = &stu[j][i];
continue;
}
for(;p;up = p,p = p->next)
{
if(stu[j][i].evalScore[i] > p->evalScore[i])
{
Student *temp = up->next;
up->next = &stu[j][i];
stu[j][i].next = temp;
break;
}
}
if(p == NULL)
{
up->next = &stu[j][i];
stu[j][i].next = NULL;
}
}
else
{
leadStu[num] = &stu[j][i];
stu[j][i].next = NULL;
}
}
}
}
打印匹配结果
void printMatch(Teacher tea[],FILE *f2)
{
int i,j;
fprintf(f2,"师生匹配信息:
");
for(i = 0;i < TEANUM;i++)
{
fprintf(f2,"导师号: %3d 满额: %d 实招: %d 学生号: ",tea[i].teaNum,tea[i].leadNum,tea[i].realNum);
for(j = 0;j < tea[i].realNum;j++)
fprintf(f2,"%d ",tea[i].teaLeadStu[j]);
fprintf(f2,"
");
}
}
void printStu(Student stu[][ASPIRATION],FILE *f2)
{
int i,j,sum = 0;
fprintf(f2,"
未被导师选中的学生: ");
for(i = 0;i < STUNUM;i++)
if(!stu[i][j].chosen)
{
sum++;
fprintf(f2,"%d ",stu[i][0].stuNum);
}
fprintf(f2,"
共 %d 个
",sum);
fprintf(f2,"
");
}
void printTea(Teacher tea[],FILE *f2)
{
int i,sum = 0;
fprintf(f2,"未被学生选的导师: ");
for(i = 0;i < TEANUM;i++)
if(tea[i].realNum == 0)
{
sum++;
fprintf(f2,"%d ",tea[i].teaNum);
}
fprintf(f2,"
共 %d 个
",sum);
}
4）算法评价的最终目标分析
算法最终实现对于同一组输入，输出的未被导师选中的学生数越少越好。为此我们小组将学生和老师的数量减少，做了个测试，测试结果如下表所示：
从折线中可以看出，这个算法基本实现学生的完全匹配，但是另一方面，没有学生选的导师也比较多。这部分导师主要是满额学生数少与算法本身造成的。满额数少根据公式cpt(m,n)=m/n，m为实报人数，n为满额人数，容易得出竞争度cpt较高，然而实际选的学生数可能并不多，根据算法竞争度高的要到后期匹配，本来有选这个导师的学生因为其他导师的匹配成功可能导致该导师能够匹配的学生数急剧减少，甚至无法匹配，所以满额度低的导师容易选不到学生。另一方面，因为从低竞争度开始匹配，所以学生就能够比较高度匹配。
四、结对编程及感悟
我们小组是男女搭配的小组，不同的脑回路带来的肯定是思想上的各种摩擦，但是摩擦过后迎来的肯定是思想的融合。所以我们的任务完成的也算成功，接下来是我们两结对过程中的感受及对对方的看法。
解宇虹：结对编程真的是一个互相学习的好机会，在这个过程中，当对方有问题的时候可以互相讨论，并及时提出相应的措施，避免了大量时间的浪费，提高了我们代码的学习成本。但在这次结对编程中最大的感受就是当两个人对一个问题各持己见时引发的“口水战”。虽然我是女生，但是我性子有点急，还好我的队友够耐心，每次遇到这种情况都能不骄不躁，并且努力让我理解他的想法，静下心来思考，我想这是他身上最大的闪光点。
巫振格：这次结对编程感觉还是比较耗时间的，开始连题目都有一点懵逼，后来开始讨论算法的规则，一个一个点的考虑，还是有很多不足之处，想的不全面，导致后来走了弯路，设计了一个不太高效的算法，有4、5、6、7个学生未匹配都有，再就是翘课重编了……然后就一直讨论，后面勉强憋了一个程序出来，勉强看。总的体会就是，结对讨论确实可以弥补一个人的不足，也可以让人相互督促，互相进步。
附件：智能匹配算法源程序