社区举办“杀戮游戏”，你是幸存的那个吗？

“杀戮游戏”通告

X社区要举办“杀戮游戏”，你会是幸存的那个人吗？
游戏规则如下：

所有人（本例子中12个人）排成一个圆圈，由第一个人开始，向下杀死相邻的人，直到剩下一个人，游戏结束。
获胜条件：你为了在这场“杀戮游戏”中存活下来，需要选择一个幸运号码，本例子中为9。

你的直觉是什么

大多数人应该和我一样，第一想法是构造一个链表数据结构，把所有人放到这个链表里面。

只要你懂得数据结构，这个解法非常直观。逻辑上就是每次杀死一个人，把代表这个人的节点删除，类似下面这样。

递归思想是一个好东西

也许你从另外一个思路入手，利用递归思想来解决这个问题。
递归树如下：

我们观察如下情况：
退出条件为
j(1,k) = 0 物理含义为：如果只有一个人参加游戏，则这个人必然存活，返回此时他的编号（假设由0开始编号）

递归之间的关系转移为：
j(n,k) =( j(n-1, k) + k ) % n

关系式中的 j(n-1, k) + k 物理意义：
 j(n-1, k) 为n-1规模存活下来的人，
 此时这个人的编号+k就是n规模存活下来的人的编号（这个编号有可能超出n），
 所以，考虑到所有的人都在一个圈上，需要对n取余，返回n范围以内的编号。

有了思路，代码真的不重要，但还是写一下，便于大家理解
代码如下：

def kill_game(n, k):
    if n == 1:
        return 0
    return (kill_game(n-1,k) + k ) % n
n = 12
k = 2
print("你的幸运号码是:{}".format(kill_game(n, k)+1))
#最后这里+1的，是因为最开始示例中使用的编号是从1开始。
#如果你的编号是从0开始，则可以忽略这个1

输出

你的幸运号码是:9

这种方式的好处就是实现起来，代码非常简单。

你还是被杀死了

社区举办这场“杀戮游戏”是参考历史上赫赫有名的约瑟夫环。

约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记来录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和源40名死硬的将士在附近的一个洞穴中避难。在那里，这些*者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这百个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为度洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。
网络上还有该问题的其它变种。

为了还原当时的历史条件，X社区决定不允许使用电脑编程这样的辅助设备，只能凭脑力。
用算法的语言描述就是你用O(N)的时间复杂度来解决这个问题，会被TLE(Time Limit Exceeded)。

更快的算法。

我们先来缩小规模，来观察这个问题，看有没有规律可以寻找。
规模缩小到8

第一个规律

如果n满足2的幂数倍，那最后存活下来的人一定是最开始的那个人：本例子中为1。

第二个规律

如果n不是2的整数倍，我们可以把n表示为$n=2^x+l$n=2x+l 其中x是n范围内2的最大次幂。
比如13 我们就可以表示为$13 = 2^3 + 5$13=23+5 也就是 $13 = 8 + 5$13=8+5。此时如果x为4，则$2^4$24 > 13,所以x只能为3.

此时游戏人数是13，我们知道8是可以被2整除的，所以可以自然的想到，先干掉5个人，剩下的8个人开始的位置 i 就是最后存活下来的人。
如下图：


此时i的值为11，剩下了8个人，8==$2^3$23.

最后的存活者就是11，你可以用刚才的递归代码去验证。

n =13
k = 2
print("你的幸运号码是:{}".format(kill_game(n, k)+1))

输出：

你的幸运号码是:11

于是我们可以观察到这个规律这种情况下的

幸存号码=$2*l+1$2∗l+1
本例中=> ( 2 * 5 +1)

最终的公式

存活下来的人可以用如下关系表示：
$n=2^x + l$n=2x+l
$13=2^3+5$13=23+5 可得 ${x=3, l=5}$x=3,l=5
存活下来的人(i)
$i = 2*l+1$i=2∗l+1 可得 $i=11$i=11

你现在能活下来吗？

现在你可以活下来了吗？
现在你已经被拉到了游戏现场，一共有41个人，已经开始选号码了！
你要选择多少？
把答案写在评论区吧！

满足你的强迫症

虽然这个问题，只要n不是特别夸张，对于已经熟练对65536求log的你应该已经可以心算了。
可我们毕竟是开发人员，总感觉不写段代码就哪里不对劲，为了满足这种强迫症，奉上代码.

import math
def kill_game(n):
    x = math.floor(math.log(n, 2))
    l = n - math.pow(2, x)
    luck_num = int(2*l+1)
    return luck_num
    
n = 13

print("你的幸运号码是:{}".format(kill_game(n, k)))

输出：

你的幸运号码是:11

我最喜欢的杀戮游戏

这场“杀戮游戏”是我非常喜欢在电话面试中用来考核候选者的一道面试题。
考察候选者对数据结构中的链表与递归思想进行考核，只要有了思路，编码实现一般都不会有什么大问题。
最后会和候选人探讨，有没有更快的实现方式？也就是本文中重点介绍的方法。当然候选人在面试情况下如果第一次接触这个问题，我并不会要求他给出正确的答案，只要他有正确的观察思路，我就会判他通关。

算法与真实的世界

在现实生活中，为什么很多事情，同样的人做会有不同的效果。
就在于你对这个问题的认识深度，能不能用算法，用模型去思考。每个人的时间都是有限的，如何用有限的时间去高效的解决问题，这是一个技术活！！
算法不仅仅是为了编程，他与我们的真实世界息息相关。
算法是能给你带来财富，节省生命的宝贵工具。

恭喜你在游戏中获胜了

---

---

我的其他文章
最火的瓜，得用动态规划来吃
A姓女友，B姓女友，渣男与最长公共子串（有视频）
就这一次干翻动态规划 - Longest Common Subsequence（有视频）

参考资料
感谢Numberphile 制作的视频素材