使用环形单向链表解决约瑟夫环问题

超、凢脫俗 2023-07-01 06:24 25阅读 0赞

package com.zzb.datastructure.singlelist;
    
    import java.io.Serializable;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/1/18 17:38
     * @Description: 使用 环形单向链表 解决 约瑟夫环 问题
     *
     * 问题描述：
     * total 个人围成一圈，从第 index 个人起从 1 开始报数，数到 target 的那个人出队，出队的那个人的下一个人又开始从 1
     * 开始报数，数到 target 的那个人又出队，如此重复，直到圈内的人全部出队，并且求出出队顺序（或者是圈内只剩下一个人，
     * 杀人游戏，谁活到最后）
     *
     * 解题思路：
     * （1）使用不带头结点的环形单向链表解决约瑟夫环问题
     * （2）创建一个有total个节点的环形单向链表，
     *    创建方法：
     *    ①创建第一个Person类型的节点对象，使环形单链表的 head 属性变量指向该节点对象（head = person;），
     *    并使第一个Person类型的节点对象的next属性指向第一个Person类型的节点对象自身（head.next = head;），
     *    自身形成环形
     *    ②由于head属性变量不能移动变化，需要定义一个Person类型的辅助指针变量temp，表示当前节点，并完成链表添加节点的功能，temp的初始值为head（temp = head），
     *    从添加第二个节点对象开始，temp的next属性指向待添加的节点对象（temp.next = person），待添加的节点对象的next属性指向head属性变量指向的节点对象（person.next = head），
     *    形成一个环形链表，辅助变量后移（temp = temp.next），等待添加新的节点对象
     *    ③循环执行步骤②就可得到一个具有total个节点的环形单向链表
     *  （2）从第 index 个人起从 1 开始报数，则需要找出第index个人的位置，环形单向链表初始化时 head 属性变量指向的节点对象就是第一个人的位置，
     *   head属性变量在环形单向链表中需要移动 index - 1 次，移动 index - 1 次后的head属性变量指向的就是第index个人的位置了，循环解决如下
     *   for(int i = 0; i < index - 1; i++) {
     *       head = head.next;
     *       tail = tail.next;
     *   }
     *  （3）数到 target 的那个人出队,head属性变量在环形变量中移动 target - 1 次后，此时head属性变量指向的节点对象就是要被删除的节点（即出圈的人员），
     *  为了使环形单向链表在删除节点之后仍然能构成一个环形，则还需要一个Person类型的辅助指针变量tail，tail指向初始化时的环形单向链表的最后一个节点对象，
     *  （初始化时的环形单向链表的head属性变量指向环形单向链表的第一个节点对象）
     *    ①得到需要被删除的节点对象的方法如下
     *    for(int i = 0; i < target - 1; i++) {
     *        head = head.next;
     *        tail = tail.next;
     *    }
     *    ②得到初始化时的环形单向链表的最后一个位置tail的方法如下
     *    tail = head;
     *    while(true) {
     *        if(tail.next == head) {
     *            break;
     *        }
     *        tail = tail.next;
     *    }
     *  （4）根据步骤（3）得到需要被删除的节点对象后，head要指向下一个节点对象，tail要指向head，继续构成一个环形单向链表，
     *  head = head.next; tail.next = head;
     *  （5）直到tail == head 表示整个循环结束，出圈完毕，约瑟夫环问题已解决
     */
    public class JosephuForSingleLinkedListTest {
        public static void main(String[] args) {
            // total 个人围成一圈
            int total = 5;
            // 从第 index 个人起从 1 开始报数
            int index = 1;
            // 数到 target 的那个人出队
            int target = 2;
    
            // 使用环形单向链表求出约瑟夫环的出队顺序
            int[] orderOfOut = CircleSingleLinkedList.orderOfOut(total, index, target);
            System.out.println("出队顺序");
            for (int out : orderOfOut) {
                System.out.print(out + "\t");
            }
            /*出队顺序
            2	4	1	5	3*/
    
            System.out.println();
    
            // 杀人游戏，第几个人活了下来
            int whoLive = CircleSingleLinkedList.whoLive(total, index, target);
            System.out.println("第  " + whoLive + "  个人活了下来");
            /*第  3  个人活了下来*/
        }
    }
    
    // 环形单向链表类
    class CircleSingleLinkedList {
        // 不带头结点的环形单向链表，即头结点就是真实有效的节点
        private Person head = null;
    
        // 添加total个节点对象构成环形单向链表
        public void add(int total) {
            // 参数校验
            // 只有一个节点，则自身构成环形
            if(total < 1) {
                throw new RuntimeException("参数 total 取值非法！");
            }
            // 辅助变量temp，帮助构成环形单向链表
            Person temp = null;
            for(int i = 1; i <= total; i++) {
                Person person = new Person(i);
                if(i == 1) { // head属性指向第一个节点对象，并且自身构成环形
                    head = person;
                    head.setNext(head);
                    temp = head;
                } else {
                    temp.setNext(person);
                    person.setNext(head);
                    // 后移
                    temp = temp.getNext();
                }
            }
        }
    
        // 遍历环形单向链表
        public void show() {
            // 判断是否为空
            if(this.getHead() == null) {
                System.out.println("环形单向链表为空！");
            }
            Person temp = this.getHead();
            while(true) {
                System.out.println("第  " + temp.getId() + "  个人");
                // 退出循环的条件
                if(temp.getNext() == this.getHead()) {
                    break;
                }
                temp = temp.getNext();
            }
        }
    
        /**
         * 使用环形单向链表求出约瑟夫环的出队顺序
         *
         * @param total total 个人围成一圈
         * @param index 从第 index 个人起从 1 开始报数
         * @param target 数到 target 的那个人出队
         * @return 约瑟夫环的出队顺序
         */
        public static int[] orderOfOut(int total, int index, int target) {
            // 存储出队顺序的数组
            int[] orderOfOut = new int[total];
            int indexOut = 0;
            // 参数校验
            if(total <= 0) {
                throw new RuntimeException("参数 total 取值非法！");
            }
            if(index <= 0 || index > total) {
                throw new RuntimeException("参数 index 取值非法！");
            }
            if(target <= 0) {
                throw new RuntimeException("参数 target 取值非法！");
            }
            // 创建有total个节点的环形单向链表
            CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
            circleSingleLinkedList.add(total);
    
            // 得到初始化时的环形单向链表的最后一个位置tail
            Person tail = circleSingleLinkedList.head;
            while(true) {
                if(tail.getNext() == circleSingleLinkedList.head) {
                    break;
                }
                tail = tail.getNext();
            }
    
            // 从第 index 个人起从 1 开始报数
            // 获取开始报数的位置节点对象head 与 最后位置节点对象tail
            for(int i = 0; i < index - 1; i++) {
                circleSingleLinkedList.head = circleSingleLinkedList.getHead().getNext();
                tail = tail.getNext();
            }
    
            // 数到 target 的节点对象被从环形单向链表中删除，完成出圈
            while(true) {
                // 环形单向链表中只剩下一个节点，退出循环
                if(tail == circleSingleLinkedList.head) {
                    break;
                }
                // head属性变量移动 target - 1 次后，head属性变量指向的节点对象就是要出圈的节点对象
                for(int j = 0; j < target - 1; j++) {
                    circleSingleLinkedList.head = circleSingleLinkedList.getHead().getNext();
                    tail = tail.getNext();
                }
                // 存储出圈节点
                orderOfOut[indexOut] = circleSingleLinkedList.head.getId();
                indexOut++;
                // 剩下的节点对象继续构成环形单向链表
                circleSingleLinkedList.head = circleSingleLinkedList.getHead().getNext();
                tail.setNext(circleSingleLinkedList.getHead());
            }
            // 存储最后一个节点对象
            orderOfOut[indexOut] = tail.getId();
            // 返回出圈顺序
            return orderOfOut;
        }
    
        /**
         * 杀人游戏，第几个人活了下来
         *
         * @param total total 个人围成一圈
         * @param index 从第 index 个人起从 1 开始报数
         * @param target 数到 target 的那个人出队
         * @return 第几个人活了下来
         */
        public static int whoLive(int total, int index, int target) {
            // 参数校验
            if(total <= 0) {
                throw new RuntimeException("参数 total 取值非法！");
            }
            if(index <= 0 || index > total) {
                throw new RuntimeException("参数 index 取值非法！");
            }
            if(target <= 0) {
                throw new RuntimeException("参数 target 取值非法！");
            }
            // 创建有total个节点的环形单向链表
            CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
            circleSingleLinkedList.add(total);
    
            // 得到初始化时的环形单向链表的最后一个位置tail
            Person tail = circleSingleLinkedList.head;
            while(true) {
                if(tail.getNext() == circleSingleLinkedList.head) {
                    break;
                }
                tail = tail.getNext();
            }
    
            // 从第 index 个人起从 1 开始报数
            // 获取开始报数的位置节点对象head 与 最后位置节点对象tail
            for(int i = 0; i < index - 1; i++) {
                circleSingleLinkedList.head = circleSingleLinkedList.getHead().getNext();
                tail = tail.getNext();
            }
    
            // 数到 target 的节点对象被从环形单向链表中删除，完成出圈
            while(true) {
                // 环形单向链表中只剩下一个节点，退出循环
                if(tail == circleSingleLinkedList.head) {
                    break;
                }
                // head属性变量移动 target - 1 次后，head属性变量指向的节点对象就是要出圈的节点对象
                for(int j = 0; j < target - 1; j++) {
                    circleSingleLinkedList.head = circleSingleLinkedList.getHead().getNext();
                    tail = tail.getNext();
                }
                // 剩下的节点对象继续构成环形单向链表
                circleSingleLinkedList.head = circleSingleLinkedList.getHead().getNext();
                tail.setNext(circleSingleLinkedList.getHead());
            }
            // 返回幸存者
            return tail.getId();
        }
    
        public Person getHead() {
            return head;
        }
    
        public void setHead(Person head) {
            this.head = head;
        }
    }
    
    // 节点类
    class Person implements Serializable {
        private static final long serialVersionUID = 6478673867919613756L;
        private int id;
        private Person next;
    
        public Person(int id) {
            this.id = id;
        }
    
        public int getId() {
            return id;
        }
    
        public void setId(int id) {
            this.id = id;
        }
    
        public Person getNext() {
            return next;
        }
    
        public void setNext(Person next) {
            this.next = next;
        }
    
        @Override
        public String toString() {
            return "Person{" +
                    "id=" + id +
                    ", next=" + next +
                    '}';
        }
    }