NCHU OOP BLOG1--電梯調度程序

正文

1.前言

這三次大作業主要圍繞的對電梯的調度來展開，調度算法為LOOK算法，實際上，比現實中的一些電梯所用算法更簡單。
其中，第一次作業難度最大，後面兩次作業進行迭代並不難；
考點主要是類和對象，以及類與類之間的關係，還包括java中List容器的使用，和正則表達式的使用。
題量其實並不大，並且給了類圖做參考，提供了很大的幫助。但是，如果看輕了這幾次作業，沒有花費足夠的時間去分析題目，做設計等，就很難在DeadLine之前完成，然後就Die了，後面進行迭代的時候就更跟不上進度了，因此還是要重視每一次的大作業啊。

2.設計與分析

第一次大作業（共5道題）：

重點在最後一道：電梯調度問題，因而前面幾道便簡單分析一下

1.前面兩題：

7-1 NCHU_求身份證號校驗位、7-2 NCHU_求解一元二次方程

7-1
分析：
對輸入的數字字符串進行操作，根據公式，計算出最後一位的數字
這道題的難點是在如何對字符串的每位上的數字進行處理，我採用將字符串轉化為字符數組的方法，從而對數組的每個元素進行處理，用java中字符串自帶的toCharArray()函數；

7-2
分析：
求二元方程的解，包括一個解，兩個解，無解等多種情況，主要對二次方程a b c三個係數進行計算，因此創建了一個代表二次方程的類QuadraticEquation，a b c為該類的三個私有屬性

該類除了基本的構造方法，get、set方法，還包括得到Discriminant方法，得到兩個root的方法，用於得到兩個根

小結：其實這兩道題主要是讓我們熟悉java的語言風格，幫助我們掌握基本的類和對象的知識，能夠用類創建對象，並對對象進行操作（都只有一個類，就不做類圖了）

2.第三四題：

7-3 NCHU_正則表達式訓練-驗證碼校驗 7-4 NCHU_正則表達式訓練-QQ號校驗

7-3
分析：
實際上就是判斷一個字符串是否符合相應的格式（四位數字或字母），很標準的用正則表達式求解的題目
這道題的難點在於：正則表達式部分該如何寫，其實就是"\w{4}"，\w可以匹配大小寫字母和數字

7-4
分析：
判斷輸入的數字字符串是否符合條件（5-15位、每位數字：0-9、首位不為0），基本於7-3相同，就是正則表達式更復雜了些（不重複了）

3.第五題：

7-5 NCHU_單部電梯調度程序

7-5

題面：

設計一個電梯類，具體包含電梯的最大樓層數、最小樓層數（默認為1層）當前樓層、運行方向、運行狀態，以及電梯內部乘客的請求隊列和電梯外部樓層乘客的請求隊列，其中，電梯外部請求隊列需要區分上行和下行。
電梯運行規則如下：電梯默認停留在1層，狀態為靜止，當有乘客對電梯發起請求時（各樓層電梯外部乘客按下上行或者下行按鈕或者電梯內部乘客按下想要到達的樓層數字按鈕），電梯開始移動，當電梯向某個方向移動時，優先處理同方向的請求，當同方向的請求均被處理完畢然後再處理相反方向的請求。電梯運行過程中的狀態包括停止、移動中、開門、關門等狀態。當電梯停止時，如果有新的請求，就根據請求的方向或位置決定移動方向。電梯在運行到某一樓層時，檢查當前是否有請求（訪問電梯內請求隊列和電梯外請求隊列），然後據此決定移動方向。每次移動一個樓層，檢查是否有需要停靠的請求，如果有，則開門，處理該樓層的請求，然後關門繼續移動。
使用鍵盤模擬輸入乘客的請求，此時要注意處理無效請求情況，例如無效樓層請求，比如超過大樓的最高或最低樓層。還需要考慮電梯的空閒狀態，當沒有請求時，電梯停留在當前樓層。
請編寫一個Java程序，設計一個電梯類，包含狀態管理、請求隊列管理以及調度算法，並使用一些測試用例，模擬不同的請求順序，觀察電梯的行為是否符合預期，比如是否優先處理同方向的請求，是否在移動過程中處理順路的請求等。為了降低編程難度，不考慮同時有多個乘客請求同時發生的情況，即採用串行處理乘客的請求方式（電梯只按照規則響應請求隊列中當前的乘客請求，響應結束後再響應下一個請求），具體運行規則詳見輸入輸出樣例。

