关于约瑟夫问题的Java版

关于约瑟夫问题的Java版

java 链表实现：

Java code

package com.wayfoon.test;

import java.util.LinkedList;
import java.util.List;
/**
 * 有M个人，其编号分别为1－M。这M个人按顺序排成一个圈。
 * 现在给定一个数N，从第一个人开始依次报数，数到N的人出列，
 * 然后又从下一个人开始又从1开始依次报数，
 * 数到N的人又出列．．．如此循环，直到最后所有人出列为止。
 * 输出出列轨迹
 *
 */

public class Tx
{
    //存放M
    List<String> list = new LinkedList<String>();
    //一圈数数完之后，临时存放出列的人
    List<String> tmp = new LinkedList<String>();

    public Tx(int m)
    {
        for (int i = 1; i <= m; i++)
        {
            list.add(i + "");
        }
    }

    /**
     * 递归 执行主体
     * @param start
     * @param n
     */
    public void start(int start,int n)
    {
        int size = list.size();
        if (list.size() == 0)
        {
            System.out.println("结束！！");
            return ;
        }
        for (int i = 1; i <= size; i++)
        {
            if ((i + start) % n == 0)
            {
                System.out.println(list.get(i - 1) + " 出局,");
                tmp.add(list.get(i - 1));
            }
        }
        //在m中删除临时队列的人
        for (String str : tmp)
        {
            list.remove(str);
        }
        //清除list
        tmp.clear();
        //递归
        start((size + start) % n,n);
    }

    public static void main(String[] args)
    {
        long t1=System.currentTimeMillis();
       
        //M=100
        Tx tx = new Tx(100);
        //n=7
        tx.start(0,7);
       
        System.out.print("花费时间：");
        System.out.println(System.currentTimeMillis()-t1);

    }

}

执行结果，

7 出局,
14 出局,
21 出局,
28 出局,
35 出局,
42 出局,
49 出局,
56 出局,
63 出局,
70 出局,
77 出局,
84 出局,
91 出局,
98 出局,
5 出局,
13 出局,
22 出局,
30 出局,
38 出局,
46 出局,
54 出局,
62 出局,
71 出局,
79 出局,
87 出局,
95 出局,
3 出局,
12 出局,
23 出局,
32 出局,
41 出局,
51 出局,
60 出局,
69 出局,
80 出局,
89 出局,
99 出局,
9 出局,
19 出局,
31 出局,
43 出局,
53 出局,
65 出局,
75 出局,
86 出局,
97 出局,
10 出局,
24 出局,
36 出局,
48 出局,
61 出局,
74 出局,
88 出局,
1 出局,
16 出局,
29 出局,
45 出局,
59 出局,
76 出局,
92 出局,
6 出局,
25 出局,
40 出局,
58 出局,
78 出局,
94 出局,
15 出局,
34 出局,
55 出局,
73 出局,
96 出局,
18 出局,
44 出局,
67 出局,
90 出局,
17 出局,
47 出局,
72 出局,
2 出局,
33 出局,
66 出局,
100 出局,
37 出局,
81 出局,
11 出局,
57 出局,
4 出局,
52 出局,
8 出局,
68 出局,
27 出局,
93 出局,
83 出局,
82 出局,
85 出局,
26 出局,
64 出局,
20 出局,
39 出局,
50 出局,
结束！！
花费时间：15
Java code 

class OnelinkNode // 单向链表的结点类
{
    public int data; // 存放结点值
    public OnelinkNode next; // 后继结点的引用

    public OnelinkNode(int k) // 构造值为k的结点
    {
        data = k;
        next = null;
    }

    public OnelinkNode() // 无参数时构造值为0的结点
    {
        this(0);
    }
}

public class Josephus //单向循环链表，解约瑟夫环
{
    private OnelinkNode head;

