前言

對于三次題目集而言：總體難度適中，除了三次電梯調度程序以外，其他大部分題目都比較簡單，大部分都是以往已經涉及過的題目。而這三次電梯程序設計，總的來說就是：

1. 電梯運行的算法
2. 符合SRP的類設計
3. 應對需求改變的迭代升級

本篇blog將集中于我的三次電梯調度程序的分析與總結以及完成這次階段性作業后的心得體會。

設計與分析

第一次電梯調度程序

題目：

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

輸入格式:

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

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

輸出格式:

模擬電梯的運行過程，輸出方式如下：

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

輸入樣例:

1
20
<3,UP>
<5>
<6,DOWN>
<7>
<3>
end

輸出樣例:

Current Floor: 1 Direction: UP
Current Floor: 2 Direction: UP
Current Floor: 3 Direction: UP
Open Door # Floor 3
Close Door
Current Floor: 4 Direction: UP
Current Floor: 5 Direction: UP

Open Door # Floor 5
Close Door
Current Floor: 6 Direction: UP
Current Floor: 7 Direction: UP
Open Door # Floor 7
Close Door
Current Floor: 6 Direction: DOWN
Open Door # Floor 6
Close Door
Current Floor: 5 Direction: DOWN
Current Floor: 4 Direction: DOWN
Current Floor: 3 Direction: DOWN
Open Door # Floor 3
Close Door

類圖設計

無設計，代碼所有功能均由Lift類實現。

代碼分析

• 代碼共 303 行，含 2 個類，平均每個類有 4.5 個方法，方法平均語句數為 17.11 ，分支語句占比 29.5% 。
• 平均復雜度 7.44* ，最復雜方法是Lift.getTarget()，位于 111 行，包含 85 條語句，復雜度以及達到了 40* 。
• 最大塊深度為 8 ，平均塊深度 4.09 ，依然是Lift.getTarget()，非常復雜。
• 不同塊深度對應語句數有差異，深度為 2 時語句數較多有 36 條，深度 8 時有 32 條語句 ，可以看出代碼結構復雜程度。
• 總之，代碼的平均復雜度、最大復雜度以及最大深度指標表現欠佳，說明代碼中部分方法或結構存在較高的邏輯復雜性，理解和維護難度較大。并且，在一些地方上語句數量明顯較多，代碼中存在較深嵌套和較大規模的代碼塊，結構不夠簡潔。這是由于代碼邏輯設計較差，方法內部嵌套過多控制結構等原因導致。后續可通過重構代碼，減少不必要的嵌套，優化算法邏輯，增加注釋等方式，降低代碼復雜度，提升代碼可讀性與可維護性。

總結與心得

第1次代碼實現的過程很艱難。因為只有一個測試用例，剛上手的時候完全沒搞清楚邏輯是什么。所以前前后后改了很多次，最后再仔細研究了老師給的電梯運行過程詳解，聽了老師的講解之后，終于搞明白了題目是什么意思?；撕芏鄷r間后，最后還是做出來了?？偟膩碚f，這次代碼是比較糟糕的。不過在完成這次題目集的過程中，我對電梯運行模擬有自己的理解：

1. 根據電梯的運行方向，位置，和隊列請求信息得到電梯與請求的相對位置，相對方向，和電梯的預期方向。
2. 根據上述信息，基于方向優先原則，在內外請求中做出選擇，得到電梯前往的目標位置。
3. 前往目標位置，并刪除隊列頭元素。
4. 重復述過程直到完成所有請求。
   這為后面兩次題目的完成打下了良好的基礎。

第二次電梯調度程序

題目：

對之前電梯調度程序進行迭代性設計，目的為解決電梯類職責過多的問題，類設計要求遵循單一職責原則（SRP），要求必須包含但不限于設計電梯類、乘客請求類、隊列類以及控制類，具體設計可參考如下類圖。

電梯運行規則與前階段單類設計相同，但要處理如下情況：

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

輸入格式:

同一

輸出格式:

同一

輸入樣例1:

