C++--用list容器处理约瑟夫环问题

约瑟夫环

约瑟夫环问题是一个经典的数学问题，描述如下：

假设有 n 个人站成一圈，编号从 1 到 n。从第一个人开始报数，报到 m 的人出列，然后下一个人继续从 1 开始报数，直到所有人都出列为止。问最后留下的是原来的第几号

用list解

#include <iostream>
#include <list>

using namespace std;

// 模拟约瑟夫环问题，返回最后剩下的节点的编号
int josephus(int n, int m) 
{
    
    //使用一个循环链表
    list<int> people;

    // 初始化人员列表
    for (int i = 1; i <= n; ++i) 
    {
        people.push_back(i);
    }

    //定义当前的迭代器
    auto current = people.begin();//迭代器

	  //当不知道循环的具体次数时，优先使用while循环
    while (people.size() != 1)
    {
        // 移动迭代器，模拟报数过程
        for (int i = 1; i < m; ++i) 
        {
            ++current;//迭代器往前走
            if (current == people.end()) 
            {
                current = people.begin(); // 如果到达末尾，则从头开始
            }
        }

        // 删除当前节点，并移动迭代器到下一个节点
        current = people.erase(current);
        if (current == people.end()) 
        {
            current = people.begin(); // 如果删除的是末尾节点，则将迭代器移到开头
        }
    }

    // 返回最后剩下的节点的编号
    return *(people.begin());
}

int main() 
{
    int n = 5; // 总人数
    int m = 3; // 报数为 3 的人出列

    int survivor = josephus(n, m);
    cout << "最后剩下的人的编号是：" << survivor << endl;

    return 0;
}