    Josephus(int n) // 建立n个结点的单向循环链表
    { // 链表结点值为1到n
        int i = 1;
        OnelinkNode q, rear;
        if(n > 0){
            head = new OnelinkNode(i);
            head.next = head;
            rear = head;
            while(i < n){
                i++;
                q = new OnelinkNode(i);
                q.next = head;
                rear.next = q;
                rear = q;
            }
        }
    }

    public void display(int s,int d) // 解约瑟夫环
    {
        int j = 0;
        OnelinkNode p = head;
        while(j < s - 1) // 计数起始点
        {
            j++;
            p = p.next;
        }
        while(p.next != p) // 多于一个结点时循环
        {
            j = 1;
            while(j < d - 1) // 计数
            {
                j++;
                p = p.next;
            }
            delete(p); // 删除p的后继结点
            p = p.next;
            this.output();
        }
    }

    public void delete(OnelinkNode p) // 删除p的后继结点
    {
        OnelinkNode q = p.next; // q是p的后继结点
        System.out.print("delete:  " + q.data + "  ");
        if(q == head) // 欲删除head指向结点时，
            head = q.next; // 要将head向后移动
        p.next = q.next; // 删除q
    }

    public void output() // 输出单向链表的各个结点值
    {
        OnelinkNode p = head;
        System.out.print("data:  ");
        do{
            System.out.print(p.data + " -> ");
            p = p.next;
        }while(p != head);
        System.out.println();
    }

    public static void main(String args[]){
        int n = 5, s = 1, d = 2;
        Josephus h1 = new Josephus(n);
        h1.output();
        h1.display(s,d);
    }
}
data:  1 -> 2 -> 3 -> 4 -> 5 -> 
delete:  2  data:  1 -> 3 -> 4 -> 5 -> 
delete:  4  data:  1 -> 3 -> 5 -> 
delete:  1  data:  3 -> 5 -> 
delete:  5  data:  3 -> 

import java.io.*; 
class Node{              //定义结点类 
int data; 
Node next; 
public Node (int d){ 
data=d; 
} 
public int data(){ 
return data; 
} 
} 
class CirLinkList{    //定义链表类 
private Node current; 
private int size=0; 
public CirLinkList(int n){ 
Node tail=new Node(n); 
current=tail; 
for(int i=n-1;i>0;i--){ 
Node tmp=new Node(i); 
tmp.next=current; 
current=tmp; 
} 
tail.next=current; 
size+=n; 
} 
public int  size(){  //链表大小 
return size; 
} 
public void step(int n){  //遍历结点 
for(int i=0;i <n;i++){ 
current=current.next; 
} 
} 
public Node dalete(){ 
Node temp=current.next; 
current.next=temp.next; 
size--; 
return temp; 
}//删除结点 
public void display(){  //显示结点 
Node start=current,end=current; 
while(end.next!=start){ 
System.out.print(Integer.toString(end.data)+" "); 
end=end.next; 
} 
System.out.println(end.data); 
} 
}      
public class Josephus { 

    public Josephus() { 
    } 
    public static void main(String []args)throws IOException{ 
    System.out.print("总人数："); 
    String str=getString(); 
    int n=Integer.parseInt(str); 
    CirLinkList L=new CirLinkList(n); 
    System.out.print("开始号码："); 
    String start_position=getString(); 
    int start=Integer.parseInt(start_position); 
    L.step(start-1); 
    System.out.print("报数："); 
    String step_length=getString(); 
    int stp=Integer.parseInt(step_length); 
    System.out.print("出局编号："); 
    while(L.size()>1){ 
    L.step(stp-2); 
    Node death=L.dalete(); 
    L.step(1); 
    System.out.println(death.data()+"号"); 
    } 
    System.out.print(""); 
    System.out.print("最后的号码:"); 
    L.display(); 
    } 
    public static String getString()throws IOException{ 
    InputStreamReader isr=new InputStreamReader(System.in); 
    BufferedReader br=new BufferedReader(isr); 
    String s=br.readLine(); 
    return s; 
    } 
    
}