結對者： 031402324 巫振格
031402338 解宇虹
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("無法打開檔案!\n");
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\t%d\n",i,tea[i]);
fprintf(f1,"\n\n");
for(i = 0;i < STUNUM;i++)
{
fprintf(f1,"%d\t%.3f\t\t",i,rand() % 5000 / 1000.0);//随機生成學生績點，保留三位小數
for(j = 0;j < ASPIRATION;j++)
fprintf(f1,"%d\t",rand() % TEANUM);//随機生成志願
fprintf(f1,"\n");
}
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\t",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("\n");
}
}
}
學生志願與導師比對
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,"師生比對資訊:\n\n");
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,"\n");
}
}
void printStu(Student stu[][ASPIRATION],FILE *f2)
{
int i,j,sum = 0;
fprintf(f2,"\n\n未被導師選中的學生: ");
for(i = 0;i < STUNUM;i++)
if(!stu[i][j].chosen)
{
sum++;
fprintf(f2,"%d ",stu[i][0].stuNum);
}
fprintf(f2,"\n共 %d 個\n",sum);
fprintf(f2,"\n\n");
}
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,"\n共 %d 個\n",sum);
}
4）算法評價的最終目标分析
算法最終實作對于同一組輸入，輸出的未被導師選中的學生數越少越好。為此我們小組将學生和老師的數量減少，做了個測試，測試結果如下表所示：
從折線中可以看出，這個算法基本實作學生的完全比對，但是另一方面，沒有學生選的導師也比較多。這部分導師主要是滿額學生數少與算法本身造成的。滿額數少根據公式cpt(m,n)=m/n，m為實報人數，n為滿額人數，容易得出競争度cpt較高，然而實際選的學生數可能并不多，根據算法競争度高的要到後期比對，本來有選這個導師的學生因為其他導師的比對成功可能導緻該導師能夠比對的學生數急劇減少，甚至無法比對，是以滿額度低的導師容易選不到學生。另一方面，因為從低競争度開始比對，是以學生就能夠比較高度比對。
四、結對程式設計及感悟
我們小組是男女搭配的小組，不同的腦回路帶來的肯定是思想上的各種摩擦，但是摩擦過後迎來的肯定是思想的融合。是以我們的任務完成的也算成功，接下來是我們兩結對過程中的感受及對對方的看法。
解宇虹：結對程式設計真的是一個互相學習的好機會，在這個過程中，當對方有問題的時候可以互相讨論，并及時提出相應的措施，避免了大量時間的浪費，提高了我們代碼的學習成本。但在這次結對程式設計中最大的感受就是當兩個人對一個問題各持己見時引發的“口水戰”。雖然我是女生，但是我性子有點急，還好我的隊友夠耐心，每次遇到這種情況都能不驕不躁，并且努力讓我了解他的想法，靜下心來思考，我想這是他身上最大的閃光點。
巫振格：這次結對程式設計感覺還是比較耗時間的，開始連題目都有一點懵逼，後來開始讨論算法的規則，一個一個點的考慮，還是有很多不足之處，想的不全面，導緻後來走了彎路，設計了一個不太高效的算法，有4、5、6、7個學生未比對都有，再就是翹課重編了……然後就一直讨論，後面勉強憋了一個程式出來，勉強看。總的體會就是，結對讨論确實可以彌補一個人的不足，也可以讓人互相督促，互相進步。
附件：智能比對算法源程式