031402313 黃志明 031402431 章鼎
github連結:https://github.com/cafe3165/Software_Work
問題重述
>編碼實作一個畢設導師的智能比對的程式。提供輸入包括：30個老師（包含帶學生數的要求的上限，單個數值，在[0,8]内），100個學生（包含績點資訊），每個學生有5個導師志願（志願的導師可以重複但不能空缺）。實作一個智能自動配置設定算法，根據輸入資訊，輸出導師和學生間的比對資訊（一個學生隻能有一個确認導師，一個導師可以帶少于等于其要求的學生數的學生）及 未被配置設定到學生的導師 和 未被導師選中的學生。
問題分析
共有一百名學生需要選擇三十名導師中五位作為自己的志願，學生中比較有說服力的一項名額是績點，是以我們先用績點高低
來排名100位學生。
一開始的想法是按績點排名來決定配置設定導師次序，即績點
的學生先配置設定導師，績點排名靠前
的同學越後配置設定導師，但是這樣一來就會出現一個問題——大部分成績靠後的同學很難選到自己想要的導師，這對他們存在着一些不公平，誰說成績不好的同學中沒有某方面的強項呢？經過與隊友讨論，我們決定将績點排名的越靠後
以及前20%
單獨劃分出來進行導師配置設定，方法是先按績點後20%
來配置設定排名相反次序先後
的學生，再用後20%
績點排名次序先後
的學生。配置設定完成後，餘下的後20%
60%
的學生，也就是績點排名在中間的學生，我們采用由兩端向中心夾逼的配置設定方法，即排名第21的同學最先配置設定，然後是排名第80的同學，再然後是排名第22的同學······直到第50、51名同學完成配置設定。
這樣的配置設定方法既能保證成績優異同學選到自己想要的導師，又能兼顧成績較差的同學不會一大片的落選。
第二次結對程式設計作業——畢設導師智能比對
代碼分析
基本資料結構
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
//學生結構體
struct stu {
int num; //學号
double c; //績點
bool chose; //是否被選擇
int teacher[6]; //所選擇的導師數組
};
//導師所擁有學生的結構體
struct stu2 {
int num;
double c;
};
//導師結構體
struct tea {
vector<stu2> 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++，一點一點地寫。寫完測試以後，感覺挺有成就感的，測試結果還不錯，配對成功率很高！