社区举办“杀戮游戏”，你能活下来吗？
“杀戮游戏”通告
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=2^x+l n=2x+l 其中x是n范围内2的最大次幂。
比如13 我们就可以表示为 13 = 2 3 + 5 13 = 2^3 + 5 13=23+5 也就是 13 = 8 + 5 13 = 8 + 5 13=8+5。此时如果x为4，则 2 4 2^4 24 > 13,所以x只能为3.
此时游戏人数是13，我们知道8是可以被2整除的，所以可以自然的想到，先干掉5个人，剩下的8个人开始的位置 i 就是最后存活下来的人。
如下图：
此时i的值为11，剩下了8个人，8== 2 3 2^3 23.
最后的存活者就是11，你可以用刚才的递归代码去验证。
n =13
k = 2
print("你的幸运号码是:{}".format(kill_game(n, k)+1))
输出：
你的幸运号码是:11
于是我们可以观察到这个规律这种情况下的
幸存号码= 2 ∗ l + 1 2*l+1 2∗l+1
本例中=> ( 2 * 5 +1)
最终的公式
存活下来的人可以用如下关系表示：
n = 2 x + l n=2^x + l n=2x+l
13 = 2 3 + 5 13=2^3+5 13=23+5 可得 x = 3 , l = 5 {x=3, l=5} x=3,l=5
存活下来的人(i)
i = 2 ∗ l + 1 i = 2*l+1 i=2∗l+1 可得 i = 11 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 制作的视频素材
