如何解决约瑟夫环问题

约瑟夫环问题算是很经典的题了,估计大家都听说过,然后我就在一次笔试中遇到了,下面我就用 3 种方法来详细讲解一下这道题,最后一种方法学了之后保证让你可以让你装逼。

问题描述:编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈,从编号为 1 的士兵开始依次报数(1,2,3…这样依次报),数到 m 的 士兵会被杀死出列,之后的士兵再从 1 开始报数。直到最后剩下一士兵,求这个士兵的编号。

1、方法一:数组

在大一第一次遇到这个题的时候,我是用数组做的,我猜绝大多数人也都知道怎么做。方法是这样的:

用一个数组来存放 1,2,3 … n 这 n 个编号,如图(这里我们假设n = 6, m = 3)

然后不停着遍历数组,对于被选中的编号,我们就做一个标记,例如编号 arr[2] = 3 被选中了,那么我们可以做一个标记,例如让 arr[2] = -1,来表示 arr[2] 存放的编号已经出局的了。

然后就按照这种方法,不停着遍历数组,不停着做标记,直到数组中只有一个元素是非 -1 的,这样,剩下的那个元素就是我们要找的元素了。我演示一下吧:

这种方法简单吗?思路简单,但是编码却没那么简单,临界条件特别多,每次遍历到数组最后一个元素的时候,还得重新设置下标为 0,并且遍历的时候还得判断该元素时候是否是 -1。感兴趣的可以动手写一下代码,用这种数组的方式做,千万不要觉得很简单,编码这个过程还是挺考验人的。

这种做法的时间复杂度是 O(n * m), 空间复杂度是 O(n);

2、方法二:环形链表

学过链表的人,估计都会用链表来处理约瑟夫环问题,用链表来处理其实和上面处理的思路差不多,只是用链表来处理的时候,对于被选中的编号,不再是做标记,而是直接移除,因为从链表移除一个元素的时间复杂度很低,为 O(1)。当然,上面数组的方法你也可以采用移除的方式,不过数组移除的时间复杂度为 O(n)。所以采用链表的解决方法如下:

1、先创建一个环形链表来存放元素:

2、然后一边遍历链表一遍删除,直到链表只剩下一个节点,我这里就不全部演示了

代码如下:

// 定义链表节点
class Node{
    int date;
    Node next;

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

核心代码

    public static int solve(int n, int m) {
        if(m == 1 || n < 2)
            return n;
        // 创建环形链表
        Node head = createLinkedList(n);
        // 遍历删除
        int count = 1;
        Node cur = head;
        Node pre = null;//前驱节点
        while (head.next != head) {
            // 删除节点
            if (count == m) {
                count = 1;
                pre.next = cur.next;
                cur = pre.next;
            } else {
                count++;
                pre = cur;
                cur = cur.next;
            }
        }
        return head.date;
    }

    static Node createLinkedList(int n) {
        Node head = new Node(1);
        Node next = head;
        for (int i = 2; i <= n; i++) {
            Node tmp = new Node(i);
            next.next = tmp;
            next = next.next;
        }
        // 头尾串联
        next.next = head;
        return head;
    }

这种方法估计是最多人用的,时间复杂度为 O(n * m),空间复杂度是 O(n)。

还有更好的方法吗?答有,请往下看

方法三:递归

其实这道题还可以用递归来解决,递归是思路是每次我们删除了某一个士兵之后,我们就对这些士兵重新编号,然后我们的难点就是找出删除前和删除后士兵编号的映射关系

我们定义递归函数 f(n,m) 的返回结果是存活士兵的编号,显然当 n = 1 时,f(n, m) = 1。假如我们能够找出 f(n,m) 和 f(n-1,m) 之间的关系的话,我们就可以用递归的方式来解决了。我们假设人员数为 n, 报数到 m 的人就自杀。则刚开始的编号为

… 1 … m - 2

m - 1

m

m + 1

m + 2 … n …

进行了一次删除之后,删除了编号为 m 的节点。删除之后,就只剩下 n - 1 个节点了,删除前和删除之后的编号转换关系为:

删除前 --- 删除后

… --- …

m - 2 --- n - 2

m - 1 --- n - 1

m ---- 无(因为编号被删除了)

m + 1 --- 1(因为下次就从这里报数了)

m + 2 ---- 2

… ---- …

新的环中只有 n - 1 个节点。且删除前编号为 m + 1, m + 2, m + 3 的节点成了删除后编号为 1, 2, 3 的节点。

假设 old 为删除之前的节点编号, new 为删除了一个节点之后的编号,则 old 与 new 之间的关系为 old = (new + m - 1) % n + 1。

这样,我们就得出 f(n, m) 与 f(n - 1, m)之间的关系了,而 f(1, m) = 1.所以我们可以采用递归的方式来做。代码如下:

注:有些人可能会疑惑为什么不是 old = (new + m ) % n 呢?主要是因为编号是从 1 开始的,而不是从 0 开始的。如果 new + m == n的话,会导致最后的计算结果为 old = 0。所以 old = (new + m - 1) % n + 1.

int f(int n, int m){
    if(n == 1)   return n;
    return (f(n - 1, m) + m - 1) % n + 1;
}

我去,两行代码搞定,而且时间复杂度是 O(n),空间复杂度是O(1),牛逼!那如果你想跟别人说,我想一行代码解决约瑟夫问题呢?答是没问题的,如下:

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言入门到精通

7.6 指针数组和多重指针

8820
来自专栏C语言入门到精通

8.1 定义和使用结构体变量

9620
来自专栏C语言入门到精通

8.5 用typedef声明新类型名

简单的说,就是按定义变量的方式,把变量名换上新类型名,并且在最前面加“typedef”,就声明了新类型名代表原来的类型

10020
来自专栏C语言入门到精通

8.3 链表

链表中每一个元素称为结点,每一个结点都包含两部分:一是用户需要用的实际参数,二是下一个结点的地址。

7920
来自专栏C语言入门到精通

7.4 指向函数的指针

①定义指向函数的指针变量,并不意味着这个指针变量可以指向任何函数,它只能指向在定义时指定的类型的函数

13140
来自专栏C语言入门到精通

7.7 动态内存分配与指向它的指针变量

全局变量是分配在内存中的静态存储区的,非静态的局部变量是分配在内存中的动态存储区的,这个存储区称为“栈”。

11040
来自专栏C语言入门到精通

7.3 通过指针引用字符串

①用字符数组存放一个字符串,可以通过数组名和下标引用字符串中一个字符,也可以通过数组名和格式声明“%s”输出该字符串

8820
来自专栏C语言入门到精通

8.2 结构体数组和指针

指向结构体对象的指针变量既可以指向结构体变量,也可指向结构体数组中的元素。指针变量的基类型必须与结构体变量的类型相同

12220
来自专栏C语言入门到精通

8.4 共用体和枚举类型

①同一个内存段可以用来存放几种不同类型的成员,但在每一瞬间只能存放其中一个成员而不是几个

7420
来自专栏开发杂记

Java对于表达式中的自动类型提升

8620

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励