约瑟夫环问题

情景一

约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围，从 编号为k的人开始报数，数到m的那个人出列，它的下一个人又从1开始报数，数到m的那个人又出列， 依此规律重复下去，直到圆桌周围的人全部出列，输出人的出列顺序。

#include <iostream>
using std::cout;
using std::endl;

struct Node {
    int _data;
    Node* _next;
    Node(int data = 0, Node* next = nullptr) : _data(data), _next(next) {}
};

void josephRing(int n, int k, int m) {
    //创建循环链表
    Node* head = new Node(1);
    Node* p = head;
    for(int i = 2; i <= n; ++i) {
        Node* newNode = new Node(i);
        p->_next = newNode;
        p = p->_next;
    }
    p->_next = head;    //p指向尾结点

    //先走k步
    Node* q = head;
    for(int i = 1; i < k; ++i) {
        p = q;
        q = q->_next;
    }   //结束后q指向第K个人

    while(1) {
        for(int i = 1; i < m; ++i) {
            p = q;
            q = q->_next;
        }//q指向第m人
        cout << q->_data << " ";

        if( p == q) {//只剩最后一个结点
            delete q;
            cout << endl;
            return;
        }
        else {
            p->_next = q->_next;
        	delete q;
        	q = p->_next;
        }
    }

}

int main(void)
{
    josephRing(8, 1, 3);
    josephRing(8, 1, 1);
}

$./main 
3 6 1 5 2 8 4 7 
1 2 3 4 5 6 7 8 

情景二

15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

“约瑟夫环”问题的四种方法及详解注释（c++实现）_约瑟夫环c++-CSDN博客

情景三

LCR 187. 破冰游戏

社团共有 num 为成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。