目录

约瑟夫问题

介绍

约瑟夫问题:N个人围成一圈,从约定编号为K的人开始报数,第M个将被杀掉,求最后存活的人编号。比如有5个人,从第一个开始报数,每隔2个就要杀死一人,则出局顺序为2->4->1->5->3,如下 https://gitee.com/lienhui68/picStore/raw/master/null/20200616204536.png

单链表实现

  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
package com.eh.ftd.dsa.ds.impl;


/**
 * 约瑟夫环
 *
 * @author David Li
 * @create 2020/06/16 18:40
 */
public class JosephBySingleLinkedList {
    /**
     * 指向约瑟夫环报数的开始元素
     */
    private Node first;
    /**
     * 指向约瑟夫环的最后一个元素(last.next=first)
     */
    private Node last;


    class Node {
        private int num;
        private Node next;

        public Node(int num) {
            this.num = num;
        }
    }

    /**
     * 初始化约瑟夫环
     *
     * @param n 总数
     * @return
     */
    public JosephBySingleLinkedList(int n) {
        if (n < 2) {
            throw new RuntimeException("输入有误!");
        }

        // 构建个数为n的单向循环链表
        for (int i = 1; i <= n; i++) {
            Node node = new Node(i);
            if (i == 1) {
                first = node;
                last = node;
                node.next = node;
                continue;
            }
            last.next = node;
            node.next = first;
            last = node;
        }
    }

    /**
     * 执行约瑟夫环
     *
     * @param m 每隔多少位
     * @param k 从第k个开始
     */
    public void run(int m, int k) {
        // 由于从第k个开始,first和last要移动k-1位
        Node temp = last;
        for (int i = 0; i < k - 1; i++) {
            temp = temp.next;
        }
        last = temp;
        first = temp.next;
        while (true) {
            // 定位到要删除元素,first指向该元素
            for (int i = 0; i < m - 1; i++) {
                last = last.next;
                first = first.next;
            }
            // 输出元素序号
            System.out.println(first.num);
            // 删除元素
            first = first.next;
            last.next = first;
            // 跳出条件
            if (first == last) {
                System.out.println("幸存者: " + first.num);
                break;
            }
        }

    }

    /**
     * 用来展示数据,仅供测试用
     */
    public void display() {
        Node temp = first;
        while (true) {
            System.out.println(temp.num);
            if (temp == last) {
                return;
            }
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        JosephBySingleLinkedList list = new JosephBySingleLinkedList(5);
        list.run(2, 1);
    }
}

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200616203143.png

我们来计算下时间复杂度,由于有n个人,要删除n-1个人需要遍历n-1次, 又每删除一个人都要执行m-1次循环,顾时间复杂度为(n-1) * (m-1),也就是O(nm)。当n和m很大时,时间复杂度会非常大。

利用数学解法

在优化前先来查找其中有没有数学规律,仍以上面这个例子为例(下标设置从0开始,最后+k即可),n=5,m=2,k=1,每次移除一个人,将下一个人的编号映射为0,后面的一次递增(注意因为是循环,前面的人在经过删除后要放在后面) 我们使用队列list1表示报数后的编号队列,使用队列list2表示映射后的编号队列

  1. 第一轮,开始前剩余5个人(0,1,2,3,4) list1:2,3,4,0 list2:0,1,2,3

此时list2和list1的关系为(new+m) % n,其中new代表映射后的新编号

  1. 第二轮, 开始前剩余4个人(0,1,2,3) list1:2,3,0 list2:0,1,2

此时list2和list1的关系为(new+m) % (n-1)

  1. 第三轮,开始前剩余3个人(0,1,2) list1:2,0 list2:0,1

此时list2和list1的关系为(new+m) % (n-2)

  1. 第四轮, 开始前剩余2个人(0,1) list1:0 list2:0

此时list2和list1的关系为(new+m) % (n-3)

我们设第一轮幸存值编号为x1,第二轮x2,依次类推第4轮编号x4。那么有以下方程式 x4 = (0 + m) % (n - 3) = (0 + 2) % 2 = 0 x3 = (x4 + m) % (n - 2) = (0 + 2) % 3= 2 x2 = (x3 + m) % (n - 1) = (2 + 2) % 4 = 0 x1 = (x2 + m) % (n - 0) = (0 + 2) % 5 = 2 因为我们的编号是从k开始,所以最终结果为x1+k, 如果是0则统一样式不需要+k

java实现

 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
package com.eh.ftd.dsa.ds.impl;

/**
 * todo
 *
 * @author David Li
 * @create 2020/06/16 22:14
 */
public class JosephByMath {

    /**
     * 计算幸存值,使用数学方法
     *
     * @param k 从第几个编号开始
     * @param m 每个多少个人
     * @param n 总人数
     * @return
     */
    public static int calculateTheSurvivor(int k, int m, int n) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return (x + k) % n;
    }

    public static void main(String[] args) {
        System.out.println("=======通过单向链表求解约瑟夫问题=======");
        JosephBySingleLinkedList linkedList = new JosephBySingleLinkedList(200);
        linkedList.run(18, 10);
        System.out.println("=======通过数学方法求解约瑟夫问题=======");  
        System.out.println(calculateTheSurvivor(10, 18, 200));
    }

}

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200616231944.png

优化后的算法时间复杂度为O(n),效率提升了m倍。