1.結隊隊員
031502443 鄭書豪
031502404 陳邡
2.GitHub連結
jiedui2
3.問題重述
編碼實作一個部門與學生的智能比對的程式。部門有資料：部門标簽，部門人數限制，部門時間段，部門編号；學生有資料：學生編号，學生興趣标簽，學生空閑時間段，部門意願。這些資料由程式設計實作自動生成，在進行智能比對的程式，将學生合理的分到各個部門，使無學生的部門較少，無部門的學生較少，為較合理的比對。
4.資料模組化&生成資料
- 學生類
class Students
{
private:
string free_t[20];//學生空閑時間
string stu_no;//學生号
string app_dep[5];//學生志願部門
string s_tags[10];//學生标簽
public:
int s_time[7][40];//空閑時間數組
void set_free_t(string ft[]);//空閑時間指派
void set_stu_no(string sn);//學生号指派
void set_app_dep(string ad[]);//志願部門指派
void set_s_tags(string st[]);//标簽指派
void get_time();//空閑時間計算
string get_stu_no();//獲得學生号
string get_app_dep(int n);//獲得志願部門
string *get_s_tags();//獲得标簽
};
- 部門類
class Departments
{
private:
string e_sche[10];//部門活動時間
int mem_lmt;//部門納新人數
string dep_no;//部門号
string d_tags[10];//部門标簽
public:
struct acc_stu
{
acc_stu() { s_no = 0; s_sum = 0; }
int s_no;
int s_sum;
};//納新成員結構體
acc_stu a_s[15];//納新成員結構體數組
int d_time[7][20];//活動時間數組
void set_e_sche(string es[]);//活動時間指派
void set_mem_lmt(int ml);//納新人數指派
void set_dep_no(string dn);//部門号指派
void set_d_tags(string dt[]);//标簽指派
void get_time();//計算活動時間
int get_mem_lmt();//獲得部門納新人數
string get_dep_no();//獲得部門編号
string *get_d_tags();//獲得部門标簽
};
生成資料時，已生成部門标簽為例，先事先建構一個放标簽的數組，在進行随機數的生成去随機選取标簽（随機數生成時進行随機數的去重），由程式設定例如部門随機生成2~5個标簽，可由 int tags_num = rand() % 4 + 2 計算而得；以此類推......
- 學生資料的生成：
for (int i = 0; i < stu_num; i++)
{
Json::Value Stu;
for each(string s in stu[i].free_t)
{
if (s == "") break;
Stu["free_time"].append(s);
}
Stu["student_no"] = Json::Value(stu[i].stu_no);
for each(string s in stu[i].app_dep)
{
if (s == "") break;
Stu["applications_department"].append(s);
}
for each(string s in stu[i].s_tags)
{
if (s == "") break;
Stu["tags"].append(s);
}
root["students"].append(Stu);
}
- 部門資料的生成：
for (int i = 0; i < dep_num; i++)
{
Json::Value Dep;
for each(string s in dep[i].e_sche)
{
if (s == "") break;
Dep["event_schedules"].append(s);
}
Dep["member_limit"] = Json::Value(dep[i].mem_lmt);
Dep["department_no"] = Json::Value(dep[i].dep_no);
for each(string s in dep[i].d_tags)
{
if (s == "") break;
Dep["tags"].append(s);
}
root["departments"].append(Dep);
}
5.核心算法
算法中采用了由學生意願配置設定部門的形式。
算法步驟描述：
先将所有學生移入未配置設定部門的隊列，每個部門建立一個接受學生的優先隊列（意願優先級>興趣優先級=時間優先級）。
- 第一輪，先将所有未配置設定部門的隊列中有第一意願部門的學生找出，每個有第一意願部門的學生針對第一意願部門進行配置設定，會出現以下情況：1. 部門人數還沒有達到上限，學生的活動時間至少有一個時間段符合則接受該學生，該學生移出未配置設定部門的隊列，按興趣比對的個數和活動時間比對的個數兩者權重相同進行優先級計算，加入該部門的優先級隊列；2. 部門人數達到上限，則待配置設定的學生插入優先隊列，該學生移出未配置設定部門的隊列，再将優先隊列的最後一個學生移出優先隊列，該學生移入未配置設定隊列。
- 第二輪，先将所有未配置設定部門的隊列中有第二意願部門的學生找出，每個有第二意願部門的學生針對第二意願部門進行配置設定，會出現以下情況：1. 部門人數還沒有達到上限，學生的活動時間至少有一個時間段符合則接受該學生，該學生移出未配置設定部門的隊列，按興趣比對的個數和活動時間比對的個數兩者權重相同進行優先級計算（意願的優先級最高，固第二志願學生優先級一定低于第一志願學生，以此類推），加入該部門的優先級隊列；2. 部門人數達到上限，則待配置設定的學生插入優先隊列，該學生移出未配置設定部門的隊列，再将優先隊列的最後一個學生移出優先隊列，該學生移入未配置設定隊列。
- 第三輪……
- 第四輪……
- 第五輪……以此類推
- 第六輪，此時未配置設定部門的隊列中剩下的學生有：沒有意願部門的學生，意願部門已滿不接收的學生。此時所有未滿的部門計算優先級（興趣優先級設為時間優先級的兩倍），對未配置設定部門的學生進行配置設定（興趣标簽至少要有一個相同，時間段至少有一個符合），最後剩下學生為無法配置設定學生。
怎麼證明這個算法肯定能夠得到穩定的學生部門關系：
- （1） 前五輪的時候，根據學生自己的意願依次進行對學生進行部門的配置設定，學生每一輪的時候都根據給定的優先級進行學生的篩選，此時已配置設定的學生部門關系是穩定的。
- （2） 第六輪的時候，未配置設定部門的隊列中剩下的學生有：沒有意願部門的學生，意願部門已滿不接收的學生。是以不在考慮學生的意願，而按照學生的興趣進行劃分，隻要學生時間段至少有一個符合，興趣标簽至少要有一個相同，且該部門有空缺，就會被配置設定。最後剩下的學生意願部門已滿拒收，興趣部門時間不符，無法配置設定，此時的配置設定關系最為穩定。
算法流程圖：
- 前五輪比對：
//前五輪配置設定
//志願優先原則 學生優先級按照志願位置、時間比對次數、标簽比對次數進行權重計算 權重分别為 10、5、2
for (int q = 0; q < 5; q++)
{
for (int i = 0; i < stu_num; i++)
{
if (Stu[i].get_app_dep(q + 1) != "")
//學生第q個志願為空則不進行操作
{
for (int j = 0; j < dep_num; j++)
//将志願與部門比對
{
if (Stu[i].get_app_dep(q + 1) == Dep[j].get_dep_no())
//若比對
{
if (noInArray(Dep[j].a_s, i))
//若學生已進入該部門納新成員數組則不做考慮
{
continue;
}
if (acc[j] < Dep[j].get_mem_lmt() && cmp_time(Stu[i], Dep[j]) >= 1)
//志願部門人數未滿且時間至少比對一次
{
acc[j]++;//部門納新人數加一
sum = (5 - q) * 10 + cmp_time(Stu[i], Dep[j]) * 5 + cmp_tags(Stu[i], Dep[j]) * 2;//計算學生優先級
insert(Dep[j].a_s, sum, i, Dep[j].get_mem_lmt());//向部門納新數組插入學生
assign[i]++;//納入學生配置設定情況更新
}
else if (acc[j] == Dep[j].get_mem_lmt() && cmp_time(Stu[i], Dep[j]) >= 1)
//志願部門人數已滿且時間至少比對一次
{
sum = (5 - q) * 10 + cmp_time(Stu[i], Dep[j]) * 5 + cmp_tags(Stu[i], Dep[j]) * 2;//計算學生優先級
if (sum > Dep[j].a_s[Dep[j].get_mem_lmt() - 1].s_sum)
//若學生優先級大于部門納新數組中優先級最低成員則将其取代
{
assign[Dep[j].a_s[Dep[j].get_mem_lmt() - 1].s_no]--;//淘汰學生配置設定情況更新
insert(Dep[j].a_s, sum, i, Dep[j].get_mem_lmt());//向部門納新數組插入學生
assign[i]++;//納入學生配置設定情況更新
}
}
}
}
}
}
}
- 第六輪比對：
//第六輪配置設定
for (int k = 0; k < dep_num; k++)
{
if (acc[k] < Dep[k].get_mem_lmt())
//找出未滿的部門
{
for (int w = 0; w < stu_num; w++)
{
if (assign[w] == 0)
//若學生未進入任何部門
{
if (acc[k] < Dep[k].get_mem_lmt() && cmp_time(Stu[w], Dep[k]) >= 1 && cmp_tags(Stu[w], Dep[k]) >= 1)
//志願部門人數未滿且時間至少比對一次且标簽至少比對一次
{
acc[k]++;//部門納新人數加一
sum = cmp_time(Stu[w], Dep[k]) + 2 * cmp_tags(Stu[w], Dep[k]);//計算學生優先級
insert(Dep[k].a_s, sum, w, Dep[k].get_mem_lmt());//向部門納新數組插入學生
assign[w]++;//納入學生配置設定情況更新
}
else if (acc[k] == Dep[k].get_mem_lmt() && cmp_time(Stu[w], Dep[k]) >= 1 && cmp_tags(Stu[w], Dep[k]) >= 1)
//志願部門人數已滿且時間至少比對一次且标簽至少比對一次
{
sum = cmp_time(Stu[w], Dep[k]) + 2 * cmp_tags(Stu[w], Dep[k]);//計算學生優先級
if (sum > Dep[k].a_s[Dep[k].get_mem_lmt() - 1].s_sum)
{
assign[Dep[k].a_s[Dep[k].get_mem_lmt() - 1].s_no]--;//淘汰學生配置設定情況更新
insert(Dep[k].a_s, sum, w, Dep[k].get_mem_lmt());//向部門納新數組插入學生
assign[w]++;//納入學生配置設定情況更新
}
}
}
}
}
}
6.結果分析
| 次數 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 平均 |
| 學生數 | 300 | ||||||||||
| 部門數 | 20 | ||||||||||
| 未比對學生 | 22 | 15 | 18 | 14 | 23 | 27 | |||||
| 未比對部門 |
7.代碼規範
- 命名：類名用的是第一個字母大寫，函數名采用駝峰命名法，局部變量根據需要采用平時常用的命名，對于命名，基本的要求是見名知意。
- 運算符間隔：一進制運算符不做間隔處理，二進制運算符前後各加一個空格。
- 注釋：簡單的程式沒注釋，複雜的程式注釋放在相應語句的上方。相應變量的注釋放到右邊。
- 代碼示例
/*
活動/空閑時間比對函數
輸入：單個學生類對象，單個部門類對象
傳回：學生和部門對象時間比對次數
*/
int cmp_time(Students s, Departments d)
{
int cnt = 0;//次數統計
for (int i = 0; i < 7; i++)
{
for (int j = 0; j < 20; j++)
{
if (d.d_time[i][j] == 0)
//若目前時間點為0則繼續讀取(一個時間段在時間數組中占2個位置，向後兩位進行下一時間段讀取)
{
j++;
continue;
}
for (int k = 0; k < 40; k++)
{
if (s.s_time[i][k] == 0)
//若目前時間點為0則繼續讀取(一個時間段在時間數組中占2個位置，向後兩位進行下一時間段讀取)
{
k++;
continue;
}
if (d.d_time[i][j] >= s.s_time[i][k] && d.d_time[i][j + 1] <= s.s_time[i][k + 1])
//若時間段比對則計數加一
cnt++;
//計數後繼續讀取(一個時間段在時間數組中占2個位置，向後兩位進行下一時間段讀取)
k++;
}
}
}
return cnt;
}
8.程式評價
本學生部門智能配置設定程式的配置設定結果基本滿足了題意要求，但是程式尚且存在着一些不足。在随機生成的學生資訊和部門資訊資料和現實生活中有所偏頗。學生的空閑時間大多集中在周末，而部門一般也會根據學生的時間來設定正常活動時間。興趣标簽，現實中往往幾種标簽的人數比較多，而一些冷門興趣人數較少，不應該是随機的配置設定。該程式通過六輪的比對，将沒有意願部門，沒有時間段參加部門，沒有興趣與部門相同的人篩選了出來。
9.結隊感受
結隊來說，好慶幸抱着了大腿，兩個人的合作中也學到了很多東西。比如，變成習慣非常不良好的我，開始的時候一般都不會去幾個源檔案，而是函數，類，全局變量，main（）函數......全部扔到一個源檔案中間去，以及平常寫函數時的種種不良習慣，是的兩個人的對接不太流暢，導緻後期接過隊友寫好json的部分，讀代碼時間就占用了好久，以及寫main（）函數的時候，錯誤百出，磕磕絆絆，全靠隊友帶飛。事實上，昨晚已經剛到了四五點。軟工實踐，這種有個任務在後面追着你跑的課，的确能夠學到好多東西，學到了json這個東西其實也沒有那麼神秘，隻是幾個reader.h,writer.h,value.h的幾個庫函數的使用。