Last Order
0%

约瑟夫问题

发表于 更新于 分类于

问题描述：n个人（编号1~n)，从1开始报数，报到m的退出，剩下的人继续从1开始报数。求胜利者的编号

分析：

从问题来看，首先我们假设有个数组，那么第一圈(0到n)的报数结束之后，剩下的人继续报数，可是第一圈出去的人仍然在数组里面，这样肯定会影响到编号的计算，一个方法就是出去的人的位置清0，比如第一次出去的是arr[2]，那么arr[2]的值就变成0，下一次计算的时候忽略掉这个标记的位置。

如果不用数组，整个遍历的过程就很容易想起来链表，退出的人则直接移除节点，剩下的人继续报数那么意思是最后一个人的next指针指向第一个人，这样就是符合题目的流程。注意循环结束的条件。

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
43
44
45
46
47
48
49
50
51
52
53
54
public class Test {

    public static void main(String[] args) {
        System.out.println("" + getLive(6, 3));
    }

    private static int getLive(int n, int m) {
        if (n == 1) {
            return 1;
        }
        if (m == 1) {
            return n;
        }
        Node head = new Node(0);
        Node temp = head;
        for (int i = 1; i < n; i++) {
            Node node = new Node(i);
            temp.next = node;
            temp = node;
        }
        temp.next = head;


        Node current = head;
        Node prev = null;
        int i = 1;
        while (current.next != current) {
            if (i == m) {  //报数到m的时候，移除这个节点
                removeNode(prev, current);
                i = 0;
            }
            prev = current;
            current = current.next;  
            i++;
        }
        System.out.println();
        return current.data + 1;
    }

    private static void removeNode(Node prev, Node current) {
        System.out.print(" removeNode " + current.data);
        prev.next = current.next;
        current = null;
    }

    static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }
    }
}

下面是数学上的解法，我们假设有5个人参与，每报3则出列，具体的过程如下：

1 12345 – 3出列，从4号继续开始报数

2 4512 – 1出列，从2继续开始报数

3 245 – 5出列，24继续报数

4 24 – 2出列，剩下一个4

5 4

n个人参与的时候，出列一个人，剩下的n-1继续构成新的约瑟夫环，因此n个人的问题最后肯定可以递归的转化成1个人的问题，最后这个人在1个人的情况下就是最后生存的人，它此时的编号是1，问题是这最后一个人的在n人环里面的编号是多少？

观察上面的步骤，5个人的约瑟夫环，3出列后，让4号做开头，重新构成的新的4个人的环，它们有这样一个对应关系，

5人环里面的编号4的那个人，变成了4人环里面编号1的人

5人环里面的编号5的那个人，变成了4人环里面编号2的人

5人环里面的编号1的那个人，变成了4人环里面编号3的人

基于这个过程，我们可以做出这样一个推导f(5) = f(4) + 3 % 5,其中f(5)表示5人环里面的人的编号，f(4)表示4人环里面的人的编号，这个公式表示它们之间的对应关系。除5因为这是5人环。

同样的，我们也可以得出f(4) = (f(3) + 3) % 4，f(3) = (f(2) + 3) %3，f(2) =( f(1) + 3)%2，f(1) = 1 ;

在1人的情况下，生存的是人编号一定是1，

2人的时候，它对应的编号是 1+3 % 2 = 2

3个人的时候，生存的人对应的编号是2+3%3 = 2

…

n个人的时候，对应的是f(n) = f(n-1) + 3 % n,

我们把m带入进去，f(n) = (f(n-1) + m) % n 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static int joseph(int n, int m) {
    if (n == 1) {
        return 1;
    }
    if (m == 1) {
        return n;
    }

    int s = 1;  //n=1的时候的值
    for (int i = 2; i < n+1; i++) {
        //一直循环到 i = n ，就是n个人的时候的编号
        s = (s + m) % i;
        if (s == 0) {  //编号没有0，修正为n
            s = i;
        }
    }
    return s;
}

结果与上面相同。