约瑟夫环

痛定思痛。 2022-11-27 06:54 169阅读 0赞

# 约瑟夫环 #

## 1、参考资料 ##

https://blog.csdn.net/shuaicihai/article/details/54847433

## 2、使用数组 ##

### 2.1、代码思路 ###

先使用一个数组保存每个人的编号，编号从 1~n，如果此人的编号不为零，则表示此人没有蹲下；如果此人的编号为零，则表示此人已蹲下（不要去打扰他了）

### 2.2、代码实现 ###

*  代码：数组实现

/**
     * @ClassName JosephuDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/8/12 20:05
     * @Version 1.0
     */
    public class JosephuDemo {
        
    
        public static void main(String[] args) {
        
            josephu(5, 2, 3);
        }
    
        /**
         * 数组解决约瑟夫问题
         *
         * @param personCount 总人数
         * @param startNumber 从第 startNumber 个人开始数（索引从 1 开始）
         * @param number      每次数 number 个人，然后让此人蹲下
         */
        public static void josephu(int personCount, int startNumber, int number) {
        
            // 把人放到数组中
            int[] persons = new int[personCount];
            for (int i = 1; i <= personCount; i++) {
        
                persons[i] = i;
            }
    
            // 当前正在遍历哪个人？（指针）
            int curIndex = startNumber - 1;
            // 蹲下的人数
            int downCount = 0;
            // 当前轮轮询的人数
            int cycleCount = 0;
    
            // 全部人蹲下之后，才能结束
            while (downCount < personCount) {
        
    
                // 如果此人已经蹲下了，则跳过
                if (persons[curIndex % persons.length] == 0) {
        
                    curIndex++;
                } else {
        
                    // 否则此人没有蹲下，cycleCount++ 表示轮训次数加 1
                    cycleCount++;
    
                    // 如果已经数了 number 次，则需要蹲下
                    if (cycleCount == number) {
        
                        // 将此人编号输出后，让此人蹲下
                        System.out.println(persons[curIndex % persons.length]);
                        persons[curIndex % persons.length] = 0;
                        // 轮询计数器置零
                        cycleCount = 0;
                        // 蹲下人数加 1
                        downCount++;
                    }
    
                    // 遍历下一个人
                    curIndex++;
                }
    
            }
    
        }
    }

*  程序运行结果

4
    2
    1
    3
    5

## 3、使用队列 ##

### 3.1、代码思路 ###

先按照初始顺序将小可爱们都保存在队列中，然后不停地让队头的小可爱出队

1.  如果计数器 cycleCount 达到预期值，则将计数器重置（这个小可爱就真正地出队了，再也回不来了）
2.  否则，将出队的小可爱再次放回到队尾，继续参与游戏

### 3.2、代码实现 ###

*  代码

/**
     * @ClassName JosephuDemo
     * @Description TODO
     * @Author Heygo
     * @Date 2020/8/12 20:05
     * @Version 1.0
     */
    public class JosephuDemo {
        
    
        public static void main(String[] args) {
        
            josephu(5, 2, 3);
        }
    
        /**
         * 链表解决约瑟夫问题
         *
         * @param personCount 总人数
         * @param startNumber 从第 startNumber 个人开始数（索引从 1 开始）
         * @param number      每次数 number 个人，然后让此人蹲下
         */
        public static void josephu(int personCount, int startNumber, int number) {
        
    
            // 小可爱们组成的队列
            Queue<Integer> cutes = new LinkedList<>();
    
            // 将小可爱们放入队列中
            for (int i = startNumber; i <= personCount; i++) {
        
                cutes.add(i);
            }
            for (int i = 1; i < startNumber; i++) {
        
                cutes.add(i);
            }
    
            // 记录本次轮询了多少人
            int cycleCount = 0;
    
            // 有一个小可爱蹲下，则队列少一个人
            while (cutes.isEmpty() == false) {
        
    
                // 将队头的小可爱出队
                Integer cute = cutes.remove();
    
                // 如果轮询次数等于 number，让这个小可爱出队
                if(++cycleCount == number){
        
                    System.out.println(cute);
                    cycleCount = 0;
                }else{
        
                    // 否则将小可爱加到队尾
                    cutes.add(cute);
                }
            }
        }
    
    }

*  程序运行结果

5
    1
    4
    2
    7
    3
    6

## 4、使用链表 ##

### 4.1、代码思路 ###

以后有时间再做啦~~~

### 4.2、代码实现 ###