约瑟夫环-Java兑现
约瑟夫环--Java实现
import java.util.HashMap; import java.util.Map; /** * 约瑟夫环--Java实现<br> * 有N个同学围成一圈,从1开始依次编号,从第P个开始报数,报到第T个时,该同学出列,<br> * 然后从下一个同学开始报数,仍是报到T个出列,如此重复下去,<br> * 直到所有的同学都出列( 总人数不足T个时将循环报数),求同学出列的顺序。<br> * * @author Administrator * */ public class Joseph { public Map<Integer, Person> members = new HashMap<Integer, Person>(); public String getJoseph(int n, int p, int t) { StringBuffer str = new StringBuffer(); // 构造环 for (int i = 1; i <= n; i++) { Person pn = new Person(i); if (i == 1) { pn.setBack(n); } else if (i == n) { pn.setNext(1); } members.put(i, pn); } // 当前同学 Person current = members.get(p); // 开始报数 while (n >= 1) { for (int i = 1; i <= t - 1; i++) { current = members.get(current.getNext()); if (i == t - 1) { // 切换前后关系 int back = current.getBack(); int next = current.getNext(); Person pastPerson = members.get(back); pastPerson.setNext(next); Person nextPerson = members.get(next); nextPerson.setBack(back); // 移除对象,并记录 members.remove(current.getPosition()); str.append(current.getPosition()); if (n != 1) { str.append(","); } // 重新设置下一位为当前对象 current = null; current = nextPerson; } } n--; } return str.toString(); } } public class Person { private int back;// 上一位的位置 private int position;// 我的位置 private int next;// 下一位的位置 public Person() { } public Person(int i) { back = i - 1; position = i; next = i + 1; } public int getBack() { return back; } public void setBack(int past) { this.back = past; } public int getPosition() { return position; } public void setPosition(int position) { this.position = position; } public int getNext() { return next; } public void setNext(int next) { this.next = next; } } @Test public class JosephTest extends BaseTest{ Joseph joseph = new Joseph(); public void testCount(){ String str= joseph.getJoseph(5, 2, 3); want.string(str).isEqualTo("4,2,1,3,5"); } }