1、約瑟夫問題原題：
n個小孩子手拉手圍成一個圈，編號為k(1
2、問題分析：
根據題目的描述，很容易可以想到用單向循環鍊錶來模擬。先構成一個有n個節點的單向循環鍊錶，然後節點K由1開始計數，計到m時，對應的節點從鍊錶中刪除，然後再從被刪除的下一個節點由1開始計數，直到所有節點都被刪除掉。
假設從編號為1的人開始，每次報數報到2的人出列，如果有$n= 5$個人，則$k=1,m=2$。那麼最後出列的結果應該是：2，4，1，5，3。
1、建構想法：
第一個節點
第二個節點2、程式碼實作：
根據上面的分析，可以寫出如下程式碼：
<code>package com.zhu.study.linkedList;<br><br>/**<br> * 约瑟夫问题，即单向循环链表问题<br> * @author: zhu<br> * @date: 2020/8/30 17:57<br> */<br>public class Josepfu {<br> public static void main(String[] args){<br> CircleSingleLinkedlist linkedlist = new CircleSingleLinkedlist();<br> linkedlist.add(5);<br> linkedlist.showNodes();<br> }<br>}<br><br>/**<br> * 单向循环链表<br> */<br>class CircleSingleLinkedlist{<br> private Node first = null;<br> /**<br> * 添加节点<br> * @param num 需要添加的节点个数<br> */<br> public void add(int num){<br> if (num throw new RuntimeException("非法参数");<br> }<br> Node cur = null; // 当前node<br> for (int i = 1; i Node node = new Node(i);<br> if (i == 1) {<br> first = node;<br> first.setNext(first); // next指向自己，构成环<br> cur = first;<br> } else {<br> cur.setNext(node);<br> node.setNext(first);<br> cur = node;<br> }<br> }<br> }<br><br> /**<br> * 遍历<br> */<br> public void showNodes(){<br> if (first == null){ // 链表为空<br> return;<br> }<br> Node cur = first;<br> while (true){<br> System.out.printf("小孩编号%d \n", cur.getNo());<br> if (cur.getNext() == first){ // 遍历完毕<br> break;<br> } else {<br> cur = cur.getNext();<br> }<br> }<br> } <br>}<br><br>/**<br> * 节点内部类<br> */<br>class Node{<br> private int no; // 编号<br> private Node next; // 下一个节点<br><br> public Node(int no){<br> this.no = no;<br> }<br><br> public int getNo() {<br> return no;<br> }<br><br> public void setNo(int no) {<br> this.no = no;<br> }<br><br> public Node getNext() {<br> return next;<br> }<br><br> public void setNext(Node next) {<br> this.next = next;<br> }<br>}<br></code>1、想法：
#先找到開始報數的節點，用cur記錄下來，例如從第k個開始數，那麼cur應該指向k號節點；然後再找到cur的前一個節點，用pre記錄下來；找到這兩個節點後，由cur開始數(m-1)次，即cur和pre同時移動(m-1)次，此時cur就指向了要被刪除的節點；列印要被刪除的節點，然後將cur移到被刪除節點的下一個節點，即cur = cur.next，pre的next指向新的cur，即pre.next = cur。
2、程式碼實作：
<code>/**<br> * 出圈，圈中共有n个人，从第k个开始，数m个开始出圈<br> * @param k<br> * @param m<br> * @param n<br> */<br> public void get(int k, int m, int n){<br> if (k > n || k n){<br> throw new IllegalArgumentException("非法参数");<br> }<br> // 先找到k节点，即开始报数的节点，用cur记录下来<br> Node cur = first;<br> for (int i = 1; i cur = cur.getNext();<br> }<br> // 找到k的前一个节点，用pre记录下来<br> Node pre = cur;<br> while (true){<br> if (pre.getNext() == cur){<br> break;<br> } else{<br> pre = pre.getNext();<br> }<br> }<br> // 出圈<br> while (true) {<br> if (pre == cur) { // 只有一个节点了<br> System.out.printf("小孩编号%d\n", cur.getNo());<br> break;<br> }<br> // cur和pre同时移动 m-1次<br> for (int i = 1; i cur = cur.getNext(); // 这个就是要出圈的节点<br> pre = pre.getNext(); // 这个是要出圈节点的前一个节点<br> }<br> System.out.printf("小孩编号%d\n", cur.getNo());<br> cur = cur.getNext();<br> pre.setNext(cur);<br> }<br> }</code>以上是java怎麼解決約瑟夫問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！
