约瑟夫问题

待我称王封你为后i 2022-08-08 00:39 180阅读 0赞

**约瑟夫环问题：一圈共有N个人，开始报数，报到M的人自杀，然**

**后重新开始报数，问最后自杀的人是谁？**

**![Center][]**

**第一种方法：循环思想**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    int pep[50],die[50];
    int main()
    {
    	int i,num,f,n,t,f1,m;
    	cout<<"输入人数和循环人数"<<endl;
    	cin>>n>>m;
    	for(i=0;i<=n-1;i++)
    	{
    		pep[i]=1;
    	}//一定要从0开始
    	f=-1;//f应该从-1开始
    	t=0;//记录循环次数
    	f1=num=1;
    	while(num<=n)//循环次数
    	{
    		while(1)
    		{
    			f=(f+1)%n;
    			if(pep[f]==1)
    			{
    				t++;
    			}//如果活着t就加加
    			if(t==m)//如果等于m这个人就死了
    			{
    				pep[f]=0;//0表示死了
    				die[f1++]=f+1;//记录这个人的第几死
    				t=0;//循环从0开始
    				break;//此句结束
    			}
    		}
    		num++;
    	}
    	for(i=1;i<=n;i++)
    	{
    		printf("第%d个死的人是%d\n",i,die[i]);
    	}
    }

运行结果：

**![Center 1][]**

**这种方法的优点是记录了每一个人的死亡，缺点是运行速度很慢**

**当题目让求最后一个死亡的人且n值很大时，这个算法就不太适**

**合了**

**so这时需要找到规律，运用数学方法**

#include<iostream>
    using namespace std;
    int main()
    {
    	int N;//人的总个数
    	int M;//间隔多少个人
    
    	cin>>N;
    	cin>>M;
    	int result=0;//N=1情况
    	for (int i=2; i<=N; i++)
    	{
    		result=(result+M)%i;
    	}
    	cout<<"最后自杀的人是："<<result+1<<endl;//result要加1
    	return 0;
    }

[Center]: /images/20220805/4685c48f47264812a41c3b618a40a9f9.png
[Center 1]: /images/20220805/3be02ee4db724b2391df2c000a94710a.png

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关约瑟夫问题

约瑟夫问题作者：Ackarlix 这是一个非常经典的问题：n个骑士编号1，2，...，n，围坐在圆桌旁，编号为k的骑士从1开始报数，报到m的骑士出列，然后下一个位置再从1

刺骨的言语ヽ痛彻心扉/ 2022年09月19日 13:29/ 0 赞/ 201 阅读

相关约瑟夫问题

约瑟夫问题如下： n个人围成一圈，从1号开始报数，报到m就退出，剩下的人从下一个人开始继续报数。。。问最后剩下的是谁？也可问每个人的死亡顺序. 这一题在数据量比较小的

太过爱你忘了你带给我的痛/ 2022年08月10日 17:55/ 0 赞/ 146 阅读

相关约瑟夫问题

约瑟夫环问题：一圈共有N个人，开始报数，报到M的人自杀，然后重新开始报数，问最后自杀的人是谁？ ![Center][] 第一种方法：循环思想

待我称王封你为后i/ 2022年08月08日 00:39/ 0 赞/ 181 阅读

相关约瑟夫问题

适合队列初学者 \include<queue> //队列头文件 queue<int>q; //定义队列q，I

ゝ一世哀愁。/ 2022年08月04日 04:10/ 0 赞/ 176 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被

￡神魔★判官ぃ/ 2022年07月14日 12:44/ 0 赞/ 174 阅读

相关约瑟夫问题

约瑟夫问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statis

分手后的思念是犯贱/ 2022年06月18日 05:24/ 0 赞/ 177 阅读

相关约瑟夫问题

<table> <tbody> <tr> <td>成绩</td> <td>10</td> <td>开启时间</td> <td>2017

╰半夏微凉°/ 2022年06月02日 08:57/ 0 赞/ 273 阅读

相关约瑟夫问题

1.知识点：循环链表 2.题意：n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，请输出最后一个人的编号 3.注意事项：

心已赠人/ 2022年05月30日 04:46/ 0 赞/ 170 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人

我就是我/ 2022年05月16日 06:06/ 0 赞/ 184 阅读

相关约瑟夫问题

约瑟夫问题 ![在这里插入图片描述][20181114211743434.jpg] 题目描述：开始有5个人围成圆形，从0号开始，数2个人，谁被数到就

灰太狼/ 2022年04月16日 00:46/ 0 赞/ 198 阅读