一行代码解决约瑟夫问题(我要开始装B了)

2022年05月10日 阅读数:5
这篇文章主要向大家介绍一行代码解决约瑟夫问题(我要开始装B了),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

1、前言

约瑟夫问题能够说是很是经典的一道题了,面试官常常问,我有一次就赶上了它,不对,应该是它赶上了我!下面我就用一行代码来解决这道约瑟夫问题,这种方法你学会了以后就能够在面试官面前装B了。面试

2、解题

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

其实咱们能够用递归来解决这道题,递归是思路是每次咱们删除了某一个士兵以后,咱们就对这些士兵从新编号,而后咱们的难点就是找出删除前和删除后士兵编号的映射关系。code

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


1
...
m - 2class

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。

注:有些人可能会疑惑为何不是 old = (new + m ) % n 呢?主要是由于编号是从 1 开始的,而不是从 0 开始的。若是 new + m == n的话,会致使最后的计算结果为 old = 0。因此 old = (new + m - 1) % n + 1.
这样,咱们就得出 f(n, m) 与 f(n - 1, m)之间的关系了,而 f(1, m) = 1.因此咱们能够采用递归的方式来作。代码以下:

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

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

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

我cao,之后面试官让你手写约瑟夫问题,你就扔这一行代码给它。

3、总结

不过那次笔试时,并无用递归的方法作,而是用链表的方式作,,,,,那时,不知道原来还能用一行代码搞定的,,,,欢迎各位大佬提供半行代码搞定的方法!