輸入輸出格式：

輸入格式:
第一行輸入最小電梯樓層數。
第二行輸入最大電梯樓層數。
從第三行開始每行輸入代表一個乘客請求。

電梯內乘客請求格式：<樓層數>
電梯外乘客請求格式：<乘客所在樓層數,乘梯方向>，其中，乘梯方向用UP代表上行，用DOWN代表下行（UP、DOWN必須大寫）。
當輸入“end”時代表輸入結束（end不區分大小寫）。
輸出格式:
模擬電梯的運行過程，輸出方式如下：

運行到某一樓層（不需要停留開門），輸出一行文本：
Current Floor: 樓層數 Direction: 方向
運行到某一樓層（需要停留開門）輸出兩行文本：
Open Door # Floor 樓層數
Close Door

題目及代碼分析
依據題目而言(其中標粗部分為我認為比較重要的點)：
只需要設計一個電梯類，屬性為最大樓層，最小樓層，當前樓層，狀態，方向；

下面寫該類的函數：
首先，基本的構造方法，get、set方法；

其次，依據標粗部分至少包括：
1.“有乘客對電梯發起請求”，判斷狀態是否改變的ifchangestatue，如果請求隊列中還有請求，返回true，沒有返回false；
2.“根據請求的方向或位置決定移動方向”，判斷電梯運行方向的pan_direction，返回String類型（方向）；
3.“優先處理同方向的請求”，得到要去的樓層的getgofloor
4.“檢查是否有需要停靠的請求”，判斷該樓層是否停止的ifstop
5.“處理該樓層的請求”，處理樓層的removeout和removein
6. 改變樓層是電梯樓層變化的函數的changecurrentfllor，依據是否達到目的樓層和運行方向，來確定是增加還有減少樓層；
7. 輸出的函數的print_nostop print_isstop，停靠與不停靠分開輸出；

最後，在主函數中：
我採用正則表達式來提取關鍵信息（END），數據存儲在外（內）請求數組中，再作為參數傳入，對請求進行操作

PS：依據題目要求，只設計了一個類（同樣不做類圖），後面的大作業對該類拆分，因而不會再分析算法，只對迭代的地方進行分析。

下面，讓我們來看看該類的圈複雜度：最大為23，平均為5.14，比良好的代碼2.0~4.0的範圍超了不少，主要是在得到請求樓層的函數中（在其他函數中也有這種情況），為了防止正則表達式訪問越界的情況，寫了多次的分支，使複雜度增加，以後我會盡量避免這種情況，可以用更好的方法來代替，一勞永逸。分支更多，邏輯也會更復雜，這應該是我之後的訓練方向。

第二次大作業（共3道題）：

1.前面兩題：

7-1 點與線（類設計）、7-2 NCHU_汽車風擋玻璃雨刷問題（類設計）
這兩道題主要是根據題意進行類設計，包括類的屬性，方法，以及類與類之間的關係，熟悉設計流程，幫助我們完成7-3電梯類的設計。

7-1
分析
這道題讓我們設計兩個類，包括點類和線類，其中點與線是聚合關係，線是整體，點是局部，除基本的構造方法和get、set方法外，線類中還有得到線長（兩點間距離）的方法。
這題的難點在於，類與類之間的關係（聚合），如何在語義上理解聚集關係，同時語法上實現生命週期的不同。

7-2
分析
這道題讓我們設計一個簡單的雨刷系統，實現雨刷速度的控制,每一個擋位下只能進行一次加或減；
為了符合單一職責原則和迪米特法則，設計了：雨刷類、控制桿類、刻度盤類、以及最重要的控制類，通過控制類來對其他三個類進行操作，因而控制類與其他類之間的關係為關聯。

