14.约瑟夫环问题[JosephusProblem]

2024-03-21 15:22:28

【题目】

n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。

【分析】

本题就是有名的约瑟夫环问题。既然题目有一个数字圆圈，很自然的想法是我们用一个数据结构来模拟这个圆圈。在常用的数据结构中，我们很容易想到用环形列表。我们可以创建一个总共有m个数字的环形列表，然后每次从这个列表中删除第m个元素。

这种思路需要一个有n个结点的环形列表来模拟这个删除的过程，因此内存开销为O(n)。而且这种方法每删除一个数字需要m步运算，总共有n个数字，因此总的时间复杂度是O(mn)。当m和n都很大的时候，这种方法是很慢的。

接下来我们试着从数学上分析出一些规律。首先定义最初的n个数字（0,1,…,n-1）中最后剩下的数字是关于n和m的方程为f(n,m)。

f(n,m)的DP表达式为：

f(1,m)=0
f(n,m)=[f(n-1,m)+m]%n (n>=2)

证明略。

【代码】

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//f(1,m)=0
//f(n,m)=[f(n-1,m)+m]%n (n>=2)
int LastRemaining_Solution2(int n, unsigned int m)
{
// invalid input
)
;

// if there are only one integer in the circle initially,
// of course the last remaining one is 0
;

// find the last remaining one in the circle with n integers
; i <= n; i ++)
lastinteger = (lastinteger + m) % i;

return lastinteger;
}

【参考】

码农公寓