C++实现Josephus

如何使用C++代码实现Josephus问题

• • 1、引言
  • 2、问题的分析与解决思路
• 2.1：分析问题
• 2.2：解决方案，数组实现
• 2.3：编写程序
• • 3、完整代码

1、引言

有一段文本是这样的：

一群小孩 围成一圈，任意假定一个数m，从第一个小孩起，按顺时针方向数，每数到第m个小孩时，该小孩便离开。小孩不断离开，圈子不断缩小。最后，剩下的一个小孩便是胜利者。

Josephus问题就是：请问，究竟胜利者是第几个小孩？

OK，在此声明：对于屏幕前的，如果你是一个小白型选手，对于C++或任何一种语言诸如条件判断、循环、数组等知识不算了解，那么请跳过本文，先将基础知识进行一个学习；如果是对于C++而言，以上知识的基础掌握良好的同学，欢迎阅读本文。同时，本文的目的在于对思维的一种锻炼与基础的一种巩固，可能你学不到一些高级的语法与算法，但是对于我们的目标群体，应该可以略有所得。

好啦，闲话说完，我们进入正题。

2、问题的分析与解决思路 2.1：分析问题

解决这个问题的第一步，需要搞清楚问题的本质，我们用一个图来进行描述：

假定现在有7个小孩围成一圈，m=3。也就是说，从编号为1的小孩开始数，数到3的小孩就离开。
我们来看：第一次数到3时，编号为3的小孩离开了；接着，第二次数到3时，编号为6的小孩离开了。
值得注意的是在这个示例中，第三次报数，编号为7的小号报了1，而编号为1、2的小孩则报出2、3，那么第三次应该离开的，就应该是编号为2的小孩。

在此，按照条件，编号1被忽略，编号2被踢出，这个特点是需要我们关注的。
最后，我们宣布4号小孩为获胜者。
那么，我们在图上进行过程演练的目的，就是为了将流程抽象出来。我们可以针对不同的情况，多次进行上述演练，最终设计出解决Josephus问题的流程：

2.2：解决方案，数组实现

在计算机中，我们当然可以有很多方法实现图中的绕圈，这里选用数组来存储圆圈及其中的小孩。
在这里我们需要实现的要求是：30个小孩，间隔为4，找出最后一位。

const int numofBoy = 30;		//小孩总数
int m;						//Josephus问题中的间隔
int boy[numofBoy];			//小孩数组

其中，定义了一个叫 int 类型常量 numofBoy 表示小孩数，以方便调整小孩的个数。

确定好之后，我们需要明确通过代码实现过程中将要面对的问题，确定解决问题的方法。

	第一个问题：怎样构成一个圆圈？设立一个一维数组，线性储存下如何在逻辑上构成一个圆？
	第二个问题：怎样表示小孩离开？

针对第一个问题，数小孩时，每数一个小孩，数组下标 +1，但数到最后一个时，需要再次从第一个小孩开始数，其下标应该变为 0。这里可以使用 “取模运算” 解决这个问题。

( 下标 + 1 ) % 30

而针对第二个问题，数到的小孩要离开，可将他的编号设置为 0，表示这个小孩已经离开。

此时，再往后数的时候，出现了编号为 0 的元素，其代表的小孩已经离开，因此，在数数时必须跳过编号为 0 的小孩，只数编号非 0 的小孩。
在”当前位置 i 调整到下一个小孩”时，先将当前位置 i 调整到数组中的下一个位置，在使用一个循环跳过编号为 0 的元素，以确保当前位置 i 的小孩没有离开，其代码如下：

i = ( i + 1 ) % numofBoy;
while ( boy[i] == 0 )
	i = ( i + 1 ) % numofBoy;

2.3：编写程序

对照上述流程，编写出程序框架

void main() {
	//n个小孩围成圆圈

	//小孩依次离开

	//宣布胜利者
}

