java怎麼解決約瑟夫問題

一、約瑟夫問題介紹

1、約瑟夫問題原題：

n個小孩子手拉手圍成一個圈，編號為k(1

2、問題分析：

根據題目的描述，很容易可以想到用單向循環鍊錶來模擬。先構成一個有n個節點的單向循環鍊錶，然後節點K由1開始計數，計到m時，對應的節點從鍊錶中刪除，然後再從被刪除的下一個節點由1開始計數，直到所有節點都被刪除掉。

單向循環鍊錶

假設從編號為1的人開始，每次報數報到2的人出列，如果有$n= 5$個人，則$k=1,m=2$。那麼最後出列的結果應該是：2，4，1，5，3。

 

二、單向環形鍊錶的建構

1、建構想法：

• ##先建立第一個節點，用first指標指向它，它的next指向自己，如下圖：

第一個節點

• 接著，建立第二個節點，並將第一個節點的next指標指向第二個節點，同時將第二個節點的next指標指向第一個節點，如下圖中所示：

第二個節點

#依此類推，就可以建構出單向環形鍊錶。遍歷的時候，當節點的next等於first時，表示遍歷完畢。

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>

傳入參數為k=1，m=2，n=5時，執行方法的結果與上述分析相同，輸出序列為2,4,1,5,3。

#

以上是java怎麼解決約瑟夫問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！