1
20
<3,UP>
<5>
<6,DOWN>
<7>
<3>
end

輸出樣例1:

Current Floor: 1 Direction: UP
Current Floor: 2 Direction: UP
Current Floor: 3 Direction: UP
Open Door # Floor 3
Close Door
Current Floor: 4 Direction: UP
Current Floor: 5 Direction: UP
Open Door # Floor 5
Close Door
Current Floor: 6 Direction: UP
Current Floor: 7 Direction: UP
Open Door # Floor 7
Close Door
Current Floor: 6 Direction: DOWN
Open Door # Floor 6
Close Door
Current Floor: 5 Direction: DOWN
Current Floor: 4 Direction: DOWN
Current Floor: 3 Direction: DOWN
Open Door # Floor 3
Close Door

輸入樣例2:

1
20
<3,UP>
<3,UP>
<5>
<5>
<5>
<6,DOWN>
<7>
<7>
<3>
<22,DOWN>
<5,DOWN>
<30>
END

輸出樣例2:

Current Floor: 1 Direction: UP
Current Floor: 2 Direction: UP
Current Floor: 3 Direction: UP
Open Door # Floor 3
Close Door
Current Floor: 4 Direction: UP
Current Floor: 5 Direction: UP
Open Door # Floor 5
Close Door
Current Floor: 6 Direction: UP
Current Floor: 7 Direction: UP
Open Door # Floor 7
Close Door
Current Floor: 6 Direction: DOWN
Open Door # Floor 6
Close Door
Current Floor: 5 Direction: DOWN
Open Door # Floor 5
Close Door
Current Floor: 4 Direction: DOWN
Current Floor: 3 Direction: DOWN
Open Door # Floor 3
Close Door

類圖設計

代碼分析

• 本次代碼增至 399 行，類和接口數量從 2 個提升到 7 個，平均每個類方法數從 4.5 變為 5.43 。
• 平均復雜度降至 2.24* ，最復雜的方法為 Controller.determineTarget()（即原Lift.getTarget()），復雜度達 14* ，相較于上次最復雜方法的 40* 有大幅降低。代碼復雜度優化明顯，最復雜的方法得到了很大改善。
• 最大塊深度 6 ，平均塊深度 2.34 ，深度 4 及以上語句數明顯減少，深度 7 - 9 + 無語句分布 ，大部分代碼邏輯集中在較淺深度。較上次進步明顯。

總結與心得

相較于第一次的程序有明顯改善，本次程序進行了遵循SRP的類設計，添加了排除錯誤輸入的新功能，并且優化了算法。寫代碼的過程依舊很折磨，首次提交的代碼基本上就是將第一次的程序由一個類分為多個類，算法沒有任何修改。結果提交上去始終是部分正確，測試點1一直無法通過。在經過多次試錯以及和同學的交流之后，終于確定是選擇目標算法的問題。在重新設計了選擇目標算法后測試點1終于通過。

第三次電梯調度程序

題目：

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

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

