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

?作者简介：大家好，我是大杉。
?? 个人主页：爱编程的大杉
支持我：点赞+收藏~不迷路???
?系列专栏：c语言入门每日一题
(???`?)每日格言：?过去都是假的，回忆是一条没有归途的路，以往的一切春天都无法复原，即使最狂热最坚贞的爱情，归根结底也不过是一种瞬息即逝的现实，唯有孤独永恒。-（加西亚·马尔克斯 《百年孤独》）

题目描述：???解约瑟夫问题。设有n（以n是6为例）只猴子，按 1～n编号围坐一圈，从第一个猴子开始，按顺序从1开始报数，报到m时（以m是4为例），此猴子退出圈外；接着再从1（此时的m接1）开始报数到 m，再退出，如此反复进行，直到只剩一个猴子为止。输入n和m，输出最后剩下的猴子（作为猴子大王）???。

一、????什么是约瑟夫问题？

????约瑟夫问题是一道典型的数组题，也是面试官常考的一道基础题
此题通过“猴子选大王”的场景来体现，六个猴子按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<iostream>
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;
}

刷题要有一个趁手的工具，这里强烈推荐我自己经常用的一个网站牛客网，不管对编程新手还是程序大佬都十分友善，注重基础以及核心素养的训练，这是一份牛客网的java基础的题单：牛客c语言题单大家和我一起赶快刷起吧！