题解：约瑟夫环问题

发表于 更新于 分类于 阅读次数：
本文字数： 5.1k 阅读时长 ≈ 5 分钟

约瑟夫是一个无聊的人

题解：约瑟夫环问题

Guderian出品

题目背景

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲在一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。问题是，给定了总人数n和报数值m，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

题目描述

n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

输入格式

n m

输出格式

出圈的编号

输入输出样例

输入 #1

1
10 3

输出 #1

1
3 6 9 2 7 1 8 5 10 4

说明/提示

m, n ≤ 100

解题方法

解法一：模拟 + 指针模拟链表

时间复杂度：$O(m * n)$

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
//Run on C++
#include <cstdio>
using namespace std;

struct node
{
    int data;
    node* next;
};

int n, m;
node *head, *p, *r;  //head为头结点，p表示新节点，r表示当前节点

int main()
{
    scanf("%d%d", &n, &m);
    head = new node;
    head->data = 1;
    head->next = NULL;
    r = head;
    for (int i = 2; i <= n; i++)
    {
        p = new node;
        p->data = i;
        p->next = NULL;
        r->next = p;
        r = p;
    }
    r->next = head; r = head; //使链表首尾相连
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m - 2; j++)    r = r->next;
        printf("%d ",r->next->data);
        r->next = r->next->next;
        r = r->next;
    }
    return 0;
}

解法二：模拟 + 数组模拟链表

时间复杂度：$O(m * n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//Run on C++
#include <cstdio>

int nxt[110];
int n, m;

int main()
{
    scanf("%d%d", &n,&m);
    for (int i = 1; i <= n; i++) nxt[i] = i + 1;
    nxt[n] = 1; //使链表首尾相连
    int pos = 1; //当前位置
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m - 2; j++) pos = nxt[pos];
        printf("%d ", nxt[pos]);
        nxt[pos] = nxt[nxt[pos]];
        pos = nxt[pos];
    }
    return 0;
}

解法三：模拟 + 数组

时间复杂度：$O(m * n)$

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
//Run on C++
#include <cstdio>

int m, n;
int a[110];

int main()
{
    scanf("%d%d", &n, &m);
    int t = 1, i = 1, cnt = 0; //t为出去的人的数量，i为数组下标索引，cnt为计数器
    while(t <= n)
    {
        if(i == n + 1) i = 1; //到了最后一个重新从第一个开始
        if(a[i] == 0)
        {
            cnt++;
            if(cnt == m) //到了第m个开始新一轮计数
            {
                a[i] = 1;
                cnt = 0;
                t++;
                printf("%d ",i);
            }
        }
        i++;
    }
    return 0;
}

解法四：模拟 + 队列

时间复杂度：$O(m * n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//Run on C++
#include <cstdio>
#include <queue>
using namespace std;

queue <int> q;
int n,m;

int main()
{
    scanf("%d%d",&n, &m);
    for(int i = 1; i <= n; i++) q.push(i);
    while(!q.empty())
    {
        for(int i = 1; i < m; i++) q.push(q.front()), q.pop(); //每数一个就把它放到队尾
        printf("%d ",q.front());
        q.pop(); //队头出圈
    }
    return 0;
}

注：

  • 你也可以不用stl提供的队列，自己编写一个队列
  • 你也可以用stl提供的双端队列deque，不过据笔者观察除了装逼效果之外并没有其他用处

解法五：递归（运用递推公式）

时间复杂度：$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//Run on C++
#include <cstdio>

int n, m;

int Josephus(int x, int y, int z)
{
    if (z == 1) return (y - 1) % x;
    return (Josephus(x - 1, y, z - 1) + y) % x;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) printf("%d ", Josephus(n, m, i) + 1);
    return 0;
}

解法六：迭代（运用递推公式）

时间复杂度：$O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//Run on C++
#include <cstdio>

int n, m;

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int ans;
        for (int j = 1; j <= i; j++)
            if (j == 1) ans = (m - 1) % (n - i + j);
            else ans = (ans + m) % (n - i + j);
        printf("%d ", ans + 1);
    }
    return 0;
}

推导递推公式*

