約瑟夫環的四種實現方式
一、概念
在開始正題之前，還是解釋一下約瑟夫環是什麼。約瑟夫環是一個數學的應用問題：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重複下去，直到圓桌周圍的人全部出列。通常解決這類問題時我們把編號從0~n-1，最後 [1] 結果+1即為原問題的解。
二、通過數組循環實現
最常規的思路就是通過一個數組，數組中每個元素都是一個人，然後對數組進行循環處理，每當數組中的人數到m時，將其標記為淘汰。直到最後數組中只有一個人未被淘汰。
所以，首先，我們需要一個計算方法，參數中有總數和淘汰數兩個參數。
第二步，我們需要一個長度為total的布爾值數組，數組的index就表示了第幾個人，元素的true和false表示了這個人是否被淘汰。一開始我們需要將所有人都設置為未被淘汰。
接下來第三步，我們需要三個變數：
·第一個變數記錄還剩多少人為被淘汰，這個變數的初始值為總人數；
·第二個變數記錄數到了多少，當這個參數等於淘汰數時歸零；
·第三個參數記錄當時數到了第幾個人，當這個參數等於總人數時歸零（因為是一個圈，所以最後一個人數完後又輪到第一個人數數）
第四步就開始循環計算了，首先判斷剩餘的人數是否大於一，如果大於一進入循環，取index，如果這個人未被淘汰，則計數器加一，如果等於keyNumber則淘汰這個人，否則跳過計數繼續，當index等於總人數時
最後，計算結束後，數組中只有一個元素為true，而這個就是最後沒被淘汰的那個人，現在我們就開開始找到是誰贏得了這次比賽。
我們驗證一下結果：
OK，第一種方法成功。
三、通過鏈表方式實現
最早了解到這種方法是通過馬士兵Java教學視頻了解到的方法，其實通過這個方式可以讓人更好的理解面向對象的思想和雙向循環鏈表。
第一步，我們要抽象出一些對象，在約瑟夫環這個命題中，有這樣兩個對象：人和環。人具有幾個屬性：編號，左邊的人和右邊的人。環具有幾個屬性和方法：總人數，第一個人，最後一個人，添加人和移除人。
好了，第二步我們就開始實現自己抽象出來的對象，先是People對象：
接下來是Circle對象：
最後，我們開始計算了，先向環里添加人，然後取到第一個人進行處理，處理完第一個之後取到第一人之後的一個人繼續處理，最後返回處理完的環。
下面我們來看一下執行結果：
成功，是不是覺得思想上有點繞，但是這是典型的面向對象思想，可以多消化消化。
四、Java自帶鏈表實現（LinkedList）
其實使用Java自帶的LinkedList就可以很簡單的實現我們要的效果。直接上代碼了：
是不是很簡單，能夠這麼簡單的基礎是因為鏈表的remove()方法的特殊性，第一輪循環時，index=2的元素就是3，但它找到需要刪除的元素後鏈表size-1，此時index=2指向的是原index=3的元素，也就說index不用變，這樣正好滿足了我們的需求。
約瑟夫環還有其他的方法可以實現，但是我目前學習到的只有這三種方法實現，如果以後學習到其他的方法實現，再回來進行補充。
原文地址：https://my.oschina.net/jack90john/blog/1791110
作者：珂jack
※Oracle資料庫——Oracle事務和常用數據對象優化
※RabbitMQ實戰：運行和管理RabbitMQ
TAG:深秀Deepshow |