第二次結對程式設計作業——畢設導師智能比對

031402337 胡心穎

031402341 王婷婷

作業概述

編碼實作一個畢設導師的智能比對的程式。

提供輸入包括：30個老師（包含帶學生數的要求的上限，單個數值，在[0,8]内），100個學生（包含績點資訊），每個學生有5個導師志願（志願的導師可以重複但不能空缺）。

實作一個智能自動配置設定算法，根據輸入資訊，輸出導師和學生間的比對資訊（一個學生隻能有一個确認導師，一個導師可以帶少于等于其要求的學生數的學生） 及 未被配置設定到學生的導師 和 未被導師選中的學生。

作業要求

• 輸入的資料，另外寫生成程式随機實作。
• 為輸入輸出設計标準化、通用化、可擴充的接口，為該智能比對程式子產品後期可能的整合入系統提供便利。
• 輸入輸出的格式，如采用文本檔案或資料庫的方式輸入，可自由讨論确定，但需要明确，為後期可能的整合入系統提供便利。
• 需要為智能比對算法确立幾條配置設定或排序原則，比如 績點優先、或其他、或其他等等，請你們結對讨論确定。
• 算法評價的目标是：對于同一組輸入，輸出的未被導師選中的學生數越少越好。
• 代碼具有規範性。
• 實作的程式語言不做限制性要求。
• 代碼送出在https://coding.net 上。
• 兩個人共同撰寫一個部落格，包含上述内容的描述，同時包含結對感受，以及兩個人對彼此結對中的閃光點或建議的分享。

作業分析

算法思想為采用 貪心思想 ;

簡單來說，首先将學生按照績點從高到低排序，優先配置設定績點高的學生；

然後針對每個學生，首先過濾掉其重複選擇的導師，然後按照權重值 teacher[i].qz （後面介紹）高低來配置設定導師，權重值相同的情況下按照學生志願排序；

teacher[i]表編号為i的導師,teacher[i].left表示該導師剩餘學生數，teacher[i].want表示選擇了該導師的學生總數，teacher[i].qz表示teacher[i]導師對于該學生的權重值（在本算法中可認為是比對程度，越大越比對）

teacher[i].qz =teacher[i].left/teacher[i].want

對于每個學生的五個志願導師，都計算出其對應的權重值，按照權重值高的配置設定，如果有多個權重值相同，那麼則按照志願順序配置設定；

從權重值計算公式可以看出，teacher[i].left越大,teacher[i].want越少，代表導師剩餘數越多和導師越冷門來配置設定，在符合學生志願的情況下，使得大多數學生都能配置設定到導師；

權重值相同時按照志願順序來配置設定，使得學生都能選擇到自己較喜愛的導師

流程圖

代碼分析

基本資料結構

struct Student // 學生結構體
{
	int num;//學生編号
	double grade;//學生績點
	bool flag;//是否配置設定了導師
	int tea[10];//志願
}stu[110];
struct Teacher //老師結構體
{
	int num;//導師編号
	double need;//可以接受的學生數
	double left;//還剩下的名額
	double want;//被幾個學生選擇
	double qz;//權重，qz=left/need
	bool flag;//是否有學生
	vector<int> stu;//接受的學生
}teacher[50];···
           

産生随機資料

srand(time(0));
	for(int i=0;i<30;i++)//導師随機資料
	{
		int want;
		want=rand()%9;
		fprintf(f,"%d %d\n",i,want);
	}
	for(int i=0;i<100;i++)//學生随機資料
	{
		int g=rand()%500;
		if(g<=100)g+=100;
		double grade=(double)g/100.0;
		fprintf(f,"%d %lf %d %d %d %d %d\n",i,grade,rand()%30,rand()%30,rand()%30,rand()%30,rand()%30);
	}
           

使用srand()函數創造随機數；

導師随機生成想要的學生個數，将随機數模9，使得資料範圍在 0-8 之間；

學生随機生成績點以及想要的導師編号，績點控制在1-5之間，導師編号在0-29之間

權重值teacher[i].qz

for(int i=0;i<30;i++)//計算導師權重
	{
		teacher[i].left=teacher[i].need;
		if(teacher[i].want==0)teacher[i].qz=-1;
		else teacher[i].qz=teacher[i].left/teacher[i].want;
	}
           

teacher[i]表編号為i的導師,teacher[i].left表示該導師剩餘學生數，teacher[i].want表示選擇了該導師的學生總數；

