题目描述
据说著名犹太历史学家 Josephus 有过以下故事：在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。现在请用单向环形链表得出最终存活的人的编号。
输入描述:
一行两个整数 n，m，n 表示链表的长度，m 表示每报数到 m 就自杀。
输出描述:
输出最后存活的人的编号(编号从 1 开始到 n)。
分析
模擬法
編程的初學者很容易想到用數組來模擬報數的過程：當報出m時，置數組上相應的元素為1來表示某人的死亡，同時計數器減一。計數器為1時，終止模擬，並輸出最後一個人的編號。
學習過數據結構後，應當想到還可以用循環鏈表來模擬這個過程。相比于數組，鏈表可以隨時刪去某個節點而不需要移動大量元素。這就為編寫程序提供了方便。
若用模擬法求解問題，每經歷一趟從1到m的報數，人數就減少1. 總共有n個人，因此模擬法的時間複雜度為O(mn).
#include <stdio.h>
struct Node {
int id = 0;
Node *next = nullptr;
};
int main() {
int m, n;
while (scanf("%d%d", &n, &m) != EOF) {
// 创建环形链表
Node *head = new Node;
head->id = 1;
Node *tail = head;
for (int i = 2; i <= n; i++) {
Node *node = new Node;
node->id = i;
tail->next = node;
tail = node;
}
tail->next = head;
// 模擬
int k = 1;
while (n > 1) {
if (k == m) { // 刪除節點，計數器減1
k = 1;
--n;
tail->next = head->next;
Node *temp = head;
head = head->next;
delete temp;
}
else { // 繼續報數
++k;
tail = head;
head = head->next;
}
}
printf("%d\n", head->id);
delete head;
}
return 0;
}
倒推法
只要做一些簡單的數學分析，就可以簡化約瑟夫問題的求解過程。
假設某一時刻n = N, m = M，衆人的編號為1, 2, ……, N. 這N個人從1開始報數，編號為K的人自殺了。顯然K = (M - 1) % N + 1. 於是剩下N - 1個人，將這N - 1個人重新編號，令K + 1號變爲1號，於是新舊號碼的對應關係如下
| 舊 | 新 |
|---|---|
| K + 1 | 1 |
| K + 2 | 2 |
| K + 3 | 3 |
| ... | ... |
| K - 2 | N - 2 |
| K - 1 | N - 1 |
記新編號為x，舊編號為y，顯然 y = (x + K - 1) % N + 1 = (x + (M - 1) % N) % N + 1.
得到了這個新舊編碼的變換關係，就可以从n = N - 1时問題的解推知 n = N时問題的解。舉例來說，
假設n = 2, m = 3，顯然最後的倖存者為2；
於是n = 3, m = 3時，最後的倖存者為(2 + 2 % 3 ) % 3 + 1 = 2；
同樣n = 4, m = 3時，最後的倖存者為(2 + 2 % 4) % 4 + 1 = 1；
同樣n = 5, m = 3時，最後的倖存者為(1 + 2 % 5) % 5 + 1 = 4；
……
編寫代碼如下：
#include <stdio.h>
int main() {
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
int x = 1 + (m % 2);
for (int N = 3; N <= n; N++)
x = (x + (m - 1) % N) % N + 1;
printf("%d\n", x);
}
return 0;
}
顯然，倒推法的時間複雜度為O(n).
另外，文中使用的編號為1、2、3、4……像這樣從1開始編號，推導出的公式比較複雜。實際上如果從0開始編號的話，就能得到一個更加簡單的遞推公式。
网友评论