约瑟夫环问题（蛮力，数学解法）

问题

约瑟夫问题是一个很著名的杀人问题：

约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
例如：只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。

  • 首先A开始报数，他报1。侥幸逃过一劫。
  • 然后轮到B报数，他报2。非常惨，他被杀了
  • C接着从1开始报数
  • 接着轮到A报数，他报2。也被杀死了。
  • 最终胜利者是C

可怜，真可怜，数学家真是心狠手辣（雾）

输入

这里跟算法第四版的输入有点不一样，这里我们有三个参数：

  • 总人数
  • 剩余人数
  • 间隔人数

输出

最后剩余人的编号合集，由逗号分隔

暴力解法

说明

顾名思义，求，就是嗯求，靠着大量循环做出来的结果。

循环删除直到剩余人数到需要的人数，每一次循环都删除间隔人数后的那个，最后剩下来的就是活着的人。

image-20200721161113695
image-20200721161113695

实现

这里有两个实现，可以使用双向队列实现，也可以用循环链表实现。

双向队列实现

代码
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
/**
 * 双向队列暴力求法
 * 就是嗯求
 * */
fun queueForceSolution(): String {
    val sb = StringBuilder()
    // 初始化队列
    val deque = Deque<Int>().apply {
        for (i in 1..totalPeople)
            pushRight(i)
    }

    // 没有到剩余人数就继续循环
    while (deque.size != remainPeople) {
        // 跳过间隔人数
        // 这里的跳过为了不影响后面的循环做的是左出右进的方案
        for (q in 1 until intervalPeople)
            deque.pushRight(deque.popLeft())
        deque.popLeft()
    }

    return sb.apply {
        deque.forEachIndexed { index, i ->
            append("${i}号")
            if (index != deque.size - 1) append(", ")
        }
    }.toString()
}

双向队列实现请看算法(第四版)笔记(4)—Deque,Buffer,四数之和,三数之和

分析

时间复杂度：

这里的双向队列采用的是链表实现，所以进出队列的时间复杂度都是$\mathcal{O}(1)$，所以仅用计算循环时间复杂度。

设总人数 $T$，间隔人数 $I$，剩余人数 $R$。
$$
\mathcal{O}((T-R)*I)
$$
空间复杂度：

存在中间数据结构双向队列，非常数级空间复杂度。
$$
\mathcal{O}(N)
$$

循环链表实现

循环链表循环链表，就是说头尾相连的链表(就像是人体蜈蚣那样)

所以首先来实现循环链表：

循环链表实现
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package ds

/**
 * 循环链表
 * 此类仅用于约瑟夫环问题 所以api设计很简单
 * */
class CircularLinkedList<T> : MutableIterable<T> {
    private var _size = 0
    private var first: Node<T>? = null
    private var last: Node<T>? = null

    val size
        get() = _size

    fun clear() {
        var n = first
        while (n != null) {
            val next = n.next
            // 快速gc
            n.item = null
            n.next = null
            n.prev = null
            n = next
        }
        first = null
        last = null
        _size = 0
    }

    fun isEmpty(): Boolean = _size == 0

    fun add(element: T): Boolean {
        linkedLast(element)
        return true
    }

    override fun iterator(): MutableIterator<T> {
        return IteratorImpl(0)
    }

    private fun getNode(index: Int): Node<T> {
        val reIndex = index % _size
        return if (reIndex < (_size shr 1)) {
            var node = first
            for (i in 0 until index) {
                node = node?.next
            }
            node!!
        } else {
            var node = last
            for (i in _size - 2 downTo index) {
                node = node?.prev
            }
            node!!
        }
    }

    /**
     * 连接尾节点
     * */
    private fun linkedLast(item: T) {
        val l = last
        val nNode = Node(item, l, null)
        last = nNode

        if (l == null) {
            first = last
        } else {
            l.next = nNode
        }
        first!!.prev = nNode
        nNode.next = first
        _size++
    }

    /**
     * 解连接
     * */
    private fun unlink(node: Node<T>): T {
        val npre = node.prev
        val nnext = node.next
        val nitem = node.item

        if (npre == last && nnext == first) {
            last = null
            first = null
        } else {
            if (node == first)
                first = nnext
            if (node == last)
                last = npre
            npre!!.next = nnext
            nnext!!.prev = npre
            node.next = null
            node.prev = null
        }

        node.item = null
        _size--
        return nitem!!
    }

