又是经典的约瑟夫环问题plus版本及vector的熟练使用

目录

1. 前言

2. 正文

2.1 问题

2.2 解决办法

2.2.1 思路

2.2.2 代码实现

2.2.3 测试结果

3. 备注

1. 前言

我记得之前第一次遇到这个题目是当时说的是固定的一个数，就是说固定数3个数，显然比这个简单一点，因为动的数据显然更麻烦一点。有兴趣的小伙伴可以先去看之前的那篇博客。

2. 正文

2.1 问题

题目描述：

设有n个人围坐一圈并按顺时针方向从1到n编号，从第1个人开始进行1到m的报数，报数到第个m人，此人出圈，再从他的下一个人重新开始1到m的报数，如此进行下去直到所剩下一人为止。

输入格式：

输入多行，每行２个数，分别表示n和m.

输出格式：

计算每一行中最后剩下这个人的编号．

样例输入：

8 5

样例输出：

3

2.2 解决办法

2.2.1 思路

这个问题呢，肯定要先读懂题目，就是说一排人，在这个里找隔壁老王，从头开始喊，喊道固定的那个数的时候就出去，下一个人从一开始继续喊，如果队列中人不够，那么久从第一个续上接着喊，直到找到隔壁老王。

这个题目呢也有好多种方法，有从1开始给人编号，有的是将队列中的人都设置为0或者一，最后去遍历那个1或者0是第几个，方法等等。

我使用的是容器给每个人编号的方法，思路就是通过增删改查，最后得到一个元素，读出元素的值就是老王。

这个难点就在于这个删除的时候的迭代器的问题，要考虑到，剩余人数大于报数值，剩余人数等于报数值，剩余人数小于报数值这三种情况，因此只要将这三种情况处理好，那么就没有太大的问题。

在这个过程中可以增加对c++中容器的熟练使用。

看完题目之后，大家还是可以现场是写一下，必经过程和思路都是最重要的。

2.2.2 代码实现

由于思路很清晰，代码就没有太多的注释。

#include <iostream>
#include <vector>
using namespace std;
void updatePeople(vector<int> &data, int &n)
{
    for (int i = 0; i < n; i++)
    {
        data.push_back(i + 1);
    }
}
int lastPeopleNumber(vector<int> &data, int &m)
{
    size_t temp = 0;
    int indx = 1;
    try
    {
        while (data.size() > 1)
        {
            temp++;
            indx++;
            if (data.begin() + temp == data.end())
            {
                temp = 0;
            }
            if (indx == m)
            {

                data.erase(data.begin() + temp);
                indx = 1;
            }
            if (data.begin() + temp == data.end())
            {
                temp = 0;
            }
        }
    }
    catch (const char *message)
    {
        cerr << "error:" << message << endl;
    }
    return data.at(0);
}
int main()
{
    int n, m;
    vector<vector<int>> multi_group(0, vector<int>(2));
    vector<int> people;
    while (cin >> n >> m)
    {
        multi_group.push_back(vector<int>{n, m});
    }
    for (auto temp : multi_group)
    {
        people.clear();
        n = temp.at(0);
        m = temp.at(1);
        updatePeople(people, n);
        cout << lastPeopleNumber(people, m) << endl;
    }
    return 0;
}

2.2.3 测试结果

测试结果也是非常的美丽。

 大家可以直接在这个线上的编译环境执行

码曰 - 让代码在云端多飞一会 (dotcpp.com)

3. 备注

>>>>>>

当时因为这个迭代器的判断老师倒是报端错误，真是气死人了。当时可无语了，感觉都没有错，但是重新分析过那三种情况之后，就悟了。

>>>>>>

人的一生是短的，但如果卑劣地过这一生，就太长了。——莎士比亚

 >>>>>>

制作不易，且行且珍惜，点个关注支持下吧。