本题为经典约瑟夫问题的变形问题，思路类似，但解法并不相同，考察对递推状态和相应算法的掌握程度。

题目描述

题目大意

假设有 k 个好人和 k 个坏人站成一圈，且 k 个好人紧密相邻标号为 1 到 k，k 个坏人紧密相邻标号为 k+1 到 2k。从 1 开始报数，报到 m 的时候相应的报数人被处死，则总会有特殊的 m 使得在 k 个坏人被处死前不会有一个好人死亡，求这样的 m 最小值。

输入

有多组输入数据，每组数据只包含一个数字即 k 的值，而且 k 为不大于 14 的正整数。当输入为 0 的时候表示输入结束。

示例输入为：

1
2
3

3
4
0

输出

输出与每个输入值对应的结果，每个结果各占一行。

对应的示例输出为：

1
2

5
30

知识点解析

约瑟夫问题的原题目为：有 n 个人站成一环，标号分别为 1 到 n，从 1 号开始报数，报到 m 时处死相应的报数人，直到剩下最后一个人时停下。n 和 m 已知的情况下，求最后是哪一个编号的人会存活。 这是一个经典的程序问题，常常出现在入门各种程序竞赛试题中。一般来说有两种解法，分别是模拟法和递推公式法。模拟法虽然直观，但是效率太低不适合处理大规模数据，这里注意讲一下递推法。

解题过程为： 不妨假设 n 个人的编号为 0 到 n - 1，这样方便求余数操作，在用循环队列模拟环的时候更方便。第一个被处死的人是下标为 m - 1 的人，而后从下标 m 开始重新计数，即新的队列下标变成了 0 到 n - 2，且原下标 m 变成了新的下标 0，之后循环计数。这样不断重复，直到最后队列剩余一个元素，且它的下标为 0。 如果用 f(x) 表示有 x 个元素的时候，最后存活元素的编号，那么有： f(1) = 0； 在不考虑下标越界的情况，每次向上推断下标都是在存活元素前面加上 m - 1 个元素，而考虑到下标从 0 开始，则实际递推公式为 f(i) = f(i-1) + m，这时在考虑下标边界问题，将结果处理为 f(i) = (f(i-1) + m) % i； 最后，本题的结果就是 f(n) + 1。

写成 Java 代码为：

1
2
3
4
5
6
7
8

int joseph(int n,int m) {
    int re = 0;
    for (int i = 2; i <= n; i++) {
        re = (re + m) % i;
    }

    return re + 1;
}

解题思路

本题解法和原有问题很像，但绝不相同，主要体现在结果关注点不同导致递推的思路的迥异。 在处死 k 个坏人的过程中，实际根本不必关心坏人的下标变化，只是关心处死的下标是否落在前 k 个编号的范围内即可。而且，最后所求结果也和下标无关，故可以任意指定一个方便使用的下标方案，而不变一定遵守题设。 不妨假设约瑟夫问题中的 n 的值为 2 * k，且所有人下标从 0 开始，直到 n - 1。这样，就要保证前 k 个操作步骤内的处死目标下标不小于 k 即可； 因为不关心坏人下标的变化，可以假设处死一个坏人之后他后面的坏人依次顶替了前面一个的编号，使得队列编号总数减一，但是前 k 个元素编号不变； 这样每次要处死的人员的下标可以由上一步的下标加上 m - 1 得到，而为了保证下标不越界还要对总人数取余。

用递推式表示为： 假设第 i 步的处死人员的编号为 f(i)； 因为从第一个元素计数，为了便于计算假设 f(0) = 0（但实际没有处死编号 0）； 而后下一步处死的人的编号可以递推得到 f(i) = (f(i-1) + m - 1) % (n - i + 1)，这其中 n - i + 1 表示第 i 步处死人时总的队列人数。

本题数据范围不大，可以暴力求解：从 m 为 1 开始，不断验证上述条件，保证从第 1 步到第 k 步中，所有下标元素都不小于 k 即可，如果小于则说明当前的 m 不符合要求，要再求下一个更大的 m。

最后，应该注意对本题中的数据进行打表，防止重复计算引起的超时。

代码展示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

import java.util.Scanner;

public class Main {

    public static final int[] buf = new int[14];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int k = in.nextInt();
            if (k == 0) break;

            if (buf[k] != 0) {
                System.out.println(buf[k]);
            } else {
                int n = k + k;
                int tmp = 0;

                int re = 1;
                for (int i = 1; i <= k; i++) {
                    tmp = (tmp + re - 1) % (n - i + 1);

                    if (tmp < k) {
                        i = 0;
                        tmp = 0;
                        re++;
                    }
                }
                buf[k] = re;
                System.out.println(re);
            }
        }
    }
}

参考

约瑟夫环问题