此类问题是非常经典的 Josephus 问题（Josephus problem），其起源与犹太历史学家 Flavius Josephus（弗拉维奥·约瑟夫）的记载相关.

他的记载中描述了古罗马时期 $41$ 人通过循环报数决定自杀顺序的传说.

$17$ 世纪法国数学家 Gaspard Monge（加斯帕尔·蒙日）在著作中记载了 $30$ 人淘汰 $15$ 人的教徒求生案例，进一步推广了该问题.

Josephus 通过计算将朋友与自身置于第 $16$ 与 $31$ 位逃生的策略，这成为该问题的历史原型.

本题有许许多多的解法，此片笔记将由易到难地叙述大部分解法.

模拟法

这是思路最自然的解法，我们可以通过多种数据结构进行模拟.

数组模拟

首先是使用数组模拟该问题，我们需要记录以下数据：

int isNotInQue[n], cnt = 0, pos = 1, inQue = n, loop;

下面解释以上参数：

• isNotInQue[i] 代表第 $i$ 个人的状况：是否仍在队伍中，如果是，则值为 $0$，反之为 $1$.
• cnt 模拟报数，代表当前报到了 cnt.
• pos 是当前报数者所在的位置.
• inQue 是当前仍在队伍中的人数.
• loop 是报数临界点，即报到 loop 的人将出列（被杀）.

因此我们可以借助上述参数很自然的写出核心代码：

while (inQue > 0) {
    if (++ cnt == loop) {
        inQue --;
        if (!inQue) {
            break;
        }
        isNotInQue[pos] = 1;
        cnt = 0;
    }
    while (pos ++ && inQue > 0) {
        if (pos == n + 1) {
            pos = 1;
        }
        if (!isNotInQue[pos]) {
            break;
        }
    }
}

当外层 while 被 break 时，isNotInQue 中应该只剩下了一个值为 0 的位置，这个位置上的人就是最终存活的人.

队列模拟

队列（Queue）是一种数据结构，它与栈（Stack）不同，其中的元素遵循先进先出（FIFO）的原则.

因此，我们可以让人按编号从队尾入队，从队首出队. 若出队时没有被杀，则再次从队尾入队，这本质上是在模拟一种循环队列（Circular queue）.

为方便起见，我们使用变量 head 与 tail 分别模拟队列的头指针和尾指针（头指针指向队首元素的位置，尾指针指向队尾元素的位置的下一个位置）.

当然，如果要实现上述的出队入队，head 与 tail 可能会变得非常大，这是一种对内存的极大浪费，因此我们每次在更新 head 与 tail 时都要让其模除一次 n 以保证用固定长度的数组模拟循环队列.

我们使用数组 Que[n] 来表示队列，其中 Que[i] = i 是队列中的人的编号.

我们容易注意到这么做的好处：如果想要让队首元素出队，只需要 head = (head + 1) % n，而不需要去手动更新 Que 中的值. 入队同理.

同样的，我们很容易写出其核心代码：

while (head != tail - 1) {
    if (++ cnt == loop) {
        head = (head + 1) % n;
        cnt = 0;
    } else {
        Que[head] = Que[tail];
        head = (head + 1) % n;
        tail = (tail + 1) % n;
    }
}

最终 Que[head] 即为所求.

当然，由于本题要求使用指针方法处理，可以将 head 与 tail 写成指针，并用指针来创建 Que 数组，此处不再赘述写法.

模拟法到此结束.

数学法

既然此类问题的模拟法如此简单，有没有什么公式能够直接计算最终结果呢？

当然是有的，但是这个公式是一个递推式：

$$f\left(n,m\right) = \left[f\left(n-1,m\right)+m\right]\%n $$

其中 $f\left(n,m\right)$ 指的是在 $n$ 个人，报到 $m$ 时出列的 Josephus 问题中，最终存活者的编号.

为什么是这样？因为每次第 $m-1$ 个人出列后，剩余的 $n-1$ 个人，将从第 $m$ 个人开始报数，组成一个新的 Josephus 问题.

我们可以使用递归轻松写出核心代码：

int josephus(int n, int m) {
    if (n == 1) {
        return 0;
    }
    return (josephus(n - 1, m) + m) % n;
}

当然，需要注意的是，上述代码返回的值是最终存活者的编号减 $1$，因此 josephus(n, m) + 1 是最终答案.

我们也可以在 for 循环中根据递推式直接进行计算：先前我们已经知道，这个递推式本质上是第 $m-1$ 个人出列后，剩余的 $n-1$ 个人，从第 $m$ 个人开始报数，组成一个新的 Josephus 问题. 既然是从第 $m$ 个人开始报数，我们就可以看做这个环状队列被向后转动了 $m$ 个位置.

我们已知最终存活者的编号为 0，可以每次将这个环状队列向前转动 $m$ 个位置，逆推最终存活者原来的编号：

int josephus(int n, int m) {
    int suv = 0;
    for (int i = 2; i <= n; i ++) {
        suv = (suv + m) % i;
    }
    return suv + 1;
}

数学法到此结束.

循环链表法

这是题目 9.2排队报数plus 需要用到的方法.

如果要求使用指针方法处理 Josephus 问题，那么最合适的办法当然是使用循环链表（Circular linked list）.

在 Josephus 问题下，链表的创建十分简单，我们只需要给每个节点赋值固定的编号即可.

定义节点如下：

struct Node {
    int num;
    struct Node* pNext;
};

当然，此处我们可以使用 typedef 来简化后续代码：

typedef struct Node N;

则该循环链表的创建如下：

N* create(int n) {
    N* pHead = (N*)malloc(sizeof(N));
    pHead->num = 1;
    pHead->pNext = NULL;
    N* pCyclic = pHead;
    for (int i = 2; i <= n; i ++) {
        N* pNew = (N*)malloc(sizeof(N));
        pNew->num = i;
        pNew->pNext = NULL;
        pCyclic->pNext = pNew;
        pCyclic = pCyclic->pNext;
    }
    pCyclic->pNext = pHead;
    return pHead;
}

以上 create() 函数将返回创建好的循环链表的头指针.

在创建过程中，我们使用 pNew 来作为新节点的临时指针，并以 pCyclic 作为信使，将所有的节点串联起来. 最终让 pCyclic 指向 pHead 形成闭环.

接下来考虑在循环链表上求解 Josephus 问题，其思路非常清晰且自然：从 pHead 开始，不停向下一个节点寻找，当找到第 loop 个节点后，将其删除（使第 loop - 1 个节点直接指向第 loop + 1 个节点）. 直到剩下最后一个节点，其编号即为所求：

N* josephusProb(N* pHead, int loop) {
    N* pTemp = pHead;
    N* pPre = pTemp;
    while (pTemp->pNext != pTemp) {
        for (int i = 1; i <= loop - 1; i ++) {
            pPre = pTemp;
            pTemp = pTemp->pNext;
        }
        pPre->pNext = pTemp->pNext;
        pTemp = pTemp->pNext;
    }
    return pTemp;
}

该函数返回的是指向最终存活者对应的节点的指针. 在该函数方法中，我们使用了 pPre 和 pTemp 双指针的方法来进行节点的删除，当 pTemp 指向自己的时候，就说明循环链表中只剩下了 pTemp，此时结束循环.

以上就是使用循环链表解决 Josephus 问题的方法.