请教！！有n个人围成一圈，顺序编号。从第一个人开始报数，凡报到m的人退出圈子，问最后一个圈中的人的编号？

Question

非常感谢大家的解答！！

Answer 1

import java.security.InvalidParameterException;
/**
 * Josephus Problem
 * 
 * Given a group of N men arranged in a circle under the edict that every Mth
 * man will be executed going around the circle until only one remains, find the
 * position in which you should stand in order to be the last survivor (Ball and
 * Coxeter 1987).
 * 
 * @author protozz
 * 
 */
public class Josephus { private static int n;// the number of person private static int m;// the interval private static int INDEX_BEGIN = 1; public Josephus(int num, int interval) {
if (interval >= num)
throw new InvalidParameterException();
n = num;
m = interval;
} private void showQueue(Person head) {
Person p = head;
System.out.print(head.index + "->");
head = head.next;
while (head != p) {
System.out.print(head.index + "->"); head = head.next;
}
System.out.println();
} public int getLast() {
Person head = initQueue();
showQueue(head);
int counter = 0;
while (counter != n - 1) {
for (int i = 1; i < m - 1; i++) {
head = head.next;
}
head.next = head.next.next;
head = head.next;
System.out.print(counter + ":");
showQueue(head);
counter++;
}
return head.index;
} private Person initQueue() { Person p = new Person(INDEX_BEGIN);
Person head = p;
for (int i = 0; i < n - 1; i++) {
p.next = new Person(p.index + 1);
p = p.next;
}
p.next = head; return head;
}}class Person {
Person next; int index; public Person(int index) {
this.index = index;
this.next = null;
}
}

Answer 2

import junit.framework.TestCase;
/**
 * 
 * @author protozz
 * 
 */public class JosephusTest extends TestCase {
public void testGetLast() {
Josephus case1 = new Josephus(41, 3);
assertEquals(case1.getLast(), 31);
}

}

Answer 3

to:shendiaoke(风尘豪客) 
我是北京大学应用文理学院毕业的，你也是吗？

Answer 4

几行代码就足够了private static int removeNM(int n, int m) {
LinkedList<Integer> ll = new LinkedList<Integer>();
for(int i = 0; i < n; i++)
ll.add(new Integer(i));
int lastSelected = 0;
while(ll.size() > 1) {
lastSelected = (lastSelected + m) % ll.size();
ll.remove(lastSelected--);
}
return ll.get(0).intValue();
}public static void main(String[] args) throws Exception {
System.out.println(removeNM(100,4));
}

Answer 5

public void outList(int n ,int m)
{
int i;
int list[] = new int[n];
for(i = 0;i<n;i++)
{

list[i] = 1;

}
i = 0;
int num = -1;
while(true)
{   
int next =(num + 1) % n;
if(list[next]!= 0)
{
i++;
if(i == m)
{

list[next] = 0;
System.out.print( (next+1) + " ");
i = 0;
}

}

num = next;
int cnt=0;
for(int o=0;o<n;o++)
{
if(list[o]==1)
{
cnt ++;
}


}
if(cnt ==0)
break;
}
}

Answer 6

好像 private static int removeNM(int n, int m) {
LinkedList<Integer> ll = new LinkedList<Integer>();
for(int i = 0; i < n; i++)
ll.add(new Integer(i));
int lastSelected = 0;
while(ll.size() > 1) {
lastSelected = (lastSelected + m) % ll.size();
ll.remove(lastSelected--);
}
return ll.get(0).intValue();
}public static void main(String[] args) throws Exception {
System.out.println(removeNM(100,4));
}
有BUG 你试试 removeNM(3,1) 或者 removeNM(3,2) 得到的答案都是0 是什么意思？

Answer 7

ChDw(米) ( ) 信誉：155 
顺便说说你这个程序的思路吧 我觉得思路很好

Answer 8

To:ChDw(米) ( ) 信誉：155 
LinkedList<Integer> ll = new LinkedList<Integer>();
这一行编译不了呀，有时间，顺便解释一下！十分感谢！

Answer 9

最简单原始的算法，用数组记录谁被out了。
class WhoLeft {
public static void main(String[] args) {
int n = 6;  //总人数
int m = 3;  //报数
int k = 0;; //初始
int[] a = {8,1,1,1,1,1,1}; //初始数组，为求方便理解，从a[1]开始使用。
for(int i = 1 ;i < n ; i++) { //报n-1圈
for(int j = 0; j < m; j++) { //找报数为m的人
k++;//由于k初始为0,所以第一次报数就可以往k上加了
if(k > n) k-=n;
while(a[k] == 0) {  //遇到out的人继续往下报
k++;
if(k > n) k-=n;
}
}
a[k] = 0; //报m的人out掉
System.out.println(k + " out!");
}
k = 1;  //从第一个数组开始检查，看还有谁在。
while(a[k] == 0) { 
k++;
if(k >= n) k-=n;
}
System.out.println(k + " left");
}
}由于JAVA对数组的初始进行严格检查，所以纯粹用数组做记录的办法会显得非常笨，呵呵。。

Answer 10

http://www.graphics.net.cn/bbs/c_or_cpp/0191/279.asp

Answer 11

写得是有点小问题。我原来那个是JDK1.5的语法，方便一些而已。public static int removeNM(int n, int m) {
LinkedList ll = new LinkedList();
for(int i = 0; i < n; i++)
ll.add(new Integer(i+1));
int removed = -1;
while(ll.size() > 1) {
removed = (removed + m) % ll.size();
ll.remove(removed--);
}
return ((Integer)ll.get(0)).intValue();
}
public static void main(String[] args) {
System.out.println(removeNM(3,2));
}