约瑟夫问题

1. 缘起

约瑟夫问题又叫约瑟夫环或丢手绢问题。故事据说发生在古罗马时期，在罗马人占领乔塔帕特后，39个犹太人与约瑟夫及他的朋友躲到一个洞中，他们宁愿死也不要被敌人抓到，于是约定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下1个人重新报数，直到所有人都自杀身亡为止。但是约瑟夫和他的朋友并不想死，就开始计算要站在什么地方才能避免被处决。

很显然如果想要逃避死亡，约瑟夫和他的朋友的死亡顺序应该是倒数第一和倒数第二，那么如何才能快速计算出这两个位置呢？

通过上图的推演大家应该是受到了启发，这个问题的本质其实就是循环链表的问题，围成一个圈之后，一个一个顺序报数，这就是相当于是在遍历循环链表。数到对应数字的出列，这就相当于是搜索并删除了循环链表中的一个节点！

2. 解决问题

既然处理约瑟夫问题需要用到循环链表，那么这个链表是选择带头结点的还是不带头结点的呢？

仔细分析之后相信大家选择的都是不带头结点的循环链表，因为现在的需求是通过最后一个数据节点直接找到链表中的第一个数据节点，如果是带头结点的循环链表，由于头结点不携带任何数据，在完成一轮遍历之后会对下一轮的衔接造成干扰（每次循环都需要跳过头结点）。

2.1 定义约瑟夫环类

在编写链表代码之前，我们先定义一个链表节点：

1
2
3
4
5
6
7
8
struct Node
{
    int data;
    int pos;
    Node* next;
    Node(int value, int index) : 
        data(value), next(nullptr), pos(index) {}
};

在这个节点中一共有三个成员，它们的作用依次是：

  • data：存储数据
  • pos：记录当前节点在链表中的位置（辅助调试用，可有可无）
  • next：存储当前节点的后继节点的地址

在C++中，结构体就是类，所以给节点类提供了一个构造函数，通过构造函数的初始化列表来初始化构造函数的参数。

有了链表节点之后，就可以定义一个约瑟夫环类了，通过这个类来解决约瑟夫怎么活下来的问题：

1
2
3
4
5
6
7
8
9
10
11
#pragma once
class JosephusCircle
{
public:
    JosephusCircle(int size);
    void display();
    void findSurvivor(int m);

private:
    Node* m_head;
};

在这个类中一共提供了3个函数：

  • 构造函数：参数size表示初始化到约瑟夫环中的元素数量
    • 随机生成size个元素，并将他们串联成一个单向循环链表
    • 这个单向循环链表没有头结点，只有数据节点
  • 遍历函数：通过display函数遍历链表中的节点
  • 幸存者函数：通过findSurvivor函数计算约瑟夫环中的元素的死亡顺序
    • 参数m表示数几个数死一个人

2.2 实现约瑟夫环类

在这个类中的核心函数就是void findSurvivor(int m)函数，该函数的核心处理思想如下：

  1. 根据头指针从第一个数据节点开始向后遍历
  2. 每个节点从1开报数，依次累加，数到m的节点需要从链表中删除
  3. 被删除的节点的后继节点重新从1开始报数
  4. 重复第2、3步，直到链表为空终止循环
  5. 链表中节点被删除的顺序就是约瑟夫环中的人的死亡顺序
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
#include <iostream>
using namespace std;

JosephusCircle::JosephusCircle(int size)
{
    if (size <= 0)
    {
        cout << "约瑟夫环人数必须大于0" << endl;
        return;
    }
    // 创建链表
    srand(time(0)); // 设置随机数种子
    m_head = new Node(0, 0);
    Node* p = m_head;
    for (int i = 1; i <= size; ++i)
    {
        Node* pNode = new Node(rand() % 100, i);
        p->next = pNode;
        p = pNode;
    }
    p->next = m_head->next;
}

void JosephusCircle::display()
{
    Node* p = m_head->next;
    if (p == nullptr)
    {
        cout << "空链表" << endl;
        return;
    }

    do
    {
        cout << "value: " << p->data << ", pos: " << p->pos << endl;
        p = p->next;
    }while (p != m_head->next);
}

