题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。
分析:本题就是有名的约瑟夫环问题。既然题目有一个数字圆圈,很自然的想法是我们用一个数据结构来模拟这个圆圈。在常用的数据结构中,我们很容易想到用环形列表。我们可以创建一个总共有m个数字的环形列表,然后每次从这个列表中删除第m个元素。
在参考代码中,我们用STL中std::list来模拟这个环形列表。由于list并不是一个环形的结构,因此每次跌代器扫描到列表末尾的时候,要记得把跌代器移到列表的头部。这样就是按照一个圆圈的顺序来遍历这个列表了。
这种思路需要一个有n个结点的环形列表来模拟这个删除的过程,因此内存开销为O(n)。而且这种方法每删除一个数字需要m步运算,总共有n个数字,因此总的时间复杂度是O(mn)。当m和n都很大的时候,这种方法是很慢的。
接下来我们试着从数学上分析出一些规律。首先定义最初的n个数字(0,1,…,n-1)中最后剩下的数字是关于n和m的方程为f(n,m)。
在这n个数字中,第一个被删除的数字是(m-1)%n,为简单起见记为k。那么删除k之后的剩下n-1的数字为0,1,…,k-1,k+1,…,n-1,并且下一个开始计数的数字是k+1。相当于在剩下的序列中,k+1排到最前面,从而形成序列k+1,…,n-1,0,…k-1。该序列最后剩下的数字也应该是关于n和m的函数。由于这个序列的规律和前面最初的序列不一样(最初的序列是从0开始的连续序列),因此该函数不同于前面函数,记为f’(n-1,m)。最初序列最后剩下的数字f(n,m)一定是剩下序列的最后剩下数字f’(n-1,m),所以f(n,m)=f’(n-1,m)。
接下来我们把剩下的的这n-1个数字的序列k+1,…,n-1,0,…k-1作一个映射,映射的结果是形成一个从0到n-2的序列:
k+1
-> 0
k+2
-> 1
…
n-1
-> n-k-2
0
-> n-k-1
…
k-1 ->
n-2
把映射定义为p,则p(x)=
(x-k-1)%n,即如果映射前的数字是x,则映射后的数字是(x-k-1)%n。对应的逆映射是p-1(x)=(x+k+1)%n。
由于映射之后的序列和最初的序列有同样的形式,都是从0开始的连续序列,因此仍然可以用函数f来表示,记为f(n-1,m)。根据我们的映射规则,映射之前的序列最后剩下的数字f’(n-1,m)=
p-1[f(n-1,m)]=[f(n-1,m)+k+1]%n。把k=(m-1)%n代入得到f(n,m)=f’(n-1,m)=[f(n-1,m)+m]%n。
经过上面复杂的分析,我们终于找到一个递归的公式。要得到n个数字的序列的最后剩下的数字,只需要得到n-1个数字的序列的最后剩下的数字,并可以依此类推。当n=1时,也就是序列中开始只有一个数字0,那么很显然最后剩下的数字就是0。我们把这种关系表示为:
0n=1
f(n,m)={
[f(n-1,m)+m]%n
n>1
尽管得到这个公式的分析过程非常复杂,但它用递归或者循环都很容易实现。最重要的是,这是一种时间复杂度为O(n),空间复杂度为O(1)的方法,因此无论在时间上还是空间上都优于前面的思路。
思路一的参考代码:
///////////////////////////////////////////////////////////////////////
//n integers (0, 1, ... n - 1) form a circle. Remove the mth from
//the circle at every time. Find the last number remaining
//Input: n - the number of integers in the circle initially
//
m - remove themth number at every time
//Output: the last number remaining when the input is valid,
//
otherwise -1
///////////////////////////////////////////////////////////////////////
intLastRemaining_Solution1(unsigned
int n,
unsigned
int m)
{
// invalid input
if(n < 1|| m < 1)
return -1;
unsigned
int i = 0;
//initiate a list with n integers (0, 1, ... n - 1)
list<int>integers;
for(i = 0; i< n; ++ i)
integers.push_back(i);
list<int>::iteratorcurinteger = integers.begin();
while(integers.size()> 1)
{
// find the mth integer. Note that std::list is not acircle
// so we should handle it manually
for(int i = 1; i < m; ++ i)
{
curinteger ++;
if(curinteger== integers.end())
curinteger = integers.begin();
}
//remove the mth integer. Note that std::list is not a circle
// so we should handle it manually
list<int>::iteratornextinteger = ++ curinteger;
if(nextinteger== integers.end())
nextinteger = integers.begin();
--curinteger;
integers.erase(curinteger);
curinteger = nextinteger;
}
return *(curinteger);
}
思路二的参考代码:
///////////////////////////////////////////////////////////////////////
//n integers (0, 1, ... n - 1) form a circle. Remove the mth from
//the circle at every time. Find the last number remaining
//Input: n - the number of integers in the circle initially
//
m - remove themth number at every time
//Output: the last number remaining when the input is valid,
//
otherwise -1
///////////////////////////////////////////////////////////////////////
intLastRemaining_Solution2(int
n, unsigned
int m)
{
// invalid input
if(n <= 0|| m < 0)
return -1;
//if there are only one integer in the circle initially,
// of course the last remaining one is 0
intlastinteger = 0;
//find the last remaining one in the circle with n integers
for (int i = 2; i <= n; i ++)
lastinteger = (lastinteger + m) % i;
return lastinteger;
}
如果对两种思路的时间复杂度感兴趣的读者可以把n和m的值设的稍微大一点,比如十万这个数量级的数字,运行的时候就能明显感觉出这两种思路写出来的代码时间效率大不一样。
分享到:
相关推荐
用循环单向链表解决约瑟夫问题 原题: 设有n个人站成一圈,每个人持有一个密码(正整数)。现从第t个人开始,按顺时针方向“1,2,3,4,…”循环报数,数到m1(第t个人所持密码)的人出列,然后从出列者的下一个人重新...
已知n个人(不妨分别以编号1,2,3,…,n 代表 )围坐在一张圆桌周围,首先从编号为 k 的人从1开始顺时针报数,1, 2, 3, ...,记下顺时针数到 m 的那个人,同时从编号为 k ...数据结构中经典的双向约瑟夫问题c语言代码
约瑟夫问题代码,约瑟夫问题代码
约瑟夫问题,通过类实现的链表,并加以改进,做成双向链表
约瑟夫问题的两种求解方法,顺序存储和链表
约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的人的序号为5,4,6,2,3。最后剩下1号。 假定在圈子里前K个为好人,后K...
约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。 分析: (1)由于对于每个人只有死和活两种...
用链表与循环完成约瑟夫问题 while (cin>>x>>y) { node *p, *q; //建立循环链表 for (i = 1; i ; i++) { if (i == 1) { list->head = new node; list->head->data = i; q = list->head; ...
Josephus 约瑟夫问题(POJ)相关习题的源代码(1012,2359,1781,2244,3517,2939,2800)
C++_循环链表实现约瑟夫问题 vc2008 课堂作业!
该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n个人围坐一圈,用链表中的每一个结点代表一个人和他所代表的序号。在输入初始序号m后,对该链表进行遍历,直到第m个结点,令该结点的序号值作为新的序号值,...
利用循环链表实现约瑟夫问题的求解。 约瑟夫问题如下:已知n个人(n>=1)围坐一圆桌周围,从1开始顺序编号。从序号为1的人开始报数,顺时针数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依...
约瑟夫问题C语言
解决约瑟夫问题,数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构解决约瑟夫问题数据结构...
利用STL解决约瑟夫问题,可以接受数据的不同存储方式,比如vector ,list 等。
约瑟夫问题循环链表实现代码
约瑟夫问题的来历 约瑟夫问题的一般形式: 约瑟夫问题的另外一个有名的例子: 猴子选大王 笔算解决约瑟夫问题
算法实现源程序java代码实现约瑟夫问题