问题：0,1,2,…，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。编程求解圆圈里最后剩下的数字。

该问题就是约瑟夫（Josephuse）环问题。

原理：

解决该问题又两种思路：（1）通过模拟环的删除过程找到最后一个剩余的数字（2）使用动态规划方法

思路一的难点是编程实现这个模拟过程，但直观。第二种思路使用动态规划，需要我们找到删除过程的地推表达式。稍后讲解。

实现：

思路一

通过环形链表模拟该过程，先实现环形链表。在具体实现上有两种方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Node:

    def __init__(self, value):
        self.value = value
        self.next = None

def build_ring_list(numbers):
    if not numbers:
        return None
    root = Node(numbers[0])
    p_node = root
    for value in numbers[1:]:
        p_node.next = Node(value)
        p_node = p_node.next
    p_node.next = root
    return root

删除最后一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
def last_remaining_number(ring, m):
    p_node = ring
    n = 0
    while p_node:
        # 判断是否只剩下最后一个结点
        if p_node == p_node.next:
            return p_node
        n += 1
        # 删除第m个结点，然后重新计数
        if n == m - 1:
            p_node.next = p_node.next.next
            n = 0
        p_node = p_node.next

这种思路的时间复杂度为O(mn)。

另外我们可以使用Python的生成器实现。

（待续）

思路二

使用动态规划。我们注意到，输入的序列在删除一个元素后，序列的长度会改变，如果索引在被删除的元素位置开始计算，那么每删除一个元素，序列的长度减一而索引会完全改变。如果能找到改变前的索引和新索引的对应关系，那么该问题就容易解决了。

我们定义一个函数f(n, m)，表示每次在n个数字0,1,2,3,…,n-1中每次删除第m个数字后剩下的数字。那么第一个被删除的数字的索引是(m-1)%n。删除该索引元素后，剩下的n-1个数字为0,1,2,…,k-1,k+1,…,n-1。下次删除数字是重k+1位置开始，于是可以把序列看作k+1,..,n-1,0,1,…,k-1。该序列最后剩下的序列也是f的函数。但该函数和第一个函数不同，存在映射关系，使用f°来表示，于是有：f(n, m)=f°(n-1, m)。接下来需要找到映射关系。

1
2
3
4
5
6
7
8
9
10
11
k+1 --> 0
k+2 --> 1
     .
     .
     .
n-1 --> n-k-2
0   --> n-k-1
     .
     .
     .
k-1 --> n-2

于是不能得到右边的序列和左边序列的关系。

right = left-k-1

定于为p(n)，则p(n) = (x-k-1)%nx-k-1)%n