    /**
     * 转字符串方法
     * */
    override fun toString(): String {
        when (_size) {
            0 -> return "[]"
            else -> {
                val sb = StringBuilder()
                sb.append("[")
                var n = first
                while (n != last) {
                    sb.append("${n!!.item}, ")
                    n = n.next
                }
                return sb.append("${n!!.item}]").toString()
            }
        }
    }

    companion object {
        private data class Node<T>(
                var item: T?,
                var prev: Node<T>?,
                var next: Node<T>?
        )

        /**
         * 查看位置是否合法
         * */
        internal fun checkPositionIndex(index: Int, size: Int) {
            if (index < 0 || size == 0) {
                throw IndexOutOfBoundsException("index: $index, size: $size")
            }
        }
    }

    private inner class IteratorImpl(
            private var index: Int = 0
    ) : MutableIterator<T> {
        private var current: Node<T>? = null
        private var lastReturned: Node<T>? = null

        init {
            checkPositionIndex(index, size)
            current = getNode(index)
        }

        override fun hasNext(): Boolean = current != null

        override fun next(): T {
            if (!hasNext()) {
                throw NoSuchElementException()
            }
            lastReturned = current
            current = current?.next
            index++
            return lastReturned?.item ?: throw NoSuchElementException()
        }

        override fun remove() {
            unlink(lastReturned ?: throw IllegalStateException())
            index--
        }

    }
}
主函数实现
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
fun linkedListForceSolution(): String {
    val sb = StringBuilder()
    val cl = CircularLinkedList<Int>().apply {
        for (i in 1..totalPeople)
            add(i)
    }
    val iter = cl.iterator()

    var cnt = 0
    while (iter.hasNext() && cl.size != remainPeople) {
        iter.next()
        cnt++
        if (cnt == intervalPeople) {
            iter.remove()
            cnt = 0
        }
    }

    return sb.apply {
        cl.forEachIndexed { index, i ->
            append("${i}号")
            if (index != cl.size - 1) append(", ") else return@apply
        }
    }.toString()
}
分析

时间复杂度：

这里使用的是循环链表实现，所以进出队列的时间复杂度都是$\mathcal{O}(1)$，所以仅用计算循环时间复杂度。

设总人数 $T$，间隔人数 $I$，剩余人数 $R$。
$$
\mathcal{O}((T-R)*I)
$$
空间复杂度：

存在中间数据结构循环链表，非常数级空间复杂度。
$$
\mathcal{O}(N)
$$

数学解法

说明

其实数学解法也是应用了一种环的思想，但环思想在此解法中仅是辅助作用，主要的思想是倒推和数学归纳法的应用。

我们先从(T = 2, R = 1, I = 3)开始看起：

preview
preview

可以看到，

第一轮删除了2，所以第二轮就从2后面的一位元素开始。

因为我们假设整个数组也是环形的，所以数组结尾后面的元素也是开始的元素，如此反复，所以第二轮删除了0

同理，第三轮删除了4

第四轮删除了1

这样，完整的过程我们就模拟完成了，这也是我们前两种方法的主要思路，模拟整个过程，完成计算。但其实，我们并不需要观察整个数组变化的过程，我们只需要观察我们所需要的关键元素就可以了，在这里即是3，我们从最后一轮选择出的结果倒推，直到推导出此元素最开始在原数组中的位置即可直接输出原数组中的元素。注意：这里我们是先正向推导了一遍才可以直接看出来数字是3的，真实情况下我们是不需要正向推导，而是从结果来反推。

比如上面的例子，第一轮反推，我们首先抛弃数字的概念，设定最后选出来的数字x的下标是0。

为反推到第四轮首先先补上间隔数字，得出[a, x, | a, x]，此时x下标为1

再往上反推，得出[a , x , b, | a, x]，所以x下标为1

再往上，[x, b, c, a, | x, b]，所以x下标为0

再往后就是[c, a , d, x, b, | c, a]，所以最终x的坐标就是3

从此，我们可以发现，每一次倒推的数组组成都是末尾+新数字+开头的反向三明治结构，这就导致每一次倒推的数字下标是$(index + I) \mod K$，$K$为反推后数组大小。

