【day5-cc++入门题目-关于“约瑟夫问题”那些事】

👀作者简介：大家好，我是大杉。

🚩🚩 个人主页：爱编程的大杉
支持我：点赞+收藏~不迷路🧡🧡🧡
✔系列专栏：c语言入门每日一题
(❁´◡`❁)每日格言：🌞过去都是假的，回忆是一条没有归途的路，以往的一切春天都无法复原，即使最狂热最坚贞的爱情，归根结底也不过是一种瞬息即逝的现实，唯有孤独永恒。

-（加西亚·马尔克斯 《百年孤独》）

题目描述：🏘🏘🏘解约瑟夫问题。

设有n（以n是6为例）只猴子，按 1～n编号围坐一圈，从第一个猴子开始，按顺序从1开始报数，报到m时（以m是4为例），此猴子退出圈外；接着再从1（此时的m接1）开始报数到 m，再退出，如此反复进行，直到只剩一个猴子为止。

输入n和m，输出最后剩下的猴子（作为猴子大王）🚩🚩🚩。

文章目录

• 
  

  一、🏴‍☠️什么是约瑟夫问题？

• 二.🌞如何解决约瑟夫问题
• • 1、❄基本思路
  • 2.☔题意展示图
• 三.🌍动态图展示
• 四. 🧭利用N-S图进行逻辑梳理
• 五.🗽代码展示

---

一、🏴‍☠️什么是约瑟夫问题？

❄❄❄❄约瑟夫问题是一道典型的数组题，也是面试官常考的一道基础题
此题通过“猴子选大王”的场景来体现，六个猴子按1~6编号，从第一个猴子开始报数，一直报数到m，此时淘汰掉第m个猴子。

则在这时原先第m+1个猴子变成了第m个猴子，这个猴子继续报数字“1”。

如此循环这个过程，直到只剩下一个猴子，被选为“大王”

二.🌞如何解决约瑟夫问题 1、❄基本思路

1.首先应该明确定义几个变量？
答：3个变量；
🚩因为要淘汰掉第m个猴子，所以我们需要对淘汰掉的猴子做一个标记，以免下一次报数中，将淘汰掉的猴子计入其内，所以需要一个变量num来记录当前正在报数的猴子的编号（数组下标），当标号到m时，num被赋值为0;
🚩最后要剩余一个猴子，所以需要一个变量rest：记录圈内剩余的猴子数
🚩需要定义一个变量next表示存储下一个猴子应报的数

2.☔题意展示图

三.🌍动态图展示

规定猴子没被淘汰时为“1”，猴子被淘汰为“0”

四. 🧭利用N-S图进行逻辑梳理

五.🗽代码展示

以n=6;m=4为例

#include
using namespace std;
int main()
{
	int m = 0;
	int n = 0;
	cin >> m >> n;
	int rest = n;
	int num = 1;
	int next = 1;
	int arr[7] = { 0 };
	int i = 0;
	for (i = 1; i <= n; i++)
	{
		arr[i] = 1;
	}
	while (rest > 1)
	{
		if (arr[num] == 1)//猴子没有被淘汰
		{
			if (next == m)//当前猴子马上要报m
			{
				arr[num] = 0;
				rest--;
				next = 1;
			}
			else
			{
				next++;
			}
		}
		    if (num == n)

			{
				num = 1;//报道最后一个，又要从“1”开始
			}
			else
			{
				num++;
			}
		
	}
	int j = 1;
	if (j <= n && arr[j] != 1)
	{
		j++;//如果arr[j]=0.则继续向后遍历
		//直到找到剩余一个没有被淘汰的猴子
		cout << j;
	}
	return 0;
}