菜鸟系列之C/C++经典试题(五)

超、凢脫俗 2022-08-11 16:52 132阅读 0赞

**求圆圈中剩下的最后一个数字**

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

本题就是著名的约瑟夫环问题。

本题的解法我们比较容易想到用链表，当然我们可以自己写一个链表，也可以直接用stl库中的list，实现代码如下：

//使用标准库
    int JosephusProblem_Solution2(int n, int m)
    {
    	if(n < 1 || m < 1)
    		return -1;
    
    	list<int> listInt;
    	unsigned i;
    	//初始化链表
    	for(i = 0; i < n; i++)
    		listInt.push_back(i);
    
    	list<int>::iterator iterCurrent = listInt.begin();
    	while(listInt.size() > 1)
    	{
    		//前进m - 1步
    		for(i = 0; i < m-1; i++)
    		{
    			if(++iterCurrent == listInt.end())
    				iterCurrent = listInt.begin();
    		}
    		//临时保存删除的结点
    		list<int>::iterator iterDel = iterCurrent;
    		if(++iterCurrent == listInt.end())
    			iterCurrent = listInt.begin();
    		//删除结点
    		listInt.erase(iterDel);
    	}
    
    	return *iterCurrent;
    }

分析：上面解法的时间复杂度为(n-1)\*m，即(mn)。让我们试图来寻找一种更好的解法。

我们用归纳法来分析，假如我们能找到第n-1个数和第n个数关系，我们就可以一次递推到删除到1个数在2个数的位置，在3….n个数中的文字，最后得到解。

现在我们来找这个关系:

在这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。

k+1 -> 0  
k+2 -> 1  
…  
n-1 -> n-k-2  
0 -> n-k-1  
…  
k-1 -> n-2

现在我们知道了有n-1个数时last的位置，记为f(n-1,m)，那么如何来求得f(n,m)关于f(n-1,m)之间的关系？用X,Y来表示，如下：

Y X

k+1 -> 0  
k+2 -> 1  
…  
n-1 -> n-k-2  
0 -> n-k-1  
…  
k-1 -> n-2

y=( x+k+1) %n

k = (m-1)%n

所以y=(x+m)%n，最终关系如下：

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

所以，我们可以用上面的是，最后剩下的数即n=1时要删除的数， n = 1 时， f(n, m ) = 0，由此我们知道, f（2， m）…

代码如下：

int JosephusProblem_Solution4(int n, int m)
    {
    	if(n < 1 || m < 1)
    		return -1;
    
    	vector<int> f(n+1,0);
    	for(unsigned i = 2; i <= n; i++)
    		f[i] = (f[i-1] + m) % i;
    
    	return f[n];
    }

有错请指出， 分享请标明出处! 谢谢