首页 > 编程语言 >利用数组实现约瑟夫环算法

利用数组实现约瑟夫环算法

时间:2024-08-12 22:51:49浏览次数:15  
标签:Josephus 个人 int flag 约瑟夫 ++ 算法 数组 报数

问题来历:     据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

约瑟夫环问题有多种变形,下面给出一种实现方式。

问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉(我们这里认为第3个人被杀掉),最后剩下的一个人可以免于死亡,问最后留下来的人是第几个人。

分析:

(1)由于对于每个人只有死和活两种状态,可以用1表示活着,0表示死

(2)开始时每个人都是活的,所以数组初值全部赋为1。

(3)模拟杀人过程,直到所有人都被杀死为止:如果人在队伍(==1)中就报数,报到3将1置为0,重新开始报数,直到只剩下一个人。

(4)重新循环数组,仍在队列中(仍==1)的就是剩下的那个人。

代码如下:

//约瑟夫环
#include<stdio.h>
#define n 20
int main()
{
	int m = 3;//数到3的人出列
	int flag[n] = { 0 };//20个人
	int i;
	int outCount = 0;//出列的人数
	int numoff = 0;//报数
	for (i = 0; i < n; i++)
	{
		flag[i] = 1;//所有人都在
	}
	while(outCount < 19)
	{
		for (i = 0; i < 20; i++)
		{
			//如果在队伍中
			if (flag[i] == 1)
			{
				numoff++;//报数
				//数到3出列
				if (numoff == 3)
				{
					printf("第%d个人出列\n", i);
					outCount++;
					flag[i] = 0;
					numoff = 0;
				}
			}
		}
	}
	for (i = 0; i < n; i++)
	{
		if (flag[i] == 1)
		{
			printf("最后留下的人是%d\n", i);
		}
	}

}

标签:Josephus,个人,int,flag,约瑟夫,++,算法,数组,报数
From: https://blog.csdn.net/you_52/article/details/141097189

相关文章

  • 「Day 7—离散化 & 树状数组 & 线段树」
    离散化定义离散化本质是一种哈希,是一种用来处理数据的方法。1.创建原数组的副本。2.将副本中的值从小到大排序。3.将排序好的副本去重。4.查找原数组的每一个元素在副本中的位置,位置即为排名,将其作为离散化后的值。B3694数列离散化代码#include<iostream>#include<algo......
  • 自学linux第十五天:二维数组的指针
    二位字符型数组:chars[][10]={"hello","world","china"};1.定义指针:char(*p)[10]=s;这样定义表示为  p指向二维数组s                 *(*(p+i)+j) 表示二维数组中的s[i][j]元素chars[10]="hello";//存放字符串数据s的......
  • 24/8/12算法笔记 复习_线性回归
    importnumpyasnp#导入包X=np.array([[1,1],[2,1]])#构造矩阵y=np.array([14,10])np.linalg.solve(X,y)#linalg是线性代数,用于求解线性方程AX=b,solve计算线性代数回归问题X.T#转置a=X.T.dot(X)#矩阵乘法B=np.linalg.inv(a)#求逆矩阵fromsklearn.line......
  • 24/8/11算法笔记AdaBoost多分类原理展示
    importnumpyasnpfromsklearn.ensembleimportAdaBoostClassifierfromsklearnimportdatasetsfromsklearn.model_selectionimporttrain_test_splitfromsklearnimporttreeimportgraphviz加载数据X,y=datasets.load_iris(return_X_y=True)X_train,X_test......
  • 【聚类算法】
    聚类算法是一种无监督学习方法,用于将数据集中的数据点自动分组到不同的类别中,这些类别也称为“簇”或“群”。聚类的目标是让同一簇内的数据点尽可能相似,而不同簇之间的数据点尽可能不相似。聚类算法广泛应用于多种领域,如数据挖掘、模式识别、图像分析、信息检索等。聚类算......
  • 长度最小的子数组 | LeetCode-209 | 双指针+滑动窗口 | 前缀和+二分查找 | Java详细注
    ......
  • 字符串查找 - 模拟实现strstr 、BF算法 、 KMP算法
    文章目录前言一、模拟实现库函数strstr二、BF算法三、KMP算法总结前言路漫漫其修远兮,吾将上下而求索。一、模拟实现库函数strstrTips:此处采用利用指针+字符串末尾'\0'的判断,当然你可以利用数组的下标;库函数strstr的原型:char*strstr(constchar*str1,......
  • 用Python实现9大回归算法详解——01线形回归算法
    1.线性回归的基本概念线性回归是一种最基本的监督学习算法,用于预测因变量(目标变量)和一个或多个自变量(特征变量)之间的关系。线性回归假设因变量与自变量之间的关系是线性的,即可以用以下形式的线性方程来表示:其中: 是因变量(目标变量)。 是自变量(特征变量)。是截距项,表示当所......
  • 个性化推荐算法需要备案!
    政策要求:根据我国《互联网信息服务算法推荐管理规定》(以下简称《规定》)第六条,具有舆论属性或社会动员能力的互联网信息服务,包括个性化推荐算法,需要进行备案。个性化推荐算法:这种算法根据用户行为和偏好提供个性化内容,如个性化推送类,需要备案。评估自身:个性化推荐算法平台......
  • 2024年新SCI顶刊算法红嘴蓝鹊优化器RBMO优化Transformer模型的多变量时间序列预测
    matlabR2024a以上一、数据集二、2024年新SCI顶刊算法红嘴蓝鹊优化器RBMO红嘴蓝鹊优化算法(Red-billedbluemagpieoptimizer,RBMO)是一种新型的元启发式算法(智能优化算法),灵感来源于红嘴蓝鹊的合作、高效的捕食行为。该成果由ShengweiFu等人于2024年5月发表在SCI顶......