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

simonzu521 2006-03-30 12:08:25

非常感谢大家的解答！！

...全文

3231 20 打赏收藏转发到动态举报

写回复

用AI写文章

20 条回复

切换为时间正序

请发表友善的回复…

发表回复

yanxiazhiqiu 2006-04-03

打赏
举报

so easy ...

ChDw 2006-04-03

打赏
举报

写得是有点小问题。我原来那个是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));
}

perfervid 2006-04-02

打赏
举报

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

benewu 2006-04-02

打赏
举报

最简单原始的算法，用数组记录谁被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对数组的初始进行严格检查，所以纯粹用数组做记录的办法会显得非常笨，呵呵。。

simonzu521 2006-04-01

打赏
举报

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

zaghost 2006-04-01

打赏
举报

约瑟夫问题数据结构的经典例题

sophitia212 2006-03-31

打赏
举报

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

sophitia212 2006-03-31

打赏
举报

好像 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 是什么意思？

wfhlxl 2006-03-31

打赏
举报

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

ChDw 2006-03-31

打赏
举报

几行代码就足够了

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

hemiao_1993 2006-03-31

打赏
举报

约瑟夫问题嘛, 从学C语言的时候就开始做这个, 老谭那本Ｃ语言上就有例子，改成ＪＡＶＡ的不难吧．

chg2008 2006-03-31

打赏
举报

北京大学毕业的这个题不会做？

十分钟年华老去 2006-03-31

打赏
举报

循环链表就可以了

simonzu521 2006-03-31

打赏
举报

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

simonzu521 2006-03-31

打赏
举报

非常感谢wizardblue(不死鱼)！

shendiaoke 2006-03-30

打赏
举报

你是哪个学校的？

记得我在学校的时候，有个老师就是出同样的题目！

wizardblue 2006-03-30

打赏
举报

import junit.framework.TestCase;

/**
*
* @author protozz
*
*/

public class JosephusTest extends TestCase {
public void testGetLast() {
Josephus case1 = new Josephus(41, 3);
assertEquals(case1.getLast(), 31);
}

}

wizardblue 2006-03-30

打赏
举报

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