根据数学归纳法，可以推出如下公式：

设函数$f(K, I)$为$K$个报数时，间隔人数为$I$的时候，所求最终胜出的人的编号。
$$
f(K, I) = (f(K - 1, I) + I) \mod K
$$
测试一下
$$
f(1,3) = 0\\
f(2,3) = (f(1, 3) + 3) \mod 2 = 1\\
f(3,3) = (f(2, 3) + 3) \mod 3 = 1\\
f(4,3) = (f(3, 3) + 3) \mod 4 = 0\\
f(5,3) = (f(4, 3) + 3) \mod 5 = 3
$$
结果正确~

实现

数学实现

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fun mathFastSolution(): String {
    val sb = StringBuilder()
    val k = MutableList(remainPeople) { it }
    for (idx in remainPeople + 1..totalPeople) {
        k.forEachIndexed { index, i ->
                          k[index] = (i + intervalPeople) % idx
                         }
    }
    return sb.apply {
        k.map { it + 1 }
        .forEachIndexed { index, i ->
                         append("${i}号")
                         if (index != k.size - 1) append(", ")
                        }
    }.toString()
}
分析

时间复杂度：

这里使用的是数学方法实现。

设总人数 $T$，间隔人数 $I$，剩余人数 $R$。
$$
\mathcal{O}((T-R+1)*R)
$$
空间复杂度：

不存在中间数据结构，仅是用到了循环变量，所以是常数级空间复杂度。
$$
\mathcal{O}(1)
$$

类实现

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
package algorithms

import ds.CircularLinkedList
import ds.Deque

class JosephusSolutions(
        private var totalPeople: Int = 0,
        private var intervalPeople: Int = 0,
        private var remainPeople: Int = 1
) {
    init {
        checkArguments()
    }

    private fun checkArguments() {
        if (
                totalPeople <= 0 || remainPeople <= 0 || intervalPeople <= 0
        ) {
            throw IllegalArgumentException("人数不能小于等于0！")
        }

        if (totalPeople < remainPeople)
            throw IllegalArgumentException("总人数不能小于剩余人数！")
    }

    fun changePeopleNumbers(
            totalPeople: Int,
            intervalPeople: Int,
            remainPeople: Int
    ) {
        this.totalPeople = totalPeople
        this.intervalPeople = intervalPeople
        this.remainPeople = remainPeople
        checkArguments()
    }

    /**
     * 双向队列暴力求法
     * 就是嗯求
     * */
    fun queueForceSolution(): String {
        val sb = StringBuilder()
        // 初始化队列
        val deque = Deque<Int>().apply {
            for (i in 1..totalPeople)
                pushRight(i)
        }

        // 没有到剩余人数就继续循环
        while (deque.size != remainPeople) {
            // 跳过间隔人数
            // 这里的跳过为了不影响后面的循环做的是左出右进的方案
            for (q in 1 until intervalPeople)
                deque.pushRight(deque.popLeft())
            deque.popLeft()
        }

        return sb.apply {
            deque.forEachIndexed { index, i ->
                append("${i}号")
                if (index != deque.size - 1) append(", ")
            }
        }.toString()
    }

    fun linkedListForceSolution(): String {
        val sb = StringBuilder()
        val cl = CircularLinkedList<Int>().apply {
            for (i in 1..totalPeople)
                add(i)
        }
        val iter = cl.iterator()

        var cnt = 0
        while (iter.hasNext() && cl.size != remainPeople) {
            iter.next()
            cnt++
            if (cnt == intervalPeople) {
                iter.remove()
                cnt = 0
            }
        }

        return sb.apply {
            cl.forEachIndexed { index, i ->
                append("${i}号")
                if (index != cl.size - 1) append(", ") else return@apply
            }
        }.toString()
    }

    fun mathFastSolution(): String {
        val sb = StringBuilder()
        val k = MutableList(remainPeople) { it }
        for (idx in remainPeople + 1..totalPeople) {
            k.forEachIndexed { index, i ->
                k[index] = (i + intervalPeople) % idx
            }
        }
        return sb.apply {
            k.map { it + 1 }.forEachIndexed { index, i ->
                append("${i}号")
                if (index != k.size - 1) append(", ")
            }
        }.toString()
    }
}

Github

Github