Question

求解约瑟夫环问题(Java)

约瑟夫环问题：古代某法官要判决N个犯人的死刑，他有一条荒唐的法律，让犯人站成一个圆圈，从第S个人开始数起，每数到第D个犯人，就拉出来处决，然后再数D个，数到的人再处决……直到剩下的最后一个可赦免。使用数组存储每个人的编号，数组下标按环形方式递增。对于N、S、D的任意一组值，显示出环者次序，求出正确的解。下面是老师给出的方法,看不懂他说什么,希望能有高手来解决啊!!!!!!在线等答案啊!!!!
方法一：可以用数组来存放N个数，相当于N个数排成的圈；用整型变量指向当前数到的数组元素，
相当于人的手指；划掉一个数的操作，就用将一个数组元素置0的方法来实现。人工数的时候，要跳过已
经被划掉的数，那么程序执行的时候，就要跳过为0的数组元素。注意，当指向当前数到的数组元素的整
型变量指向数组中最后一个元素（下标为N-1）时,再数下一个，则该整型变量要指回到数组的第一个元
素（下标为0），这样才像一个圈。
方法二：采用单向循环链表完成此题。Java API提供了丰富的集合类型，封装了各种数据结构(链表、散列、树、图等)，链表的建立和相关操作可使用java.util包中提供的相关集合类。

Answer 1

package 约瑟夫环;

import java.util.LinkedList;
import java.util.List;

/**
* 约瑟夫环问题的一种描述是：编号为1.2.3…….n的n个人按顺时针方向围坐一圈 ，每人手持一个密码（正整数），
* 开始任意选一个整数作为报数上限值，从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，
* 将他的密码作为新的m值，从他顺时针下一个人开始重新从1开始报数，
* 如此下去直到所有的人全部都出列为止。试设计程序实现，按照出列的顺序打印各人的编号。
* @author Administrator
*
*/
public class Question2 {
class person {
int password;
int number;
int state = 1;

public person(int password, int number) {
this.password = password;
this.number = number;
}
public person(int number){
this.number = number;
}
}

public int ListLength(List<person> list) {
int count = 0;
if (list != null) {
for (person p : list) {
if (p.state != 0) {
count++;
}
}
}
return count;
}

public void cacle() {
// 初始化数据
List<person> list = new LinkedList<person>();
list.add(new person(3,1));
list.add(new person(1,2));
list.add(new person(7,3));
list.add(new person(2,4));
list.add(new person(4,5));
list.add(new person(8,6));
list.add(new person(4,7));

int position = -1;//初始位置
int m = 20; //第一次报多少的人出来
int count = 0;//已经报了多少人
while (ListLength(list) != 0) {

position = (position + 1) % list.size();// 位置定位

if (((person) list.get(position)).state != 0) {
count++;
}
if (count == m) {
person p = list.get(position);
System.out.print(p.number+" ");
p.state = 0;
m = p.password;
list.set(position, p);
count = 0;
}
}

}
public static void main(String[] args) {
Question2 q= new Question2();
q.cacle();
}

}

跟这差不多的。

Answer 2

其实很简单的方法是 人死了，经过一个循环，后面的数都向前移，这样最简单。

Answer 3

要答案还是想法?