约瑟夫问题

发表于 | 分类于 | 评论： | 阅读次数：

背景简介

约瑟夫问题（又是也称为约瑟夫置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是一开始要站在什么地方才能避免自杀？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

——摘自约瑟夫问题百度百科

问题描述

约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，从被杀掉的下一位重新开始报数，第M个将被杀掉，复现这个过程，最后剩下一人，其余人都将被杀掉。例如N=6, M=5，被杀掉的顺序是：5，4，6，2，3，1.

解法

使用循环单链表模拟整个过程。

代码

python：

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# josephus.py
import sys

class Node(object):
    '''
    构造节点
    '''
    def __init__(self, value):
        self.value = value
        self.next = None

def create_link_list(number):
    '''
    创建数目为number的循环单链表
    '''
    head = Node(1)
    cur = head
    for i in range(2, number+1):
        node = Node(i)
        cur.next = node
        cur = cur.next

    cur.next = head
    return head

def josephus(number, offset):
    '''
    使用循环单链表复现约瑟夫问题
    '''
    node = create_link_list(number)
    cur = node

    if offset == 1:
        for i in range(number):
            print(i+1)
        return

    while node.next != node:
        for i in range(offset-1):
            pre = node
            node = node.next

        print(node.value)
        pre.next = node.next
        node = node.next
    print(node.value)
import sys

class Node(object):
    '''
    构造节点
    '''
    def __init__(self, value):
        self.value = value
        self.next = None

def create_link_list(number):
    '''
    创建数目为number的循环单链表
    '''
    head = Node(1)
    cur = head
    for i in range(2, number+1):
        node = Node(i)
        cur.next = node
        cur = cur.next

    cur.next = head
    return head

def josephus(number, offset):
    '''
    使用循环单链表复现约瑟夫问题
    '''
    node = create_link_list(number)
    cur = node

    if offset == 1:
        for i in range(number):
            print(i+1)
        return

    while node.next != node:
        for i in range(offset-1):
            pre = node
            node = node.next
        print(node.value)
        pre.next = node.next
        node = node.next
    print(node.value)

if __name__ == '__main__':
    number = int(sys.argv[1])
    offset = int(sys.argv[2])
    josephus(number, offset)

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(.venv) ➜  约瑟夫问题 git:(master) ✗ python josephus.py 6 4
4
2
1
3
6
5
(.venv) ➜  约瑟夫问题 git:(master) ✗ python josephus.py 3 2
2
1
3
(.venv) ➜  约瑟夫问题 git:(master) ✗ python josephus.py 3 1
1
2
3
(.venv) ➜  约瑟夫问题 git:(master) ✗ python josephus.py 3 5
2
3
1
(.venv) ➜  约瑟夫问题 git:(master) ✗ python josephus.py 1 3
1

c++

code:

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
55
56
57
58
59
60
//josephus.cpp
#include <iostream>
using namespace std;

typedef struct _LinkNode {
    int value;
    struct _LinkNode *next = NULL;
} LinkNode;

LinkNode* createNodeList(int total) {
    LinkNode* head = NULL;
    LinkNode* cur = NULL;

    head = (LinkNode*)malloc(sizeof(LinkNode));
    head->value = 1;
    cur = head;

    for (int i=2; i<=total; i++) {
        LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
        node->value = i;
        cur->next = node;
        cur = cur->next;
    }
    cur->next = head;

    return head;
}

void josephus(int number, int offset) {
    LinkNode* node = createNodeList(number);
    LinkNode* pre = NULL;
    LinkNode* next = NULL;

    if (offset == 1) {
        for (int i=1; i<=number; i++) {
            printf("%d\n", i);
        }
        return;
    }

    while (node != node->next) {
        for (int i=1; i<offset; i++) {
            pre = node;
            node = node->next;
        }
        printf("%d\n", node->value);
        next = node->next;
        pre->next = next;;
        free(node);
        node = next;
    }
    printf("%d\n", node->value);
    free(node);
}

int main(int argc, char *argv[]) {
    int number = atoi(argv[1]);
    int offset = atoi(argv[2]);
    josephus(number, offset);
}

编译：

1
g++ -o josephus josephus.cpp

运行：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(.venv) ➜  约瑟夫问题 git:(master) ✗ ./josephus 6 4
4
2
1
3
6
5
(.venv) ➜  约瑟夫问题 git:(master) ✗ ./josephus 3 2
2
1
3
(.venv) ➜  约瑟夫问题 git:(master) ✗ ./josephus 3 1
1
2
3
(.venv) ➜  约瑟夫问题 git:(master) ✗ ./josephus 3 5
2
3
1
(.venv) ➜  约瑟夫问题 git:(master) ✗ ./josephus 1 3
1

代码仓库参看 https://github.com/TiannV/Code/tree/master/2019/2月/约瑟夫问题