約瑟夫（Josephu）問題

Josephu問題為: 設編號為1, 2，… n的n個人圍坐一圈，約定編號為k (1<=k<=n) 的人從1開始報數，數到m的那個人出列，它的下一位又從1開始報數，數到m的那個人又出列，依次類推，直到所有人出列為止，由此產生一個出隊編號的序列。

解決思路

用一個不帶頭結點的循環鏈表解決：先構成一個帶有n個節點的單向環形鏈表，然后由k節點起從1開始計數，計到m時，對應節點從鏈表中刪除，然后再從被刪除節點的下一個節點開始數，直到最后一個節點從鏈表中刪除。

代碼實現

單向循環鏈表 和單鏈表區別在于單向循環鏈表的最后一個節點指向第一個節點，且沒有頭結點。

//約瑟夫問題單向環形鏈表解決 public class CircleSingleLinkedListDemo {public static void main(String[] args) {CircleSingleLinkedList list = new CircleSingleLinkedList();list.addBoy(10);list.traverseBoy();list.countBoy(2,2,10);} }class CircleSingleLinkedList{public Boy first = null;//第一個節點/*** 添加num個節點* @param num*/public void addBoy(int num){if (num<1){System.out.println("num的值不正確");return;}Boy curBoy = null;//輔助變量，幫助遍歷for (int i = 1; i <=num ; i++) {Boy boy= new Boy(i);//創建節點if (i == 1){//如果為第一個節點給第一個節點賦值first=boy;first.setNext(boy);//cirBoy指向當前的firstcurBoy = first;}else {//將當前節點指向下一個節點添加的節點boycurBoy.setNext(boy);//將最后一個節點指向第一個節點，形成環形鏈表boy.setNext(first);//curBoy后移一位curBoy = boy;}}}/*** 遍歷環形鏈表*/public void traverseBoy(){if (first==null){System.out.println("環形鏈表為空");return;}Boy curBoy = first;//輔助變量，用于遍歷System.out.print("遍歷結果：");while (true){System.out.print(curBoy.getNo()+" ");if (curBoy.getNext()==first){break;}//當前節點curBoy后移一位curBoy= curBoy.getNext();}System.out.println();}/**** @param startNo 表示從第幾個小孩開始數* @param countNum 表示每次數幾下* @param nums 表示一共有幾個小孩*/public void countBoy (int startNo,int countNum,int nums){if (first ==null || startNo<1 ||countNum>nums){System.out.println("參數輸入有誤");return;}System.out.print("出圈順序：");//先讓first節點和開始節點為同一個節點for (int i = 0; i <startNo - 1 ; i++) {first = first.getNext();}//創建輔助變量helper指向最后一個節點Boy helper =first;while (true){if (helper.getNext()==first){//遍歷結束break;}helper= helper.getNext();}//讓firs和helper同時移動countNum -1次數后，first就為要出圈的那個節點//循環操作，直到圈中只有一個節點while (true) {if (first == helper){//圈中只有一個結點break;}//firs和helper同時移動countNum -1次for (int i = 0; i < countNum - 1; i++) {first = first.getNext();helper = helper.getNext();}//first就為要出圈的那個節點System.out.print(first.getNo()+"-->");//刪除出圈的節點first = first.getNext();helper.setNext(first);}System.out.println(first.getNo());} }class Boy{private int no;//節點編號private Boy next; //下一個節點，默認為空public Boy(int no) {this.no = no;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public Boy getNext() {return next;}public void setNext(Boy next) {this.next = next;}@Overridepublic String toString() {return "Boy{" +"no=" + no +'}';} }

總結

以上是生活随笔為你收集整理的（数据结构与算法）单向环形链表解决约瑟夫问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。