约瑟夫环问题——《算法》1.1.37的解法

话不多说，先给出题的图

 这个题的意思就是给一个人数N，比如7，从0开始标号，0，1，2，3，4，5，6。这样最后一个就是6。然后再报一个数M，比如2，

这样第一次从0开始，数2，就是标号为1的在第一轮出局。这样剩下0，2，3，4，5，6，

这次是从2，开始数，这样出局的是3，剩下0，2，4，5，6。

然后从4开始数，出局的是5，剩下0，2，4，6。

然后从6开始数，出局的是0，剩下2，4，6。

这次从2开始数，这样出局的是4，剩下2，6。

最后从6开始数，2出局。剩下6。

6。

一、问题思路

题目是要编写一个Queue的用例。一开始想到如果M比较大，剩下的数比较少的时候，怎么办？可以考虑用M对剩下的数取模的方法。后来想到用环形的单链表其实还比较容易实现。

 像图示那样，设计一个单向环链表，然后设置一个where指针，一开始指向所加的最后一个元素6。然后要删除的时候，比如M=2，让where指针走M-1次next就可以指向“1”，然后用delete方法删除1就可以了。然后再次走的话，再重复就可以了。

二、解决方案

1、设计node类

链表上的每个元素包含1个int类型数值，还要包含node，指向next。

class Node{
    int num;
    Node next;
    Node(){
        this.num = 100;
        this.next = null;
    }
    Node(int element) {
        this.num = element;
        this.next = null;
    }
}

2、创建josephus环

 public void create(){
        this.josephus = new Node();
        this.where = josephus;
        this.nodenum = 0;
    }

一开始where指针指向头节点josephus.

3、如何加元素

增加一个元素的话，让新增的元素放在where后面，所以where.next = newNode ，然后再让where向前移动一格，where= where.next。新节点指向第一个节点。newNode.next = josephus.next.然后整个环的节点数+1。

public void add(int element){
        Node newNode = new Node(element);
        where.next= newNode;
        this.where = newNode;
        newNode.next = this.josephus.next;
        this.nodenum++;
    }

4、如何删除元素。因为约瑟夫环要求删除某个元素，有一个参数M。

根据我们的分析，对于参数M，就是让where指针向前走M-1步，然后删除where.next节点，就是让where.next = where.next.next，记录被删除元素的节点num值。

public int minus(int M){
        int deleted;
        for(int i = 1 ; i < M ; i++)
            where = where.next;
        deleted = where.next.num;
        where.next = where.next.next;
        this.nodenum--;
        return deleted;
    }

当然这里最好有个是否为空的判断。

5、最后给出测试用例：

public static void main(String[] args) {
        Josephus josephus = new Josephus();
        josephus.create();
        int i;
        for( i = 0 ; i < 10 ; i ++ )
            josephus.add(i);
        System.out.println(josephus.where.num);
        for(i = 1; i < 10;i++) {
            int minus = josephus.minus(17);
            System.out.print(minus+" ");
        }
 
    }

9
6 4 5 9 7 0 1 3 8 
Process finished with exit code 0

6、最后给出全部类及测试的代码

class Node{
    int num;
    Node next;
    Node(){
        this.num = 100;
        this.next = null;
    }
    Node(int element) {
        this.num = element;
        this.next = null;
    }
}
 
 
public class Josephus {
    int nodenum;
    Node josephus;
    Node where;
 
    public void create(){
        this.josephus = new Node();
        this.where = josephus;
        this.nodenum = 0;
    }
    public int size(){return this.nodenum;}
    public void add(int element){
        Node newNode = new Node(element);
        where.next= newNode;
        this.where = newNode;
        newNode.next = this.josephus.next;
        this.nodenum++;
    }
    public int minus(int M){
        int deleted;
        for(int i = 1 ; i < M ; i++)
            where = where.next;
        deleted = where.next.num;
        where.next = where.next.next;
        this.nodenum--;
        return deleted;
    }
    public static void main(String[] args) {
        Josephus josephus = new Josephus();
        josephus.create();
        int i;
        for( i = 0 ; i < 10 ; i ++ )
            josephus.add(i);
        System.out.println(josephus.where.num);
        for(i = 1; i < 10;i++) {
            int minus = josephus.minus(17);
            System.out.print(minus+" ");
        }
 
    }
}