问题:设编号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实现。但是有那么一点头绪,总无法全部实现。
有会的,希望能帮下!谢谢了!
------解决方案--------------------
- Java code
public class Test { /** * 初始化编号和密码表 * **/ 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是他执有的密码.
------解决方案--------------------
- Java code
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; } }