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

简介:

问题: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,于是这个人就是吃不到馒头的人。


目录
相关文章
|
JavaScript 前端开发 Python
leetcode每日一题 2021/4/4 781. 森林中的兔子
leetcode每日一题 2021/4/4 781. 森林中的兔子
57 0
|
6月前
|
机器学习/深度学习 Java Python
代码解密 | 2024春晚刘谦魔术与约瑟夫环问题
2024春节联欢晚会中,刘谦老师的魔术节目可以说是我心目中的全场最佳~春晚刚结束网上就有大佬给出了第二个魔术(拼扑克牌)的数学模拟,也有大佬发布了代码程序。博主在模拟了魔术过程之后,也在此分享一下程序代码和思路。同时,也借此回顾一下经典的数学问题:约瑟夫环问题。
101 8
|
6月前
|
算法
2024春晚纸牌魔术原理----环形链表的约瑟夫问题
2024春晚纸牌魔术原理----环形链表的约瑟夫问题
|
6月前
|
算法
【力扣热题100】287. 寻找重复数(弗洛伊德的乌龟和兔子方法)
【力扣热题100】287. 寻找重复数(弗洛伊德的乌龟和兔子方法)
66 0
PTA猴子选大王(约瑟夫环问题)
PTA猴子选大王(约瑟夫环问题)
122 1
|
存储
剑指Offer - 面试题14:剪绳子
剑指Offer - 面试题14:剪绳子
82 0
|
机器学习/深度学习
剑指offer 13. 剪绳子
剑指offer 13. 剪绳子
71 0
|
存储 算法 C++
【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!
【每日算法Day 74】经典面试题:约瑟夫环,我敢打赌你一定不会最后一种方法!
LeetCode每日一题——1823.找出游戏的获胜者(约瑟夫环问题)
共有 n 名小伙伴一起做游戏。小伙伴们围成一圈,按 顺时针顺序 从 1 到 n 编号。确切地说,从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置,其中 1 <= i < n ,从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
154 0
LeetCode每日一题——1823.找出游戏的获胜者(约瑟夫环问题)
|
机器学习/深度学习 C++
洛谷P1996 约瑟夫问题 c++链表做法
n 个人围成一圈,从第一个人开始报数,数到 mm 的人出列,再由下一个人重新从 11 开始报数,数到 mm 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。 输入格式 输入两个整数 n,mn,m。 输出格式 输出一行 nn 个整数,按顺序输出每个出圈人的编号。 输入输出样例 输入 #1 10 3 输出 #1 3 6 9 2 7 1 8 5 10 4
176 0