约瑟夫环问题的两种解法(循环链表、递推)

文章目录
  1. 1. 循环链表模拟
  2. 2. 数学方法求解
  3. 3. 完整代码
  4. 4. 参考文章

对于n个人,每报数到m的人出列的约瑟夫环问题,一般是需要我们求最后幸存者,有两种解决方法:循环链表模拟,数学方法求解。

循环链表模拟

此方法使用单向循环链表求解,效率较低。一共有n个人,每报到m的人出列,即是说每在链表上滑动两次就删去一个结点,因为要求最后的幸存者,所以一共需要删去n-1个结点,那么此方法的时间复杂度为O(nm),空间复杂度O(n),为链表的开销。
代码:

struct Node
{
    int data;
    Node *next;
    Node(int ddata = -1, Node *nnext = NULL) : data(ddata), next(nnext) {}
};

//use linkedlist to solve
int solve(int n, int m)
{
    //build a one-way linkedlist
    Node *header = new Node(n);
    for (int i = n - 1; i > 0; --i)
        header = new Node(i, header);
    //print(header);

    //make linkedlist an circular one-way linkedlist
    Node *cur = header;
    while (cur->next)
        cur = cur->next;
    cur->next = header;

    //delete m-th node until the linkedlist remains a node
    cur = header;
    while (cur->next != cur) //when cur's next node is itself,loop stop.
    {
        for (int i = 0; i < m - 2; ++i)
            cur = cur->next;
        Node *tmp = cur->next;
        cur->next = cur->next->next;
        //cout << "delete: " << tmp->data << endl;
        delete tmp;
        cur = cur->next;
    }
    int ret = cur->data;
    delete cur;
    return ret;
}

需要注意的是,循环结束的条件是循环链表只剩下一个next连接着自己的结点时,即为问题中的幸存者。

数学方法求解

首先我们要明确两个概念,顺序编号和逻辑编号。

  1. 顺序编号即为根据顺序编的号码,会因有人出列而改变;
  2. 逻辑编号即为最开始时的编号,是逻辑上的,不会因为有人出列而改变。
    以n=5,m=2的5人约瑟夫环为例,按0-4(逻辑)编号:
    逻辑编号:0 1 2 3 4
    顺序编号:0 1 2 3 4
    按照规矩,数到2的人(即为逻辑编号1的人)出列后,此时环为(以x补位):
    逻辑编号:0 x 2 3 4
    顺序编号:0 x 1 2 3
    以逻辑编号为2的人为例,在最开始的时候此人的顺序编号为2,而在出列一人后,此人的顺序编号变为了1,可以看到在有一个人出列后,逻辑编号没变,而顺序编号跳过了那个被出列的人,按顺序重新编号了。理解这两个概念有助于理解后面的内容。

数学方法求解的本质是逆推整个过程,求得最后幸存者在初始环中的编号(每出列一个人,顺序编号改变)。

依旧是n=5,m=2的例子,先普通地模拟一遍;

开始时:
逻辑编号:0 1 2 3 4
顺序编号:0 1 2 3 4

出列一人:
逻辑编号:0 x 2 3 4
顺序编号:0   1 2 3
除去x后的逻辑编号:0 2 3 4

出列二人:
逻辑编号:0 x 2 x 4
顺序编号;0   1   2
除去x后的逻辑编号:0 2 4

出列三人:
逻辑编号:x x 2 x 4
顺序编号:    0   1
除去x后的逻辑编号:2 4

出列四人:
逻辑编号:x x 2 x x
顺序编号:    0
除去x后的逻辑编号:2

按出列顺序,出列者的逻辑编号为:1 3 0 4
顺序编号为:1 2 0 1

可以看出,由于每次出列的人的顺序编号都不同,导致我们不能简单地找到规律。
我们可以处理一下,在每次有人出列后,将出列的人的下一个人“滚动”到环的开头(类似整个数组向左滚动m个位置),再模拟一遍过程,为了方便对比,这里把无滚动时的逻辑编号也列在了一起:

开始时:
逻辑编号:0 1 2 3 4
顺序编号:0 1 2 3 4

出列一人:
逻辑编号:2 3 4 0(有滚动)
逻辑编号:0 2 3 4(无滚动)
顺序编号:0 1 2 3

