约瑟夫环问题——初步了解+数组实现

浏览数：15 / 时间：2015年06月08日

约瑟夫环问题——初步了解+数组实现

一开始接触约瑟夫环问题，还是在C语言的书中，具体的题目如下：n个人围坐成一圈，选某个人开始（比如第1个），从1开始报数，沿着顺时针方向数到m的人被淘汰，然后后面一个人继续再从1开始报数，数到m时再淘汰一人。重复上面的过程，输出剩下的最后一个人。

解题思路：

Step 1：建立一个长度为n的数组；

Step 2：删除的位置编号为i = (i + m -1) % n; 为什么呢？因为第一个人事i = 0，然后 i 增加m-1即可删除另外一个人，把数组想象成一个“环”即可。

Step 3：删除 i 之后，后面的数组元素往前移动；

Step 4：当 i 正好是数组中最后一个数，删除之后，由于后面的新的 i 无法移动（后面没有数了），所以令 i =0;

代码实现如下，这个是用数组实现的：

#include <iostream>
using namespace std; 

int main()
{
	int m, n; 
	cin >> n >> m; 

	int *p=new int[n]; 
	int i; 
	for(i = 0; i < n; i++)  //初始化
	{
		p[i]=i + 1; 
	}

	while(n > 1)
	{
		i = (i + m - 1) % n;   //找到需要删除的位置
		cout << p[i] << "被删除" <<endl; 
		for(int j = i + 1; j < n; j++)  //只能是j=i+1
		{
			p[j - 1]=p[j]; 
		}

		n--; 
		if(i == n)  //如果删除的是最后一个元素，那么需要把i重新置为0
		{
			i = 0; 
		}
	}

	cout << "剩下的是" << p[i] <<endl; 

	delete []p; 

	return 0; 
}

结果如下：

技术分享