天天看點

電梯排程算法

1 有關結對程式設計的思考

結對程式設計技術是指兩位程式員肩并肩地坐在同一台電腦前合作完成同一個設計、同一個算法、同一段代碼或同一組測試。通過這次的結對程式設計練習我結識了李承晗同學,體驗了結對程式設計這樣一種新的程式設計方式。

在結對程式設計的過程中,對結對程式設計的體驗總結如下:

結對程式設計的優點如下:

在獨立設計、實作代碼的過程中不免要犯這樣那樣的錯誤。在結對程式設計中,因為有随時的複審和交流,程式各方面的品質便取決于水準較高的那一位。這樣,程式中的錯誤就會少得多,程式的初始品質會高很多,同時也省下很多以後修改、測試的時間。這樣高品質的産出能夠給程式員,尤其是能力較低的(我)那一位帶來一些信心。而且,在結對程式設計的過程中兩位程式員互相交流,互相學習傳遞經驗,能夠在結對程式設計的過程中學習到更多的東西。

但是結對程式設計也存在着一定的缺點:

結對程式設計的過程中,代碼一直處于“複審”的過程,即不斷地稽核,提高設計和編碼品質的過程。這樣對于提高代碼品質有很大的幫助,但是在互審的過程中也存在着一些問題:例如,複審的程式員對代碼不及編寫代碼的程式員深入了解降低了複審的效果。而且,這次結對程式設計是随機分組的,以前并不熟悉,這次結對程式設計的過程也會因為互相并不熟悉而産生一些缺少交流的問題。

結對程式設計隊員的優缺點:

李承晗學習态度比較好,且基礎紮實,不懂就問,積極上進,就是有點内向,需要交流。

2 有關Information Hiding, interface design, loose coupling

Information Hiding:在面向對象方法中Information Hiding是通過對象的封裝實作的。隐藏對象的屬性和實作細節,僅對外公開接口,控制在程式中屬性的讀和修改的通路級别;将抽象得到的資料和行為(或功能)相結合,形成一個有機的整體。

在程式設計過程中可以通過控制通路權限來實作。例如用private,public,protected修飾屬性和方法。

interface design:interface design包括三個方面:

1 使用者接口

用來說明将向使用者提供的指令和它們的文法結構,以及軟體的回答資訊。

2 外部接口

用來說明本系統同外界的所有接口的安排包括軟體與硬體之間的接口、本系統與各支援軟體之間的接口關系。

3 内部接口

用來說明本系統之内的各個系統元素之間的接口的安排

loose coupling:類與類之間的互相調用,這兩個類之間就會有比較高的耦合程度,降低類與類之間的耦合程度,可以通過接口實作。

3 有關Design by Contract

契約式設計或者Design by Contract (DbC)是一種設計計算機軟體的方法。這種方法要求軟體設計者為軟體元件定義正式的,精确的并且可驗證的接口,這樣,為傳統的抽象資料類型又增加了先驗條件、後驗條件和不變式。這種方法和商業契約的情況有點類似。所謂契約,也就是合約,規定兩個互動物件上的權利和責任。雇傭合同規定你的工作時數和你必須遵守的行為規則,作為公司則付你薪水,雙雙履行義務,雙雙受益。DbC的核心思想是對軟體系統中的元素之間互相合作以及“責任”與“義務”的比喻。

在面向對象程式設計中一個類的函數提供了某種功能,那麼它要:

1.期望所有調用它的客戶子產品都保證一定的進入條件:這就是函數的先驗條件—客戶的義務和供應商的權利,這樣它就不用去處理不滿足先驗條件的情況。

2.保證退出時給出特定的屬性:這就是函數的後驗條件—供應商的義務,顯然也是客戶的權利。

3.在進入時假定,并在退出時保持一些特定的屬性:不變式。

是以在進行Dbc的時候我們通常要考慮三個問題:

1.它期望的是什麼?

2.它要保證的是什麼?

3.它要保持的是什麼?

DbC六大原則

原則1 區分指令和查詢。查詢傳回一個結果,但不改變對象的可見性質。指令改變對象的狀态,但不傳回結果。(應當是不一定傳回結果)

原則 2 将基本查詢同派生查詢分開。派生查詢可以用基本查詢來定義。

原則 3 針對每個派生查詢,設定一個後驗條件,使用一個或多個基本查詢的結果來定義它。這樣我們隻要知道基本查詢的值,也就能知道派生查詢的值。

原則 4 對于每個指令都撰寫一個後驗條件,規定每個基本查詢的值。結合“用基本查詢定義派生查詢”的原則,我們現在已經能夠知道每個指令的全部可視效果。

原則 5 對于每個查詢和指令,采用一個合适的先驗條件。先驗條件限定了客戶調用查詢和指令的時機。

原則 6 撰寫不變式來定義對象的恒定特性。類是某種抽象的展現,應當将注意力集中在最重要的屬性上,以幫助讀者建立關于類抽象的正确概念模型。

4 uml圖

5 UnitTest

6 算法概述:

對于每個電梯,建立一個List<dst>存放該電梯需要通路的樓層清單,dst類包含一個int和一個Direction參數,一個表示目标樓層,一個表示該請求的方向。該清單通過一個sortList()方法進行排序(根據電梯目前方向和樓層來确定List中元素的通路順序)。

每次調用run()方法時,首先周遊所有電梯,調用gotoFirst()方法通路它們通路清單的首項,如果沒有首項,根據目前客流情況(上下班之類的)添加一個目的地。

随後我們掃描目前請求清單中的請求,對于每個請求,我們掃描每個電梯,通過一個估價函數upValue()來确定目前請求插入後所産生的代價,然後選取代價最小的電梯,将該請求插入到通路清單中。然後調用sortList()方法進行排序。

算法關鍵:

排序算法sortList()的應該算是一個關鍵吧,排序要考慮目前方向和樓層,然後根據請求的方向和樓層來排通路清單,這裡情況很多,是以代碼量很大。另一個關鍵就是估價函數upvalue(),對于一個請求,掃描電梯的通路清單确定其所在位置,然後傳回一個代價,這裡找位置也不太容易實作,其實最後我也沒有精确的找到這個位置,隻是給出了一個大概的位置和估價。sortList()方法調試了我好久,重寫了大概3次吧,因為如果稍微順序錯了,就會導緻人上不了電梯,更詭異的還會直接把這個人給忽略掉。