2.第三題：

7-3 NCHU_單部電梯調度程序（類設計）：迭代練習

7-3
題面：

對之前電梯調度程序進行迭代性設計，目的為解決電梯類職責過多的問題，類設計要求遵循單一職責原則（SRP），要求必須包含但不限於設計電梯類、乘客請求類、隊列類以及控制類；
電梯運行規則與前階段單類設計相同，但要處理如下情況：

乘客請求樓層數有誤，具體為高於最高樓層數或低於最低樓層數，處理方法：程序自動忽略此類輸入，繼續執行
乘客請求不合理，具體為輸入時出現連續的相同請求，例如<3><3><3>或者<5,DOWN><5,DOWN>，處理方法：程序自動忽略相同的多餘輸入，繼續執行，例如<3><3><3>過濾為<3>

注意：本次作業類設計必須符合如上要求（包含但不限於乘客請求類、電梯類、請求隊列類及控制類，其中控制類專門負責電梯調度過程），凡是不符合類設計要求此題不得分，另外，PTA得分代碼界定為第一次提交的最高分代碼（因此千萬不要把第一次電梯程序提交到本次題目中測試）。

輸入輸出格式：

輸入格式:
第一行輸入最小電梯樓層數。
第二行輸入最大電梯樓層數。
從第三行開始每行輸入代表一個乘客請求。

電梯內乘客請求格式：<樓層數>
電梯外乘客請求格式：<乘客所在樓層數,乘梯方向>，其中，乘梯方向用UP代表上行，用DOWN代表下行（UP、DOWN必須大寫）。
當輸入“end”時代表輸入結束（end不區分大小寫）。
輸出格式:
模擬電梯的運行過程，輸出方式如下：

題目及代碼分析
與上一次的電梯相比，這一次的電梯調度的算法沒變，還是LOOK算法，但是對電梯類進行了拆分，為實現單一職責原則這次我添加了：外部請求類、請求隊列類、控制類、枚舉類狀態、枚舉類方向；

在控制類中實現第一次作業中的對電梯的各種操作，將電梯與外部請求的隊列解耦，電梯與隊列沒有直接關係，“不要和陌生人講話”，符合迪米特法則（LOD）；

而外部請求類則是為了方便將請求類中的外部請求進行操作，兩個枚舉類型則方便對電梯中的屬性進行表示和改變值；

因為要對請求隊列中的元素進行刪除，可能還需要擴大，所以用鏈表數組LinkList，方便操作，便將字符串數組轉換為了鏈表數組；

這就是這次電梯程序的全部思路，下面來對代碼進行分析：

從類圖可以看出，就和我上方分析的一樣，控制類與電梯、隊列類為關聯關係，外部隊列類與枚舉類方向為關聯關係，電梯類與兩個枚舉類型為關聯關係；
這次的代碼整體上方法改動不大（只是改變了方法所在的類），改動最大的是主函數：
1.改變了判斷輸入是否符合規範的方法，從第一次判斷字符的個數改成了用正則表達式判斷是否滿足輸入的要求；

2.新增了判斷輸入是否正確的方法，去除請求樓層超過範圍的請求，以及連續多次輸入相同的請求；

