约瑟夫环实现

约瑟夫环

约瑟夫环小游戏：把小朋友按照编号1，2，3，…，n围成一圈，指定编号为k的小朋友从1开始报数，数到m的小朋友出队。接着他的下一位小朋友再次从1报数，以此类推，直到所有人都出队，产生了一个出队编号的序列。

1. 代码实现

public class Josepfu {
    
    public static void main(String[] args) {
        CircleLinkList list = new CircleLinkList();
        list.addBoy(10);
        list.show();
        list.countBoy(2, 4, 10);
    }
    
    /**
     * 使用环形链表模拟约瑟夫环
     */
    private static class CircleLinkList {
        //创建头结点
        private Boy first;
        
        /**
         * 添加节点形成链表
         * @param nums 小朋友的人数
         */
        void addBoys(int nums) {
            if (nums < 1) {
                System.out.println("nums的值不正确");
                return;
            }
            
            //添加辅助节点
            Boy current = null;
            for (int i=1;i<=nums;i++) {
                Boy boy = new Boy(i);
                if (i == 1) {
                    //第一个小朋友形成自环
                    first = boy;
                    first.next = first;
                    current = first;
                } else {
                    current.next = boy;
                    boy.next = first;
                    current = current.next;
                }
            }
        }
        
        /**
         * 报数
         * @param startNo 从第几个小孩报数
         * @param countNum 表示数到几号出队
         * @param nums 圈中小孩的数目
         */
        void countBoy(int startNo, int countNum, int nums){
            if (first == null || startNo < 1 || startNo > countNum) {
                System.out.println("输入参数有误，重新输入");
                return;
            }
            
            //使用辅助节点指向链表末尾
			Boy helper = first;
            while(helper.next != first) {
                helper = helper.next;
            }
            
            //小朋友报数前把first和helper移动到开始报数的小朋友的位置
            for (int i=0;i<startNo-1;i++) {
                first = first.next;
                helper = helper.next;
            }
            
            //当小朋友报数时，移动m-1次后出圈
            while (true) {
                if (first == helper) {
                    break;
                }
                
                for (int j=0;j<countNum-1;j++) {
                    first = first.next;
                    helper = helper.next;
                }
                
                //first指向要出圈的节点
                System.out.printf("小朋友%d出圈\n", first.no);
                first = first.next;
                helper.next = first;
            }
            System.out.println("最后留在圈中的小朋友编号是:" + first.no);
        }
        
        /**
         * 显示链表中的小朋友
         */
        void show() {
            if (first == null) {
                System.out.println("链表为空");
                return;
            }
            
            Boy current = first;
            while(true){
                System.out.printf("小朋友的编号%d\n", current.no);
                if(current.next == first){
                    break;
                }
                current = current.next;
            }
        }               
    }
    
    /**
     * 小朋友
     */
    private static class Boy {
        int no;
        Boy next;
        
        Boy(int no) {
            this.no = no;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

2. 以10个小朋友，从第2号小朋友开始从1报数，数到4出圈为例，输出结果如下：

小朋友的编号8
小朋友的编号9
小朋友的编号10
小朋友5出圈
小朋友9出圈
小朋友3出圈
小朋友8出圈
小朋友4出圈
小朋友1出圈
小朋友10出圈
小朋友2出圈
小朋友7出圈
最后留在圈中的小朋友编号是:6