以解法五为例，在递归函数部分代码中

1
2
3
4
5
int Josephus(int x, int y, int z)
{
    if (z == 1) return (y - 1) % x;
    return (Josephus(x - 1, y, z - 1) + y) % x;
}

x代表总人数，y代表每次报y的人出列，z是次数，该函数可以求第z次出圈的人的编号。

举个例子：总人数x为6人，从1开始，每报到3就出圈（y = 3）

初始情况：1 2 3 4 5 6

通过递推的方式使第一个幸运观众出圈之后：1 2 4 5 6

此时，这些编号已经不能组成一个环，但是2和4之间还是连着的，且下一次报数将从4开始。然而，之后的报数将总要考虑3处的空位问题。

如何避免空位对报数所造成的影响？

可以将剩下的4个数重新组合成一个新的环，这样报数的时候就不必在意3的空缺了。但是新产生的环的数字并非连续的，报数时不能直接用+ y再% x的简单递推方式，这下真令人头大。

如何使新环上的编号依然能够递推？

可以建立一种有确定规则的映射，要求映射之后的数字可以递推，且可以将在新环中继续按原规则报数得到的结果逆推出在旧环中的对应数字。

阻止我们使用老办法递推的因素就是3号出圈之后产生的新环编号不连续，那么，我们可以通过建立某种映射，使得新环的编号依然连续，方便我们继续使用递推的方法。

原始：1 2 3 4 5 6

旧环：1 2 _ 4 5 6

新环：4 5 _ 1 2 3

正如你所见，相比于旧环中2和4之间被割裂开，新环的5和1之间在对5取余的基础上是完美连续的，这就意味着我们可以继续从新环的1（即旧环的4）开始实施我们的递推方法。且只要推导出新环与旧环的映射关系，就能从在新环中报数的结果得知在旧环中的报数结果。

对于第二个幸运观众：

旧环：1 2 _ 4 5 *6

新环：4 5 _ 1 2 *3

如何从新环的3得到旧环的6呢？其实可以简单地逆推回去 : 新环是由(旧环中编号 - 报数值) % 旧环总人数得到的，所以逆推时可以由(新环编号 + 报数值) % 旧环总人数得到。

如：(3 + 3) % 6 = 0

咦？奇怪怎么是0？不是应该是6吗？这就涉及到一个进位的问题。由于旧环的编号为1~6，而我们在新环依然保留了1~5的编号并确保5和1之间在对5取余的基础上连续，这就导致了5 % 5 = 0，也就是说5与0是无法区分的。因此，虽然实际上旧环编号为6的幸运观众出圈，但是我们的计算结果依然不可避免地把它对6取余，得到一个看似奇怪却又顺理成章的0。

如何避免错误地把最大的数算成0的情况？

把所有数减1即可，最后输出结果的时候再加上1。让我们再来一遍：

对于第二个幸运观众：

旧环：0 1 _ 3 4 *5

新环：3 4 _ 0 1 *2

从新环推出旧环的幸运观众：(2 + 3) % 6 = 5

由上得，原序列x中第二次出圈的编号可以由新序列x - 1第一次出圈的编号通过特定的逆推运算得出。即在以y为出环报数值的约瑟夫环中，x人环的第z次出环编号可以由x - 1人环中的第z - 1次出环编号通过也定的运算推出。

幸运的是，第一次出环的编号是可以直接求出的，也就是说，对于任意次出环的编号，我们可以将之一直转化为第一次出环的编号问题，再一一迭代求出；也可以把第一次出环的编号作为递归基础，通过递归求出。

因此我们可以写出Josephus函数的递推公式如下：

结束语

以上就是关于约瑟夫环问题的六种解法，并送上调试过的C++代码，作者水平不高，将就看看吧 ╮(╯_╰)╭

*. 参考该网站，感谢作者的写作 ↩

本文标题:题解：约瑟夫环问题

文章作者:G-SS-Hacker

发布时间:2019年08月07日 - 20:59:28

最后更新:2021年01月19日 - 10:33:30

原始链接:https://G-SS-Hacker.github.io/题解：约瑟夫环问题/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。