07 - 单向环形链表应用场景 —— Josephu问题

1. Josephu 问题

设编号为1,2,… n的n个人围坐一圈,约定编号为 k(1<=k<=n)的人从1开始报数,数到 m 的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列

2. 解决思路

07 - 单向环形链表应用场景 —— Josephu问题

  • 【简述】用一个不带头结点的循环链表来处理Josephu问题, 先构成一个有n个结点的单循环链表,然后由 k 结点 起从1开始计数,计到 m 时,对应结点从链表中删除,然后再从 被删除结点的下一个结点 又从1开始计数,直到最后一个结点从链表中删除算法结束
  • 变量
    • first,指向 编号为k 的结点
    • helper,指向 环形链表first结点 的前一个结点
  • 出圈
    ∵ 报数从1开始,自己本身也算1个数,1到m之间共有 m-1 个空隙
    ∴ first 要移动 m-1 次,方可到达 [数到m的那个人],helper结点也移动 m-1 次,它的作用是辅助first 让 第m个人 出圈
    • first = first.next;
    • helper.next = first;
    • 原来 first 指向的结点因没有任何引用指向它而被垃圾回收器回收

3. 代码实现

直接将该方法加入06的代码实现中即可

    /**
     * 根据用户的输入, 计算出小孩出圈的顺序
     * @param startNo 从编号为startNo的boy开始数数
     * @param countNum 数几下
     * @param nums 最初有多少boy在圈中
     */
    public void countBoy(int startNo, int countNum, int nums) {
        // 0. 数据校验
        if(first == null || startNo < 1 || startNo > nums || countNum < 1) {
            System.out.println("输入数据有误");
            return;
        }
        /*
         * 1. 将first, helper移动到startNo所确定的位置
         *  1.1 helper 应指向 first 的前一个结点
         *  1.2 first 应指向编号为 startNo 的结点, 需移动 startNo-1 次
         *  1.3 helper 也得跟着动
         */
        Boy helper = first;
        while(helper.next != first)
            helper = helper.next;
        for(int i = 0; i < startNo - 1; i++) {
            first = first.next;
            helper = helper.next;
        }
        
        /* 如果 startNo = 1, 下面这种方法就不对了
        for(int i = 0; i < startNo - 2; i++)
            helper = helper.next;
        // 移动 startNo - 2 + 1 次
        first = helper.next;
        */
        
        // 2. 开始数数, 让结点逐个出圈
        while(helper != first) { // 说明圈里只有1个结点了
            // 2.1 让first, helper 同时移动 countNum-1 次
            for(int i = 0; i<countNum-1; i++) {
                first = first.next;
                helper = helper.next;
            }
            // 此时, first指向的结点即为 要出圈的结点
            System.out.println("出圈! " + first);
            first = first.next;
            helper.next = first;
            // 出圈结点 此时因没有被任何引用所引用, 而被垃圾回收
        }
        System.out.println("last Node: " + first);
    }
    
上一篇:一、Josephu约瑟夫问题


下一篇:高级定位技巧