约瑟夫问题(Josephus Problem)

据说着名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人 开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。

UVA 133 305 402 10015

方法一、直接模拟求解

只要画两个圆圈就可以让自己与朋友免于死亡游戏,这两个圆圈内圈是排列顺序,而外圈是自杀顺序,如下图所示:

josephus

使用程式来求解的话,只要将阵列当作环状来处理就可以了,在阵列中由计数1开始,每找到三个无资料区就填入一个计数,直而计数达41为止,然后将阵列由索引1开始列出,就可以得知每个位置的自杀顺序,这就是约瑟夫排列,41个人而报数3的约琴夫排列如下所示:

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

由上可知,最后一个自杀的是在第31个位置,而倒数第二个自杀的要排在第16个位置,之前的人都死光了,所以他们也就不知道约琴夫与他的朋友并没有遵守游戏规则了。

 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
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <stdlib.h>
#define N 41
#define M 3

int main(void) {
    int man[N] = {0};
    int count = 1;
    int i = 0, pos = -1;
    int alive = 0;

    while(count <= N) {
        do {
            pos = (pos+1) % N;  // 环状处理
            if(man[pos] == 0)
                i++;

            if(i == M) {  // 报数为3了
                i = 0;
                break;
            }
        } while(1);

        man[pos] = count;
        count++;
    }

    printf("\n约琴夫排列:");
    for(i = 0; i < N; i++)
        printf("%d ", man[i]);
    printf("\n\n您想要救多少人?");
    scanf("%d", &alive);

    printf("\nL表示这%d人要放的位置:\n", alive);
    for(i = 0; i < N; i++) {
        if(man[i] <= N - alive) 	printf("D");
        else 	printf("L");
        if((i+1) % 5 == 0) 	printf("  ");
    }
    printf("\n");
    return 0;
}

也可以用队列模拟,首先把每个人依序进队,pop (m - 1)个人,push 到队尾,第 m 人直接出队。

时间复杂度分析:推广到n个人,间隔m个人杀一个,时间复杂度为O(mn)

方法二、动态规划

http://en.wikipedia.org/wiki/Josephus_problem

josephusDY

除去一人后,剩下来的人重新编号,就变成了子问题了。观察原编号和新编号的关系,可得到递推公式

1
2
f(n, m) = (f(n - 1, m) + m) % n
f(1, m) = 0
1
2
3
4
5
6
7
void josephus(int n, int m)
{
    int answer = 0;
    for (int i=1; i<=n; ++i)
        answer = (answer + m) % i;
    cout << "存活的人是" << answer << "号" << endl;
}