如果導師想要的學生數為0 ，則直接将teacher[i].qz（權重值）設為-1，

否則權重值teacher[i].qz=teacher[i].left/teacher[i].want

績點排序函數

bool cmp(Student a,Student b)//學生按照績點的高到低排序
{
	return a.grade>b.grade;
}
           

将學生按照績點的高到低排序

導師配置設定函數

sort(stu,stu+100,cmp);//學生排序
	for(int i=0;i<100;i++)
	{
		double now;
		int ans;
		now=0;
		ans=-1;
		for(int j=0;j<5;j++)
		{
			if(now<teacher[stu[i].tea[j]].qz)/到志願導師中權重最高的導師
			{
				now=teacher[stu[i].tea[j]].qz;
				ans=stu[i].tea[j];
			}
		}
		if(ans==-1)continue;//如果找不到符合要求的導師就下一個
		teacher[ans].stu.push_back(i);//修改導師的剩餘名額以及其他資訊
		teacher[ans].left--;
		teacher[ans].want--;
		teacher[ans].qz=teacher[ans].left/teacher[ans].want;
		if(teacher[ans].flag==0)
		{
			countt--;
			teacher[ans].flag=1;
		}
		stu[i].flag=1;//修改學生的資訊
		counts--;
	}
           

先将學生按照績點初步排序，在通過權重值和志願順序來配置設定

程式運作結果

生成随機資料樣例

導師編号從0至29，後面緊跟導師想要的學生數從0到8

學生編号從0至99，後面緊跟其績點 從1.00到5.00，再接着就是五個志願導師

https://coding.net/u/songyufeng/p/DSFPXT/git/blob/master/data.txt

比對結果樣例

經過比對之後的結果：

首先輸出沒有比對的導師以及沒有比對的學生，

緊接着按照導師序号來輸出每個導師的比對學生情況

https://coding.net/u/songyufeng/p/DSFPXT/git/blob/master/ans.txt

算法效率評估、閃光點、改進方向

效率評估

• 以下是10次随機試驗的學生配置設定情況結果

  

• 從圖表中資料來看幾乎所有學生都能夠配置設定到導師，近乎完美，不得不感歎過貪心算法真的超級棒啊！
• 那麼學生的志願情況呢，是每個學生都能配置設定到其志願靠前的導師？

• 以下是10次随機試驗的學生志願平均情況（隻計算了有被配置設定到的學生）

  

• 從圖表中可以看出 第一志願人數>第二志願>第四志願>第三志願>第五志願
• 根據我們先前的優先配置設定績點高的同學的思想，想必績點高的同學所配置設定的志願自然是比較靠前的，下面我們也驗證一下這一點

• 按照績點段來檢視志願情況
• 由于績點是随機生成的，是以各個績點段的人數相同（這也是我們考慮不周到、比較不科學的地方，因為現實生活中績點不可能平均配置設定）
• 績點為 [4.00 - 5.00 )的績點大神

  

• 績點為 [3.00 - 4.00 )的學霸

  

• 績點為 [2.00 - 3.00 )的僞學霸

  

• 績點為 [1.00 - 2.00 )的學渣吧

  

• 圖示完美驗證了按照績點優先配置設定的情況

閃光點

• 算法的思想 - 貪心思想
• 對于某個學生重複選擇某位導師的情況，系統能夠過濾掉
• 能夠保證 最廣大學生 配置設定到自己志願的導師的情況，又可滿足 績點高者優先配置設定 以及盡可能 配置設定志願靠前的導師 ！

改進方向

• 學生績點生成得不夠合理，不夠滿足現實情況，影響了後面的志願情況分析

作業感想

• 宋禦風：結對程式設計比一個人程式設計感覺更加集中，在第二次結對程式設計作業，構思配置設定算法的時候，一個人很容易導緻思維僵化，兩個人探讨，聽取對方的意見，效率會快很多。一個人程式設計經常完成一個子產品的内容就想休息，兩個人在一起會強迫自己做下去。而且如果兩個人的思維和知識面互補的話，對項目各方面的完善都很有助益。
• wangtingting007:結對程式設計有助于克服拖延症，擺脫懶癌患者的毛病，同時結對過程能夠與隊友好好溝通、交流想法等，真的是一件很棒的事！然後結對過程能夠結合兩個人的特長和不足合理分工、提高作業效率和品質！隊友代碼能力好強！！！！

作業連結：https://coding.net/u/songyufeng/p/DSFPXT/git

項目說明：README.md

配置設定導師：a.cpp