约瑟夫问题 java

约瑟夫问题

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

java 实现：

package com.wayfoon.test;

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

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

网上搜索到的采用c语言，双链表实现，不错

#include<stdio.h>
struct node{
int s;
node* head,*tail;
};
int main()
{
int n,k;scanf("%d%d",&n,&k);
node *Begin,*End,*tem;
Begin=new node;
Begin->head=Begin->tail=NULL;Begin->s=1;
End=Begin;
for (int i=2;i<=n;i++){
tem=new node;
tem->head=End;
tem->s=i;
End->tail=tem;
End=tem;
}
End->tail=Begin;Begin->head=End;
int m=n;
tem=Begin;
while (m>0){
int c=1,p=k%m-1;// p表示要循环多小次
if (p>0){ // 正数表示顺时针 负数表示逆时
if (p>m-(p+2)+2){ // <--比较顺时针快还是逆时针快
p=m-(p+2)+2;
while (c!=p){
c++;tem=tem->head;
}
if (m!=1) printf("%d ",tem->head->s);
else printf("%d\n",tem->head->s);
tem->head->head->tail=tem;
tem->head=tem->head->head;
}else{
while (c!=p){
c++;tem=tem->tail;
}
if (m!=1) printf("%d ",tem->tail->s);
else printf("%d\n",tem->tail->s);
tem->tail->tail->head=tem;
tem->tail=tem->tail->tail;
tem=tem->tail;
}
}else{
p=-p;
if (!p){ // <--特殊处理输出本身
if (m!=1) printf("%d ",tem->s);
else printf("%d\n",tem->s);
tem->head->tail=tem->tail;
tem->tail->head=tem->head;
tem=tem->tail;
}else{
while (c!=p){
c++;tem=tem->head;
}
if (m!=1) printf("%d ",tem->head->s);
else printf("%d\n",tem->head->s);
tem->head->head->tail=tem;
tem->head=tem->head->head;
}
}
m--;
}
return 0;
}

评论

1 楼 coolbaby1984514 2010-05-07  

public int findMonkey(int n, int m)
{
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + m) % i;
    return r+1;
}