3.最後將電梯類中的，改變樓層的函數寫入主函數中，在主函數中實現電梯的調度。

			while(controller.moving())
			{
				int gofloor=controller.getnextfloor();
				if(controller.shouldstop(gofloor))
				{
					if(controller.elevator.getDirection()!=Direction.IDLE)
						controller.showState();
					controller.openDoors();
					int currentfloor=controller.elevator.getCurrentfloor();if(controller.queue.externalQuests.size()>0&&controller.queue.externalQuests.get(0).getFloor()==currentfloor)
					{
						Direction direct=controller.queue.externalQuests.get(0).getDirection();
						if(direct!=controller.elevator.getDirection())
						{
							controller.elevator.setDirection(direct);
							controller.removeRequest(currentfloor);
						}
						else {
							controller.removeRequest(currentfloor);
							controller.determineDirection();
						}
					}
					else 
					{
						controller.removeRequest(currentfloor);
						controller.determineDirection();
					}
					
					controller.removeRequest(currentfloor);
					controller.determineDirection();
					if(controller.elevator.getDirection()==Direction.UP)
					{
						currentfloor++;
						controller.elevator.setCurrentfloor(currentfloor);
					}
					else if(controller.elevator.getDirection()==Direction.DOWN)
					{
						currentfloor--;
						controller.elevator.setCurrentfloor(currentfloor);
					}
					//System.out.println(controller.queue.externalQuests.size());
					//System.out.println(controller.queue.internalQuests.size());
				}
				else
				{	
					controller.showState();
					int currentfloor=controller.elevator.getCurrentfloor();
					if(controller.elevator.getDirection()==Direction.UP)
						controller.elevator.setCurrentfloor(++currentfloor);
					if(controller.elevator.getDirection()==Direction.DOWN)
						controller.elevator.setCurrentfloor(--currentfloor);
				}
			}

最後，我們來分析一下代碼的圈複雜度，看看與上次相比有沒有什麼變化，有什麼可以改進的地方

從上圖可以看出，這次的圈複雜度還是有很大改變的；
其中，變化最大就是最大複雜度，由原來的23增大到了36，增大了不少，主函數在判斷輸入是否正確時使用了太多if_else語句，使分支數量增加；
平均複雜度處在了正常範圍，再將函數再細化，可以使複雜度再降低一些；
最後，就是註釋語句太少了，遠遠低於正常範圍，代碼的規範做的還是不到位，還需要繼續改進，需要在日常的練習中培養寫註釋的習慣，也可以看看一些大廠的代碼規範，用這些來約束自己；
那麼，以上就是大作業二的全部分析，作業三敬請期待！

第三次大作業（共3道題）：

1.前面兩題：

7-1 NCHU_銷售步槍問題 7-2 蒙特卡羅方法求圓周率
這兩道題的目的與第二次類似，為了進一步鍛鍊我們對類與對象，和麪向對象的相關知識的掌握，這兩道也不是很難，簡單分析一下。

7-1
分析
槍械銷售的題目，其實在c語言時已經寫過了，只是讓你用面向對象的編程語言翻譯一遍，設計四個類，三個具體類，一個控制類，也是為了滿足單一職責原則和迪米特法則，降低類與類之間的耦合。由題目所給的類圖，可以明確的知道要怎麼設計類，大大降低了難度。

7-2
分析
這道題涉及一個新的算法，用蒙特卡羅方法求圓周率，但是降低了難度，算法和類圖已經給出，只要看懂題目意思，基本上能解決。雖然題目本身不難，但是題目背後涉及了：統計模擬，近似求解的過程，這是一個很重要的思想，可以運用到多種問題的求解上。

2.第三題：

7-3 NCHU_單部電梯調度程序（類設計-迭代）：迭代練習

7-3
題面：

對之前電梯調度程序再次進行迭代性設計，加入乘客類（Passenger），取消乘客請求類，類設計要求遵循單一職責原則（SRP），要求必須包含但不限於設計電梯類、乘客類、隊列類以及控制類;

電梯運行規則與前階段相同，但有如下變動情況：