• 乘客請求輸入變動情況：外部請求由之前的<請求樓層數,請求方向>修改為<請求源樓層，請求目的樓層>
  對于外部請求，當電梯處理該請求之后（該請求出隊），要將<請求源樓層，請求目的樓層>中的請求目的樓層加入到請求內部隊列(加到隊尾）

輸入格式:

同一

輸出格式:

同一

輸入樣例1:

1
20
<5,4>
<5>
<7>
end

輸出樣例1:

Current Floor: 1 Direction: UP
Current Floor: 2 Direction: UP
Current Floor: 3 Direction: UP
Current Floor: 4 Direction: UP
Current Floor: 5 Direction: UP
Open Door # Floor 5
Close Door
Current Floor: 6 Direction: UP
Current Floor: 7 Direction: UP
Open Door # Floor 7
Close Door
Current Floor: 6 Direction: DOWN
Current Floor: 5 Direction: DOWN
Open Door # Floor 5
Close Door
Current Floor: 4 Direction: DOWN
Open Door # Floor 4
Close Door

輸入樣例2:

1
20
<5,9>
<8>
<9,3>
<4>
<2>
end

輸出樣例2:

Current Floor: 1 Direction: UP
Current Floor: 2 Direction: UP
Current Floor: 3 Direction: UP
Current Floor: 4 Direction: UP
Current Floor: 5 Direction: UP
Open Door # Floor 5
Close Door
Current Floor: 6 Direction: UP
Current Floor: 7 Direction: UP
Current Floor: 8 Direction: UP
Open Door # Floor 8
Close Door
Current Floor: 9 Direction: UP
Open Door # Floor 9
Close Door
Current Floor: 8 Direction: DOWN
Current Floor: 7 Direction: DOWN
Current Floor: 6 Direction: DOWN
Current Floor: 5 Direction: DOWN
Current Floor: 4 Direction: DOWN
Open Door # Floor 4
Close Door
Current Floor: 3 Direction: DOWN
Current Floor: 2 Direction: DOWN
Open Door # Floor 2
Close Door
Current Floor: 3 Direction: UP
Current Floor: 4 Direction: UP
Current Floor: 5 Direction: UP
Current Floor: 6 Direction: UP
Current Floor: 7 Direction: UP
Current Floor: 8 Direction: UP
Current Floor: 9 Direction: UP
Open Door # Floor 9
Close Door
Current Floor: 8 Direction: DOWN
Current Floor: 7 Direction: DOWN
Current Floor: 6 Direction: DOWN
Current Floor: 5 Direction: DOWN
Current Floor: 4 Direction: DOWN
Current Floor: 3 Direction: DOWN
Open Door # Floor 3
Close Door

類圖設計

代碼分析

• 本次代碼行數從 399 增至 420 ，類和接口數量不變仍為 7 個，但平均每個類方法數從 5.43 變為 5.86 ，方法平均語句數從 4.45 變為 4.34。
• 平均復雜度從 2.24* 微降至 2.17* ，最大復雜度維持在 14* （仍是 Controller.determineTarget() ），整體復雜度基本穩定，未出現大幅波動。
• 最大塊深度和平均塊深度變化不大，分別從 6 和 2.34 變為 6 和 2.48 。

總結與心得

對于涉及隊列請求的類和算法都進行了重新設計，再次改進算法。提交后發現還是有測試點未通過，居然還是非零返回。然后一個一個地排查問題，結果發現是程序在開始運行是會嘗試讀取內外兩個隊列（沒有考慮只輸入一個隊列的情況）結果發生了非零返回，修改后順利通過。

踩坑心得

最大的坑

最大的坑就是算法的問題，對于如何模擬電梯運行，我實際上有兩種構想，第一種：電梯每運行一層，就根據當前的位置與隊列請求的信息判斷運行的方向和是否停止。第二種：即前文所述。但由于最開始寫的時候對題目理解不清晰，導致并沒有正確的實現一個合理的思路，后續老師講解題目的時候又已經開始使用第二種思路。思來想去，最后還是懶得改了。錯誤的思路帶來的結果就是這三次題目集的電梯運行模擬實現，給我的體驗都極其糟糕。就好比盲人摸象，一次又一次的修改算法，得到的反饋卻只有正確和錯誤。在無數錯誤的反饋中，像無頭蒼蠅一樣亂轉，最終僥幸蒙對。

其他的問題

1. 比較明顯的問題，程序處理輸入數據的時候使用字符串數組，有需求的時候再解析成數據。，主打一個湊合就行，不僅提高了程序的復雜度，降低了健壯性。還導致程序可擴展性比較差，最后還是得改用LinkedList。
2. 其次，還是思路的問題，因為采用了第二種思路，導致程序選擇目標與前往目標的過程不一致。而這兩者又共用Lift類的方向屬性。使得程序的輸出一些問題。
   如圖：
   
   解決方案是程序前往目標輸出時不使用Lift類的方向屬性，額外添加一個臨時方向屬性專供輸出時使用。

雜項：

1. end不區分大小寫，在瀏覽討論區發現。
2. 輸入時判斷內外請求直接根據長度判斷，導致誤判。參考老師的的源碼后改進。
3. 圖方便有很多應該get的數據直接被構造作為屬性，導致類間關系非常復雜。后續改進了一部分。

改進建議

• 選擇目標算法依舊非常復雜，仍有優化空間。
• 所有代碼均無注釋（唯一的注釋還是該老師給的參考源碼忘記刪了），使得閱讀代碼非常困難（自己都看不懂……）。
• 代碼一路迭代，很多地方還是在第一次代碼的基礎是進行刪改的，存在不安全的操作。
• 個別方法存在重復操作的問題，實際上存在優化空間，如：

private boolean determineTarget()
    {
        if (!Queue.getInnerQueue().isEmpty() && !Queue.getOutQueue().isEmpty())
        {
            if (getInToDirection() == getOutToDirection())
            {
                if (getOutToDirection() == Queue.getOutQueue().getFirst().getDirection())
                {
                    if (Math.abs(Queue.getInnerQueue().getFirst().getDirectionFloor() - lift.getCurrentFloor()) >= Math.abs(Queue.getOutQueue().getFirst().getSourceFloor() - lift.getCurrentFloor()))
                    {
                        target.setFloor(Queue.getOutQueue().getFirst().getSourceFloor());
                        target.setDirection(getOutToDirection());
                        lift.setDirection(Queue.getOutQueue().getFirst().getDirection());
                        deleteOutQueueHead();
                        return true;
                    }
                    else
                    {
                        target.setFloor(Queue.getInnerQueue().getFirst().getDirectionFloor());
                        target.setDirection(getInToDirection());
                        lift.setDirection(getInToDirection());
                        deleteInnerQueueHead();
                        return true;
                    }
                }
                else
                {
                    target.setFloor(Queue.getInnerQueue().getFirst().getDirectionFloor());
                    target.setDirection(getInToDirection());
                    lift.setDirection(getInToDirection());
                    deleteInnerQueueHead();
                    return true;
                }
            }
            else
            {
                if (lift.getDirection() == getInToDirection())
                {
                    target.setFloor(Queue.getInnerQueue().getFirst().getDirectionFloor());
                    target.setDirection(getInToDirection());
                    lift.setDirection(getInToDirection());
                    deleteInnerQueueHead();
                    return true;
                }
                else
                {
                    target.setFloor(Queue.getOutQueue().getFirst().getSourceFloor());
                    target.setDirection(getOutToDirection());
                    lift.setDirection(Queue.getOutQueue().getFirst().getDirection());
                    deleteOutQueueHead();
                    return true;
                }
            }
        }
        else if (!Queue.getInnerQueue().isEmpty())
        {
            getInToDirection();
            target.setFloor(Queue.getInnerQueue().getFirst().getDirectionFloor());
            target.setDirection(getInToDirection());
            lift.setDirection(getInToDirection());
            deleteInnerQueueHead();
            return true;
        }
        else if (!Queue.getOutQueue().isEmpty())
        {
            getOutToDirection();
            target.setFloor(Queue.getOutQueue().getFirst().getSourceFloor());
            target.setDirection(getOutToDirection());
            lift.setDirection(Queue.getOutQueue().getFirst().getDirection());
            deleteOutQueueHead();
            return true;
        }
        else
        {
            return false;
        }
    }

總結

通過這3次的題目集，我學習了很多知識，比如：LinkedList類以及一些常用方法，還有泛型的使用等等。在完成題目的過程，我也意識到需求分析能夠掌握正確方向，避免浪費時間。還有類設計的重要性，合理的類設計不僅能夠，還能清晰的把握從需求分析到代碼實現的過程，提高編碼效率，事半功倍。
這次階段性作業對我來說是一次充分的歷練，給我的邏輯思維能力和編碼能力帶來了巨大的提升，使我獲益匪淺。
最后，線下課老師講課的知識點很密集，但是一些地方很不連貫，希望老師能夠給出更多的時間讓學生思考。以及pta的題目可以給出更多的測試點，讓學生更好地理解題意。