(八十一)约瑟夫环/鲁智深吃馒头

简介:

问题:99个人,99个馒头,来了一个鲁智深,找个位置把他放进去,然后每逢五的人,吃一个馒头,并且退场,最后让他无法吃。

代码:

#include<iostream>
int main()
{
	using namespace std;
	int a[100];
	for (int i = 0;i < 100;i++)
	{
		a[i] = 1;
	}

	int m = 0;	//参数m,用于记录出局者
	int i = 1;	//参数i,当i为5时,当事人被赋值为0,即出局,且a++,i=0
	int x = 0;	//参数x,用于记录当前人士坐标,x大于99,则x-100

	for (;m < 99;)
	{
		while (i < 5)
		{
			i++;
			x++;
			while (a[x] == 0)
			{
				x++;
				if (x > 99)x = x - 100;
			}
			if (x > 99)x = x - 100;
		}
		while (a[x] == 0)
		{
			x++;
			if (x > 99)x = x - 100;
		}
		a[x] = 0;
		if (i = 5)
		{
			i = 1;x++;
			while (a[x] == 0)
			{
				x++;
				if (x > 99)x = x - 100;
			}
			if (x > 99)x = x - 100;
		}
		m++;
	}

	for (i = 0;i < 99;i++)
	{
		if (a[i] == 1) { cout << "第" << i + 1 << "个位置,吃不到馒头" << endl; }
	}
	system("pause");
	return 0;
}

输出:

第47个位置,吃不到馒头
请按任意键继续. . .


 

代码解释:

①第一个部分是赋值,在场的人赋值1,然后给退场的人赋值0。

 

②最后一部分是检测谁的值是1,则谁还在场——吃不到馒头。

 

③m是退场标记,每退场一个,m+1,m到99的时候,说明就剩一个人了。

 

④i是计数标记,每当i=5的时候,退场一个人,然后i归1,且位置移动一位。每过一个人,i+1;

 

⑤每次i+1的时候(即位置移动一位的时候),测试一次当前位置有没有人(用值是否为0测试),没有人则i不变,然后当前位置继续加1。

 

⑥可以理解为100个人站成一个圆,

每次移动位置(i+1)的时候,要检测当前位置有没有人,

若有人,则x随之加1;若当前位置无人,则检测下一个位置,一直检测到有人为止,有人后x加一;

若绕完一圈(即x>99),则刚好抵达初始位置(即x-100,从开始起第101个位置的人,和初始位置的人是一个位置),这是x-100的原因。

每次移动5个位置,即逢5的人吃馒头,于是该人退场(值归0)。

等退场99个人后,一个一个位置检测过去,检测到有人值不是0,于是这个人就是吃不到馒头的人。


目录
相关文章
|
2月前
|
算法
2024春晚纸牌魔术原理----环形链表的约瑟夫问题
2024春晚纸牌魔术原理----环形链表的约瑟夫问题
|
5月前
|
存储 C++
【C++从0到王者】第三十站:二叉树的非递归遍历
【C++从0到王者】第三十站:二叉树的非递归遍历
22 0
|
10月前
|
存储
剑指Offer - 面试题14:剪绳子
剑指Offer - 面试题14:剪绳子
56 0
|
10月前
洛谷P1135 奇怪的电梯——广搜
洛谷P1135 奇怪的电梯——广搜
72 0
|
11月前
|
存储 算法 C++
【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!
【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!
|
12月前
PTA猴子选大王(约瑟夫环问题)
PTA猴子选大王(约瑟夫环问题)
|
机器学习/深度学习
带你轻松拿捏N皇后问题
要求任何两个皇后不同行、不同列,也不在同一 条斜线上
100 0
带你轻松拿捏N皇后问题
|
存储 算法
学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
学会二叉树不知道干啥?二叉树的深度优先搜索和广度优先搜索,我要打十个乃至二十个(打开你的LeetCode撸起来)学练并举
LeetCode每日一题——1823.找出游戏的获胜者(约瑟夫环问题)
共有 n 名小伙伴一起做游戏。小伙伴们围成一圈,按 顺时针顺序 从 1 到 n 编号。确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置,其中 1 <= i < n ,从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
104 0
LeetCode每日一题——1823.找出游戏的获胜者(约瑟夫环问题)
|
机器学习/深度学习 算法
每日一题冲刺大厂第九天 新二叉树
大家好,我是泡泡,给大家带来每日一题的目的是为了更好的练习算法,我们的每日一题这个月进度是数据结构,让大家练到各种各样的数据结构题目,熟悉数据结构的增删改查,一年以后,蜕变成为一个不一样的自己!
46 0