java怎么解決約瑟夫問題

一、約瑟夫問題介紹

1、約瑟夫問題原題：

n個小孩子手拉手圍成一個圈，編號為k(1 <= k <= n )的人從1開始報數(shù)，報到m的那個人出列，它的下一位又從1開始報數(shù)，報到m的又出列……依此類推，直到所有人都出列，由此產(chǎn)生一個出隊編號的序列。

2、問題分析：

根據(jù)題目的描述，很容易可以想到用單向循環(huán)鏈表來模擬。先構(gòu)成一個有n個節(jié)點的單向循環(huán)鏈表，然后節(jié)點K由1開始計數(shù)，計到m時，對應(yīng)的節(jié)點從鏈表中刪除，然后再從被刪除的下一個節(jié)點由1開始計數(shù)，直到所有節(jié)點都被刪除掉。

如上圖，n等于5，假設(shè)從1號開始報數(shù)，報到2就出列，即k等于1，m等于2。那么最后出列的結(jié)果應(yīng)該是：2，4，1，5，3。

二、單向環(huán)形鏈表的構(gòu)建

1、構(gòu)建思路：

• 首先創(chuàng)建第一個節(jié)點，用first指針指向它，它的next指向自己，如下圖：

• 然后創(chuàng)建第二個節(jié)點，將第一個節(jié)點的next指向第二個節(jié)點，第二個節(jié)點的next指向第一個節(jié)點，如圖：

依此類推，就可以構(gòu)建出單向環(huán)形鏈表。遍歷的時候，當(dāng)節(jié)點的next等于first時，表示遍歷完畢。

2、代碼實現(xiàn)：

根據(jù)上面的分析，可以寫出如下代碼：

package com.zhu.study.linkedList;

/**
 * 約瑟夫問題，即單向循環(huán)鏈表問題
 * @author: zhu
 * @date: 2020/8/30 17:57
 */
public class Josepfu {
    public static void main(String[] args){
        CircleSingleLinkedlist linkedlist = new CircleSingleLinkedlist();
        linkedlist.add(5);
        linkedlist.showNodes();
    }
}

/**
 * 單向循環(huán)鏈表
 */
class CircleSingleLinkedlist{
    private Node first = null;
    /**
     * 添加節(jié)點
     * @param num 需要添加的節(jié)點個數(shù)
     */
    public void add(int num){
        if (num < 1){
            throw new RuntimeException("非法參數(shù)");
        }
        Node cur = null; // 當(dāng)前node
        for (int i = 1; i <= num; i++) {
            Node node = new Node(i);
            if (i == 1) {
                first = node;
                first.setNext(first); // next指向自己，構(gòu)成環(huán)
                cur = first;
            } else {
                cur.setNext(node);
                node.setNext(first);
                cur = node;
            }
        }
    }

    /**
     * 遍歷
     */
    public void showNodes(){
        if (first == null){ // 鏈表為空
            return;
        }
        Node cur = first;
        while (true){
            System.out.printf("小孩編號%d \n", cur.getNo());
            if (cur.getNext() == first){ // 遍歷完畢
                break;
            } else {
                cur = cur.getNext();
            }
        }
    }   
}

/**
 * 節(jié)點內(nèi)部類
 */
class Node{
    private int no; // 編號
    private Node next; // 下一個節(jié)點

    public Node(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

三、小孩出列的實現(xiàn)

1、思路：

先要找到開始報數(shù)的節(jié)點，用cur記錄下來，比如從第k個開始數(shù)，那么cur應(yīng)該指向k號節(jié)點；然后再找到cur的前一個節(jié)點，用pre記錄下來；找到這兩個節(jié)點后，由cur開始數(shù)(m-1)次，即cur和pre同時移動(m-1)次，此時cur就指向了要被刪除的節(jié)點；打印要被刪除的節(jié)點，然后將cur移動到被刪除節(jié)點的下一個節(jié)點，即cur = cur.next，pre的next指向新的cur，即pre.next = cur。

2、代碼實現(xiàn)：

/**
     * 出圈，圈中共有n個人，從第k個開始，數(shù)m個開始出圈
     * @param k
     * @param m
     * @param n
     */
    public void get(int k, int m, int n){
        if (k > n || k < 1 || first == null || m > n){
            throw new IllegalArgumentException("非法參數(shù)");
        }
        // 先找到k節(jié)點，即開始報數(shù)的節(jié)點，用cur記錄下來
        Node cur = first;
        for (int i = 1; i < k; i++) {
            cur = cur.getNext();
        }
        // 找到k的前一個節(jié)點，用pre記錄下來
        Node pre = cur;
        while (true){
            if (pre.getNext() == cur){
                break;
            } else{
                pre = pre.getNext();
            }
        }
        // 出圈
        while (true) {
            if (pre == cur) { // 只有一個節(jié)點了
                System.out.printf("小孩編號%d\n", cur.getNo());
                break;
            }
            // cur和pre同時移動 m-1次
            for (int i = 1; i < m; i++) {
                cur = cur.getNext(); // 這個就是要出圈的節(jié)點
                pre = pre.getNext(); // 這個是要出圈節(jié)點的前一個節(jié)點
            }
            System.out.printf("小孩編號%d\n", cur.getNo());
            cur = cur.getNext();
            pre.setNext(cur);
        }
    }

調(diào)用該方法，k、m、n分別輸入1、2、5，最后發(fā)現(xiàn)結(jié)果和上面分析的一樣，打印的是2,4,1,5,3。