void JosephusCircle::findSurvivor(int m)
{
    if (m_head->next == nullptr)
    {
        cout << "空链表" << endl;
        return;
    }
    Node* p = m_head;
    while (p->next != p)
    {
        for (int i = 1; i < m; ++i)
        {
            p = p->next;
        }
        Node* delNode = p->next;
        p->next = delNode->next;
        cout << "value: " << delNode->data << ", pos: " << delNode->pos << endl;
        delete delNode;
    }
    cout << "value: " << p->data << ", pos: " << p->pos << endl;
    delete p;
    delete m_head;
}

int main()
{
    JosephusCircle jos(10);
    cout << "遍历约瑟夫环: " << endl;
    jos.display();

    cout << "开始解决约瑟夫问题: " << endl;
    jos.findSurvivor(3);

    return 0;
}

运行程序，终端输出的信息如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
遍历约瑟夫环:
value: 50, pos: 1
value: 43, pos: 2
value: 29, pos: 3
value: 34, pos: 4
value: 64, pos: 5
value: 57, pos: 6
value: 18, pos: 7
value: 29, pos: 8
value: 43, pos: 9
value: 54, pos: 10
开始解决约瑟夫问题:
value: 29, pos: 3
value: 57, pos: 6
value: 43, pos: 9
value: 43, pos: 2
value: 18, pos: 7
value: 50, pos: 1
value: 29, pos: 8
value: 64, pos: 5
value: 54, pos: 10
value: 34, pos: 4

我们可以根据节点在循环链表中的pos位置进行推导（从1号位开始），从1开始数，数到3的人出列（自杀），具体过程如下：

从图2开始，红色的箭头表示链表中当前出列（自杀）的节点，次序为：3,6,9,2,7,1,8,5,10,4。这个结果和程序打印出的次序是相同的。

所以，对于约瑟夫而言，如果有10个人，他和他的朋友需要分别站在4号位和10号位就可以活下来了。如果是上文所说的41个人，在程序中带入参数，得到的两个位置分别是16号位和31号位。

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
遍历约瑟夫环:
value: 86, pos: 1
value: 33, pos: 2
value: 73, pos: 3
value: 44, pos: 4
value: 65, pos: 5
value: 45, pos: 6
value: 1, pos: 7
value: 45, pos: 8
value: 84, pos: 9
value: 93, pos: 10
value: 73, pos: 11
value: 18, pos: 12
value: 82, pos: 13
value: 26, pos: 14
value: 7, pos: 15
value: 7, pos: 16
value: 48, pos: 17
value: 69, pos: 18
value: 20, pos: 19
value: 98, pos: 20
value: 11, pos: 21
value: 26, pos: 22
value: 84, pos: 23
value: 9, pos: 24
value: 36, pos: 25
value: 60, pos: 26
value: 14, pos: 27
value: 70, pos: 28
value: 7, pos: 29
value: 2, pos: 30
value: 67, pos: 31
value: 17, pos: 32
value: 55, pos: 33
value: 56, pos: 34
value: 54, pos: 35
value: 5, pos: 36
value: 57, pos: 37
value: 16, pos: 38
value: 36, pos: 39
value: 67, pos: 40
value: 15, pos: 41
开始解决约瑟夫问题:
value: 73, pos: 3
value: 45, pos: 6
value: 84, pos: 9
value: 18, pos: 12
value: 7, pos: 15
value: 69, pos: 18
value: 11, pos: 21
value: 9, pos: 24
value: 14, pos: 27
value: 2, pos: 30
value: 55, pos: 33
value: 5, pos: 36
value: 36, pos: 39
value: 86, pos: 1
value: 65, pos: 5
value: 93, pos: 10
value: 26, pos: 14
value: 20, pos: 19
value: 84, pos: 23
value: 70, pos: 28
value: 17, pos: 32
value: 57, pos: 37
value: 15, pos: 41
value: 1, pos: 7
value: 82, pos: 13
value: 98, pos: 20
value: 60, pos: 26
value: 56, pos: 34
value: 67, pos: 40
value: 45, pos: 8
value: 48, pos: 17
value: 7, pos: 29
value: 16, pos: 38
value: 73, pos: 11
value: 36, pos: 25
value: 33, pos: 2
value: 26, pos: 22
value: 44, pos: 4
value: 54, pos: 35
value: 7, pos: 16
value: 67, pos: 31