C++实现Josephus

C++实现Josephus,第1张

如何使用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;
		}
	}

}

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

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

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

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/868051.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-13
下一篇 2022-05-13

发表评论

登录后才能评论

评论列表(0条)

保存