出列二人:
逻辑编号:4 0 2(有滚动)
逻辑编号:0 2 4(无滚动)
顺序编号;0 1 2

出列三人:
逻辑编号:2 4(有滚动)
逻辑编号:2 4(无滚动)
顺序编号:0 1

出列四人:
逻辑编号:2(有滚动)
逻辑编号:2(无滚动)
顺序编号:0

按出列顺序,出列者的逻辑编号为:1 3 0 4
出列顺序编号为:1 1 1 1

经过这样处理,每次出列的人的顺序编号都是1。
首先我们理理思路,对于数组或者链表模拟的方法,因为使用了额外的空间,我们可以保留逻辑编号的信息。但是数学方法没有额外的空间,所以此时逻辑编号几乎无用,但我们最后要求幸存者的逻辑编号。最后的幸存者是逻辑编号为2的人,在整个过程中这个幸存者的顺序编号一直在变化,如果我们能够将最后幸存者的顺序编号(即是出列四人的情况,幸存者顺序编号为0),还原成开始时的逻辑编号(即为最开始时,顺序编号2的人),再根据开始时逻辑编号与顺序编号差1的规律,就能通过逆推整个过程,得到幸存者的逻辑编号。
通过找规律能发现,两轮之间的顺序编号满足递推公式(对任一人):此轮顺序编号 = (上轮顺序编号 + m)% 此轮人数,m为题目中“报道第m的人出列”的m。
写得严谨一点:

令f[i]表示i个人玩游戏报m的人出列最后胜利者的编号:
f[1] = 0
f[i] = (f[i-1] + m)%i 

注意:

  1. 由于整个过程是逆推,所以初始时的f[1]对应推到最后只剩下一个人时该人的顺序编号(其实就是最后幸存者的顺序编号,为0)。
  2. 在逆推的过程中,这个i是一直在变化的,因为每轮都有人出列,人数自然会变化。
  3. 整个数学方法的核心为顺序编号、逻辑编号的对应关系,以及递推的思想。滚动的处理方式只是为了更好地理解整个过程。

代码:

int solve2(int n, int m)
{
    int ans = 0;
    for (int i = 2; i <= n; ++i)
        ans = (ans + m) % i;
    return ans + 1;//对齐逻辑编号,逻辑编号从1开始,顺序编号从0开始
}

完整代码

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node *next;
    Node(int ddata = -1, Node *nnext = NULL) : data(ddata), next(nnext) {}
};

void print(Node *header)
{
    while (header)
    {
        cout << header->data << " ";
        header = header->next;
    }
    cout << endl;
}

//use linkedlist to solve
int solve(int n, int m)
{
    //build a one-way linkedlist
    Node *header = new Node(n);
    for (int i = n - 1; i > 0; --i)
        header = new Node(i, header);
    //print(header);

    //make linkedlist an circular one-way linkedlist
    Node *cur = header;
    while (cur->next)
        cur = cur->next;
    cur->next = header;

    //delete m-th node until the linkedlist remains a node
    cur = header;
    while (cur->next != cur) //when cur's next node is itself,loop stop.
    {
        for (int i = 0; i < m - 2; ++i)
            cur = cur->next;
        Node *tmp = cur->next;
        cur->next = cur->next->next;
        //cout << "delete: " << tmp->data << endl;
        delete tmp;
        cur = cur->next;
    }
    int ret = cur->data;
    delete cur;
    return ret;
}

//use mathematical method to solve
int solve2(int n, int m)
{
    int ans = 0;
    for (int i = 2; i <= n; ++i)
        ans = (ans + m) % i;
    return ans + 1;
}

int main()
{
    int n, m;
    while (scanf("%d%d", &n, &m) == 2)
    {
        if (n == 0 && m == 0)
            break;
        printf("%d,%d\n", solve(n, m), solve2(n, m));
    }

    return 0;
}

参考文章

  1. http://tingyun.site/2018/04/26/%E7%BA%A6%E7%91%9F%E5%A4%AB%E7%8E%AF%E9%97%AE%E9%A2%98%E8%AF%A6%E8%A7%A3/
  2. https://blog.csdn.net/wusuopubupt/article/details/18214999
  3. https://blog.csdn.net/yanweibujian/article/details/50876631
分享到