按照定义数组、相关变量并初始化，编写“n个小孩围成圆圈”部分的代码，再按照中二层流程，来编写“小孩依次离开”部分的代码，得到如下程序代码：

void main() {
	//n个小孩围成圆圈
	const int numofBoy = 30;	//小孩总数
	int boy[numofBoy];			//小孩数组

	int i;
	for (int i = 0; i < numofBoy; i++) {//从1开始给小孩编号
		boy[i] = i + 1;
	}
	//输入小孩的间隔
	int m;
	cout << " please input the interval: ";
	cin >> m;
	//输出开始时的小孩编号
	for (i = 0; i < numofBoy; i++) {
		cout << boy[i] << ",";
	}
	cout << endl;
	
	//小孩依次离开
	i = 0;										//当前位置设置为第1个小孩

	int n = numofBoy;							//离开小孩的个数
	while (n > 1) {								//只剩一个小孩
		//数到第m个小孩离开
		//***************************************
		//***************************************
		//此处在此留白

		n--;									//离开一个小孩
	}
	
	//宣布胜利者
	
	//*****************************
	
}

留白部分包含4部分代码，每部分代码都比较简单明确，可分别写出。
“小孩依次离开”相对复杂一点，先编写出第二层代码，后面再编写第三层“数到第m个小孩离开”的代码。

	//数到第m个小孩离开
		int j = m;
		do
		{
			//当前位置i调整到下一个小孩
		//*******************************
		
			j--;								//输一个小孩
		} while (j > 1);						//数到第m个小孩

		//第m个小孩离开
		cout << boy[i] << ",";						//输出离开的小孩编号
		boy[i] = 0;									//标识该小孩离开

		//当前位置i调整到下一个小孩
		//**************************
		

在留白处填入前面讨论的”当前位置 i 调整到下一个小孩“的代码。

输出得胜者与前面联系紧密，放在最后编写。

其他部分相对简单，不作单独讨论。

3、完整代码

最后加上预编译指令#include等与计算机语言相关的代码，就能得到求解Josephus问题的完整代码啦。示例代码如下：

#include
using namespace std;

void main() {
	//n个小孩围成圆圈
	const int numofBoy = 30;	//小孩总数
	int boy[numofBoy];			//小孩数组

	int i;
	for (int i = 0; i < numofBoy; i++) {//从1开始给小孩编号
		boy[i] = i + 1;
	}
	//输入小孩的间隔
	int m;
	cout << " please input the interval: ";
	cin >> m;
	//输出开始时的小孩编号
	for (i = 0; i < numofBoy; i++) {
		cout << boy[i] << ",";
	}
	cout << endl;

	//小孩依次离开
	i = 0;										//当前位置设置为第1个小孩

	int n = numofBoy;							//离开小孩的个数
	while (n > 1) {								//只剩一个小孩
		//数到第m个小孩离开
		int j = m;
		do
		{
			//当前位置i调整到下一个小孩
			i = (i + 1) % numofBoy;
			while (boy[i] == 0) {
				i = (i + 1) % numofBoy;
			}
			j--;								//输一个小孩
		} while (j > 1);						//数到第m个小孩

		//第m个小孩离开
		cout << boy[i] << ",";						//输出离开的小孩编号
		boy[i] = 0;									//标识该小孩离开

		//当前位置i调整到下一个小孩
		i = (i + 1) % numofBoy;
		while (boy[i] == 0) {
			i = (i + 1) % numofBoy;
		}
		n--;										//离开一个小孩
	}

	//宣布得胜者
	for (int i = 0; i < numofBoy; i++) {
		if (boy[i] != 0) {
			cout << "\n\nNo." << boy[i] << " 获胜.\n";	//输出获胜者
			break;
		}
	}

}

完成之后也可以更换项值，多次求解。
先自我求解，再使用计算机求解，判断是否一致。如若不一致，又是谁出了错。

这就是一个很不错的娱乐方式了。（笑）

希望对大部分的读者朋友有所帮助。
如有不足，不吝指教，在此谢过。