关于约瑟夫问题的Java版

public class Josephus
{
public static void main(String args[])
{
if(args.length != 2) //处理参数数目不正确情况
{
   System.out.println("Please Input a number!");
   return;
}
int i, j, n, m;
n = Integer.parseInt(args[0]);
m = Integer.parseInt(args[1]);
if (n <= 0 || m <= 0) //处理参数值不正确的情况
{
    System.out.println("Paramter must bigger than zero!");
    return;
}
int a[] = new int[n];
for (i = 0; i < n; i++) a[i] = i + 1;
int k = 1;   //标识处理第k个离开的人
i = -1;    //数组下标,下一个为0,即第一个人
while (true) //k等于n表示只剩下一个人了
{
   for (j = 0; j < m;) //在圈中数m个人
   {
    i = (i + 1) % n;
    if (a[i] >0) j++; //a[i] >0表示第i个人还没有离开
   }
   if(k==n) break;
   System.out.println("No." + a[i] + " is out!");
   a[i] = -1;   //表示该人离开
   k++;
}
System.out.println("No." + a[i] + " is the winner!");
}
}
输入：
C:\Documents and Settings\circle\桌面>java Josephus 9 4
输出结果：
No.4 is out!
No.8 is out!
No.3 is out!
No.9 is out!
No.6 is out!
No.5 is out!
No.7 is out!
No.2 is out!
No.1 is the winner!
给你找的。不是链表，。哈

java 链表实现：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

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 ->

请问2楼的程序有没有bug？因为最后一轮有可能人数不足7个怎么办？

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;
    }

}

测试通过！--------------------配置: <Default>--------------------
总人数：34
开始号码：3
报数：5
出局编号：7号
12号
17号
22号
27号
32号
3号
9号
15号
21号
28号
34号
6号
14号
23号
30号
4号
13号
24号
33号
10号
20号
1号
16号
29号
11号
31号
19号
8号
5号
18号
26号
2号
最后的号码:25处理已完成。

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 ->

学C语言的时候写过，那时候是用数组模仿链表做的，java只要改一下就好了吧。

javascript:alert('111')

我没写过Java版的，不过有C语言的约瑟夫环问题，算法思想一样，语言不是问题，很简单

弱问各位大侠：JavaAPI里的LinkedList类有什么用啊？除了二楼的import了，其他牛人都是自己重新建的链表额

Good ,I want to study very much

调试易

关于约瑟夫问题的Java版

解决方案 »