问题:设编号1,2,...,n(n>0)的n个人按顺时针方向围坐一圈,每个人持有一个正整数密码。开始时,任意给出一个报数上限值m,从第一个人开始顺时针方向自1起顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人起重新自1起顺序报数;如此下去,直到所有人全部出列为止。要求设计一个程序模拟此过程,并给出出列人的编号序列。
基本要求:
初始报数上限值m和测试数据在程序中确定;
测试数据:
n=7,七个人的密码依次为3,1,7,2,4,8,4.
初始报数上限值m=20.这是我们C语言数据结构书上的一个问题,书上是用带头结点的单循环链表来用C语言写的。
我C语言学的不是很好,然后时间长了,遗忘比较厉害。然后就想用JAVA实现。但是有那么一点头绪,总无法全部实现。
有会的,希望能帮下!谢谢了!
基本要求:
初始报数上限值m和测试数据在程序中确定;
测试数据:
n=7,七个人的密码依次为3,1,7,2,4,8,4.
初始报数上限值m=20.这是我们C语言数据结构书上的一个问题,书上是用带头结点的单循环链表来用C语言写的。
我C语言学的不是很好,然后时间长了,遗忘比较厉害。然后就想用JAVA实现。但是有那么一点头绪,总无法全部实现。
有会的,希望能帮下!谢谢了!
/**
* 初始化编号和密码表
* **/
private static final Map<Integer, Integer> map = new TreeMap<Integer, Integer>(); static {
map.put(1, 3);
map.put(2, 1);
map.put(3, 7);
map.put(4, 2);
map.put(5, 4);
map.put(6, 8);
map.put(7, 4);
} /**
* 初始化报数列表
* **/
public static void init(List<Integer> list, int n) {
for (int i = 1; i <= 7; i++) {
list.add(i);
}
} /**
* 报数函数,所有人出列,就结束
* **/
public static void report(List<Integer> list, Map<Integer, Integer> map,
int cipher, int x) {
int size = list.size();
if (size > 0) {
Integer outIndex = 0;
if (x + cipher < size) {
outIndex = x + cipher - 1;
} else {
cipher = cipher - (size - x);
outIndex = (cipher % size == 0 ? size : cipher % size) - 1;
}
Integer out = list.get(outIndex);
cipher = map.get(out);
System.out.println("outIndex:" + outIndex + " out:" + out
+ " cipher:" + cipher);
list.remove(out);
x = outIndex;
report(list, map, cipher, outIndex);
}
} public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
init(list, 7);
report(list, Test.map, 20, 0);
}
}
outIndex:5 out:6 cipher:8
outIndex:0 out:1 cipher:3
outIndex:2 out:4 cipher:2
outIndex:3 out:7 cipher:4
outIndex:0 out:2 cipher:1
outIndex:0 out:3 cipher:7
outIndex:0 out:5 cipher:4
out代表出队人的号码,cipher是他执有的密码.
public class TestJosephus { /**
* @param args
*/
public static void main(String[] args) {
Person person1 = new Person(1, 3, null);
Person person7 = new Person(7, 4, person1);
Person person6 = new Person(6, 8, person7);
Person person5 = new Person(5, 4, person6);
Person person4 = new Person(4, 2, person5);
Person person3 = new Person(3, 7, person4);
Person person2 = new Person(2, 1, person3);
person1.setNextPerson(person2);
new TestJosephus().josephus(person1, 20); }
public void josephus(Person person, int m) {
Person pPerson = person;
//只有一个对象则不用遍历,直接输出来
if (person.getNextPerson() == person) {
System.out.print(" " + person.getNum());
} else {
//遍历得到person的前一个对象
while (person != pPerson.getNextPerson())
pPerson = pPerson.getNextPerson();
//当前对象即要遍历对象之一,所以遍历数减一
for(int i=1;i<m;i++){
pPerson = person;
person = person.getNextPerson();
}
System.out.print(" " + person.getNum());
pPerson.setNextPerson(person.getNextPerson());
person.setNextPerson(null);
josephus(pPerson.getNextPerson(), person.getPassword()); }
}
}
public class Person {
private Person nextPerson;
private int num;
private int password;
public Person(int num, int password, Person nextPerson) {
super();
this.num = num;
this.password = password;
this.nextPerson = nextPerson;
}
public Person getNextPerson() {
return nextPerson;
}
public int getNum() {
return num;
}
public int getPassword() {
return password;
}
public void setNextPerson(Person nextPerson) {
this.nextPerson = nextPerson;
}
public void setNum(int num) {
this.num = num;
}
public void setPassword(int password) {
this.password = password;
}
}