「约瑟夫问题」约瑟夫问题

约瑟夫问题

问题描述

$n n$ n 个人，编号 $00$ 0 ~ $(n - 1) (n-1)$ (n−1)，从1开始报数，报到 $m m$ m 的人退出，下一个人继续从0开始报数，求胜利者的编号。

胜利者编号问题

这个问题最好想的就是使用一个循环队列或者循环链表解决，但是我们其实完全没有必要浪费空间，而且移除元素也需要时间，有更简单的方法。

假设总共有8个人，原始编号为0 ~ 7，然后报30，我们来看一下过程：

第1次，0 1 2 3 4 5 6 7，30 % 8 = 6，第6个人出局，即编号为5的人出局，原始编号为5的人出局，然后我们对剩下7个人重新编号。

第2次，2 3 4 5 6 x 0 1，30 % 7 = 2，第2个人出局，即编号为1的人出局，原始编号为7的人出局，然后我们对剩下6个人重新编号。

第3次，0 1 2 3 4 x 5 x，30 % 6 = 0，第6个人出局，即编号为5的人出局，原始编号为6的人出局，然后我们对剩下5个人重新编号。

第4次，0 1 2 3 4 x x x，30 % 5 = 0，第5个人出局，即编号为4的人出局，原始编号为4的人出局，然后我们对剩下4个人重新编号。

……

如果我们可以把第 $j (2 \leq j \leq n) j(2\leq j\leq n)$ j(2≤j≤n) 次每个人的编号还原到第 $j - 1 j -1$ j−1 次每个人的编号，我们就可以一层一层倒推，我们来看一下，上下层的编号有什么关系。

第1次编号范围为 $00$ 0 ~ $(n - 1) (n-1)$ (n−1)，第1个出列的人编号一定是 $(m - 1) % n (m-1)\% n$ (m−1)%n （不写成 $m % n - 1 m\% n-1$ m%n−1 是为了防止 $m % n = 0 m\% n=0$ m%n=0），设为 $k - 1 k - 1$ k−1，则编号变换到第2次的过程如下：

$00$ 0	$11$ 1	$22$ 2	…	$k - 2 k - 2$ k−2	$k - 1 k - 1$ k−1	$k k$ k	$k + 1 k + 1$ k+1	…	$n - 2 n - 2$ n−2	$n - 1 n - 1$ n−1
$- k -k$ −k	$1 - k 1 - k$ 1−k	$2 - k 2 - k$ 2−k	…	$- 2 -2$ −2		$00$ 0	$11$ 1	…	$n - 2 - k n - 2 - k$ n−2−k	$n - 1 - k n - 1 - k$ n−1−k
$n - k n - k$ n−k	$n + 1 - k n + 1 - k$ n+1−k	$n + 2 - k n + 2 - k$ n+2−k	…	$n - 2 n - 2$ n−2		$00$ 0	$11$ 1	…	$n - 2 - k n - 2 - k$ n−2−k	$n - 1 - k n - 1 - k$ n−1−k

可以看到变换的时候都先减掉 $k k$ k，再对前面部分加上 $n n$ n，所以，为了使第2次的每个编号还原到第1次，每个编号加上 $k k$ k，然后膜 $n n$ n，就可以了，设第2次某个编号为 $x x$ x，则 $(x + k) % n = (x + m % n) % n = (x + m) % n (x+k)\%n=(x+m\%n)\%n=(x+m)\%n$ (x+k)%n=(x+m%n)%n=(x+m)%n，即 $(x + m) % n (x+m)\%n$ (x+m)%n 就是该编号对应的第1次的编号。

第2次编号范围为 $00$ 0 ~ $(n - 2) (n-2)$ (n−2)，第1个出列的人编号一定是 $(m - 1) % (n - 1) (m - 1)\% (n-1)$ (m−1)%(n−1)，变换的时候都先减掉 $(m - 1) % (n - 1) + 1 (m - 1)\% (n-1) + 1$ (m−1)%(n−1)+1，再对前面部分加上 $n - 1 n-1$ n−1，所以，为了使第3次的每个编号还原到第2次，每个编号加上 $(m - 1) % (n - 1) + 1 (m - 1)\% (n-1) + 1$ (m−1)%(n−1)+1，然后膜 $n - 1 n-1$ n−1，就可以了，设第3次某个编号为 $x x$ x，则 $(x + (m - 1) % (n - 1) + 1) % (n - 1) = (x + m) % (n - 1) (x+(m - 1)\% (n-1) + 1)\%(n-1)=(x+m)\%(n-1)$ (x+(m−1)%(n−1)+1)%(n−1)=(x+m)%(n−1)，即 $(x + m) % (n - 1) (x+m)\%(n-1)$ (x+m)%(n−1) 就是该编号对应的第2次的编号。

现在就能看出规律了，设某次的某个编号为 $x x$ x，上次剩余 $n n$ n 个人，则 $(x + m) % n (x+m)\%n$ (x+m)%n 就是上一次的编号，我们知道最后一次的编号肯定是0，因为只剩了一个人，将这个0不断地往上一次变换，直到变换到第1次，就可以得出结果。

设最开始有 $n n$ n 个人， $A [i] A[i]$ A[i] 表示最后那个胜利者在剩余 $i i$ i 个人时的编号，则存在以下递推式：

$A [1] = 0 A[1] = 0$ A[1]=0

$A [2] = (A [1] + m) % 2 A[2] = (A[1] + m) \% 2$ A[2]=(A[1]+m)%2

$. . . ...$ ...

$A [i] = (A [i - 1] + m) % i (2 \leq i \leq n) A[i] = (A[i - 1] + m) \% i (2\leq i\leq n)$ A[i]=(A[i−1]+m)%i(2≤i≤n)

java 代码如下：

public void Yue1(int n, int m) {
    int r = 0;
    for (int i = 2; i <= n; i++) {
        r = (r + m) % i;
    }
    System.out.println(r + 1);
}

处决顺序问题

上面已经导出了相邻两次报数的编号之间的关系，我们再来看每次退出的人的编号，假设某次剩余 $i i$ i 个人，则这次退出的人的编号为 $(m - 1) % i (m-1)\% i$ (m−1)%i，我们只需要把这个编号倒推到第一次即可，所以这种方式代码如下：

public void Yue4(int n, int m) {
    int result = m % n - 1;
    System.out.print(result + 1);
    for (int i = n; i >= 2; i--) {
        result = (m - 1) % (i - 1);
        for (int j = i; j <= n; j++) {
            result = (result + m) % j;
        }
        System.out.print("->" + (result + 1));
    }
}

当然你可以使用队列做，当然不是真的队列，一个标志位数组即可：

public void Yue2(int n, int m) {
    int idx = 0, cnt = 1, pout = 0;
    int[] vis = new int[n + 10];
    while (pout != n) {
        if (1 == vis[idx]) {
            idx = (idx + 1) % n;
            continue;
        }

        if (cnt % m == 0) {
            vis[idx] = 1;
            pout++;
            if (cnt == m){
                System.out.print(idx + 1);
            }else {
                System.out.print("->" + (idx + 1));
            }
        }

        idx = (idx + 1) % n;
        cnt++;
    }
}

参考博客：

详细阐述约瑟夫环问题（报数出队问题）

ACM模版——约瑟夫问题（出列顺序 + 最后一个）

约瑟夫环（数学高效率解法，很详细）

约瑟夫环问题的两种解法（详解）

文章最后发布于: 2018-11-03 15:52:44

约瑟夫问题