14.约瑟夫环问题[JosephusProblem]

【题目】

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;
}

【参考】

http://zhedahht.blog.163.com/blog/static/2541117420072250322938/

http://en.wikipedia.org/wiki/Josephus_problem

上一篇:Linux内核中锁机制之信号量、读写信号量


下一篇:Linux内核中锁机制之内存屏障、读写自旋锁及顺序锁