- 1
- /*
- 2 * 作者:zhaop
- 3 * 功能:约瑟夫环
- 4 *
- 5 */
- 6 public class Joseph {
- 7 public static void main(String[] args) {
- 8 // TODO Auto-generated method stub
- 9 CyLink link = new CyLink();
- 10 link.setLen(5);
- 11 link.setK(2);
- 12 link.setM(2);
- 13 link.createLink();
- 14 link.show();
- 15 link.play();
- 16
- }
- 17
- }
- 18 class Child 19 {
- 20 int no; // 人的编号
- 21 Child nextChild = null; // 指向下一个
- 22 public Child(int no) 23 {
- 24 this.no = no;
- 25
- }
- 26
- }
- 27 class CyLink 28 {
- 29 Child firstChild = null; // 头指针
- 30 Child currentChild = null; // 当前指针
- 31 int len = 0; // 总人数
- 32 int k = 0; // 从第k个人开始数数
- 33 int m = 0; // 数m个数
- 34 public void setLen(int len) 35 {
- 36 this.len = len;
- 37
- }
- 38 // 设置k
- 39 public void setK(int k) 40 {
- 41 this.k = k;
- 42
- }
- 43 public void setM(int m) 44 {
- 45 this.m = m;
- 46
- }
- 47 //初始化环形链表
- 48 public void createLink() 49 {
- 50
- for (int i = 1; i <= len; i++) 51 {
- 52 Child ch = new Child(i);
- 53
- if (i == 1) // 第一个时,修改头指针
- 54 {
- 55 firstChild = currentChild = ch;
- 56
- }
- 57
- else 58 {
- 59
- if (i == len) // 最后一人的 下一个指针指向 第一个人
- 60 {
- 61 currentChild.nextChild = ch;
- 62 ch.nextChild = firstChild;
- 63 currentChild = ch;
- 64
- }
- 65
- else 66 { // 对其他的人来说,让新创建的对象 放在 当前对象的下一个位置,并让当前对象指向新创建的对象
- 67 currentChild.nextChild = ch;
- 68 currentChild = ch;
- 69
- }
- 70
- }
- 71
- }
- 72
- }
- 73 //开始游戏
- 74 public void play() 75 {
- 76 Child temp = firstChild;
- 77 //1.先开始找到数数的人
- 78
- for (int i = 1; i < k; i++) 79 {
- 80 temp = temp.nextChild;
- 81
- }
- 82 //2.数m下
- 83
- while (len != 1) 84 {
- 85 //为了便于修改指针,可以数 m - 1下
- 86
- for (int i = 1; i < m - 1; i++) 87 {
- 88 temp = temp.nextChild;
- 89
- }
- 90 91 //3.将数到m的小孩弄出圈去
- 92 // 此时temp是数m-1后的结果,所以要修改temp的下一个指针的
- 93 temp.nextChild = temp.nextChild.nextChild;
- 94 temp = temp.nextChild;
- 95 len--;
- 96
- }
- 97 System.out.println("最后一个小孩是:" + temp.no);
- 98
- }
- 99 // 打印该环形链表
- 100 public void show() 101 {
- 102 Child temp = firstChild;
- 103 do {
- 104 System.out.println(temp.no);
- 105 temp = temp.nextChild;
- 106
- } while ( temp != firstChild );
- 107
- }
- 108
- }
来源: