約瑟夫問題【c++】

原題地址

题目描述

据说著名犹太历史学家 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號，於是新舊號碼的對應關係如下

記新編號為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開始編號的話，就能得到一個更加簡單的遞推公式。