乘客請求輸入變動情況：外部請求由之前的<請求樓層數,請求方向>修改為<請求源樓層，請求目的樓層>
對於外部請求，當電梯處理該請求之後（該請求出隊），要將<請求源樓層，請求目的樓層>中的請求目的樓層加入到請求內部隊列(加到隊尾）
注意：本次作業類設計必須符合如上要求（包含但不限於設計電梯類、乘客類、隊列類以及控制類），凡是不符合類設計要求此題不得分，另外，PTA得分代碼界定為第一次提交的最高分代碼（因此千萬不要把第一次及第二次電梯程序提交到本次題目中測試）。

輸入輸出格式：

輸入格式:
第一行輸入最小電梯樓層數。
第二行輸入最大電梯樓層數。
從第三行開始每行輸入代表一個乘客請求。

電梯內乘客請求格式：<樓層數>
電梯外乘客請求格式：<請求源樓層，請求目的樓層>，其中，請求源樓層表示乘客發起請求所在的樓層，請求目的樓層表示乘客想要到達的樓層。
當輸入“end”時代表輸入結束（end不區分大小寫）。
輸出格式:
模擬電梯的運行過程，輸出方式如下：

題目及代碼分析
與上次的電梯相比，這一次電梯的算法並未改變，但是修改了輸入的方式，從而導致要刪去外部請求類，改為乘客類，然後內部與外部請求都可以用乘客類更方便表示，可以用一種泛型表示兩種數組；
“請求目的樓層加入到請求內部隊列(加到隊尾）”，因而在請求類中，內部請求添加一個add函數，用於接收外部請求的目的樓層；

因此這次的代碼，我增加了乘客類：包含基本的構造方法、get、set方法，以及獲取外部請求方向的getdirection方法（在內部請求時，默認sourceFloor屬性為0）；

public class Passenger {
Integer sourceFloor;
Integer destinationFloor;
public Passenger() {
	// TODO Auto-generated constructor stub
}
public Passenger(Integer sourceFloor,Integer destinationFloor ) {
	this.sourceFloor=sourceFloor;
	this.destinationFloor=destinationFloor;
}
public Passenger(Integer destinationFloor ) {
	this.destinationFloor=destinationFloor;
}
public Integer getSourceFloor() {
	return sourceFloor;
}
public void setSourceFloor(Integer sourceFloor) {
	this.sourceFloor = sourceFloor;
}
public Integer getDestinationFloor() {
	return destinationFloor;
}
public void setDestinationFloor(Integer destinationFloor) {
	this.destinationFloor = destinationFloor;
}
public Direction getdirection() {
	if(this.sourceFloor>this.destinationFloor)
		return Direction.DOWN;
	else if(this.sourceFloor<this.destinationFloor)
		return Direction.UP;
	else return Direction.IDLE;
}
}

最後，在主函數中，需要簡單修改一下檢測輸入的幾個步驟，問題不大。

題目分析就到這了，下面來看下類圖：

從上面的類圖可以看出，類之間的關係並不複雜，一樣，通過控制類將請求類和電梯類聯繫起來，避免了電梯與請求類的直接聯繫；
這次的題目其實改動並不大，主要是圍繞外部請求輸入改變做的調整，如果前面的兩次的電梯認真完成了，這題基本上沒問題。
最後，來看下這個電梯的圈複雜度:

與上一次的電梯相比，這一次有了點進步，最大複雜度減小6，減少了一些分支，平均複雜度也在正常的範圍內，註釋的比例也在增大，但是問題依舊存在，最大複雜度仍然遠遠高於正常值，還有需要改進的地方。
以上，就是第三次大作業的全部分析。

讓我們恭喜這一Part圓滿完成！！！

3.踩坑心得

回顧這三週的練習，想想就很不容易，踩了不少坑，每次踩進去都要花不少功夫才能出來，真是心酸史了。（分析三次電梯調度程序）

習題五——7-5

（1）首先，最大的坑就是，“我以為是這樣的”，掉坑裏幾天後，還是段老師點醒我們，永遠不要讓“你以為”佔據上風，因為“你以為的都是錯的”，一切都要根據需求來設計。
剛開始，沒有理解算法，“以為”是將所有請求都考慮進去，尋找當前樓層下，最優的請求，然後就寫了三天，後面才知道只需要考慮每個隊列的第一個請求，這是代碼改的第一遍；
然後，理解了算法後，又沒有好好做設計，導致代碼邏輯很複雜，又大部分推翻重新來過，第三遍才有了雛形；

（2）其次，有一個經常踩的坑就是，沒有搞清楚需求，導致總是得不出正確的結果；

從圖上可以很明顯的看到，一連串的非零返回，就是在需求分析時，沒有注意到，“end不區分大小寫”，導致從輸入就有了錯誤；

（3）最後，也是需求的坑，格式錯誤，導致答案錯誤，就算邏輯都對了，但是輸出出了問題，一切都沒用，輸出格式也是需求的一種，要重視需求分析，這對任何一個項目而言都非常重要，需要我們花費更多的功夫，而不是一拿到題目，就直接上手敲代碼。

習題六——7-3

這道題目有一個測試點沒過，這一路上非常的心酸，問題應該是出在有一些情況沒有考慮到，導致測試點沒過；
（1）在修改完第一次作業的代碼後，剛開始的提交是答案錯誤，先比較了兩個測試用例是一樣的，還以為是哪裏的邏輯問題沒發現，用Eclipse調試了幾遍，沒有問題，當時是有點崩潰的；

（2）第二天，從主函數出發，發現需求中，要求我們“去除連續的相同請求”，但是我的去除了所有相同的請求，所以進行了修改，結果部分正確，當時確實很心累；

（3）最後，還是回到了邏輯問題，比較幾個補充測試用例，發現不同，重新修改，反覆了三四遍，直至所有已知的測試用例都相同；但提交後，還是部分正確，當時整個人都麻了；

（4）説實話，現在還是有點懵，不知道問題在哪，但是整個過程下來，收穫還是很多的:
首先，在排除簡單錯誤的情況下，第一要考慮需求分析有沒有出現錯誤，有沒有忽略的地方；
其次，就是很好的鍛鍊了我對Eclipse的調試功能的使用，能夠合理的設置斷點；
最後，也很好的磨練了我的心態，保持平常心，不過分追求分數,也不輕易放棄；

習題七——7-3

這次習題沒有前兩次踩的坑多，完成的也很快。簡單談一下，我的心得：
首先，一定要快刀斬亂麻，有一些函數自己都理不清思路，改不明白，乾脆直接刪掉重寫，沒必要死磕在上面，有時候換個思路，能更快的解決問題；
其次，就是可以適當的找別人的幫助，因為你踩的坑，可能是別人踩過的，這樣才能更快的解決問題。大家一起討論，反而效率更高；
最後，就是一定要堅持，當時感覺人生無望，可真正走過了這個坎，會覺得一切不過如此，人生是一個階段一個階段闖過去的。

！！！下一Part——讓我們來到改進階段！！！

4.改進建議

對於代碼的改進，前面已經談論了一些，主要是：
（1）增加更多的註釋，幾次的註釋率都很低，提高代碼的可讀性；
（2）增加請求不符合格式，以及其他特殊情況的處理，邊界的處理等等，使代碼可以應對更極端和複雜的情況；
（3）修改一些函數，處理一下if——else的情況，可以做特殊處理，比如面對外部請求隊列為空的情況，不再重複判斷是否size>0，而是在一開始確定為空時，直接返回或做特殊處理，減少代碼的分枝數，從而減少圈複雜度；

最後一部分——恭喜！！！

5.總結

第一階段的練習結束了，但是我們的學習旅程還沒有結束，現在來總結一下，這段時間收穫了什麼，簡述下一階段的安排；
（1）這一階段，充分訓練了我對正則表達式的使用、List容器的使用（實現了從無到有的進程），熟悉了這門面向對象的語言的語法，以及java語言的一些原則，拉近了我與java這門兩月前還陌生的語言的距離；
（2）必不能少説的就是，對心性的磨練，不斷地打擊你，又拉起你，反反覆覆，內心都更強大了（方便接受下一階段的打擊）；
（3）也有一些需要改進和深入學習的地方：類與類之間的關係。組合、聚合、關聯三者還是不能很好的區分，同時在語法上，對組合、聚合關係的區分也掌握的不是很好；
（4）下一階段，在鞏固這一階段學習的基礎上，將側重學習java繼承與多態的知識，更深入的瞭解java的設計原則，不斷的運用在實踐中；

結束！！！
我們下次再見！！！

等時圓~ 日志

@Dengsiyan

标签

面向對象 (24)

动态