码农们来做题吧：约瑟夫杀人事件

[Rabboni]

说是有n个码农（这个n可能很大，可能有几个亿），排成1个圆圈。现在从1开始1，2报数，报到2的人就被杀了，现在问第k（1<=k<=n)个被杀的码农原来的排号是多少？别想用链表或者有序数组做循环，因为码农太多，会超时的。

[MrAnderson]

条件不够吧？杀了一个之后，然后是从谁，从几开始数呢？

说是有n个码农（这个n可能很大，可能有几个亿），排成1个圆圈。现在从1开始1，2报数，报到2的人就被杀了，现在问第k（1<=k<=n)个被杀的码农原来的排号是多少？别想用链表或者有序数组做循环，因为码农太多，会超时的。

[Rabboni]

只要活着就往下数。譬如5个人，12,3,4,5，第一轮2，4被杀，然后是1被杀，然后5被杀，3是最后温拿。

[Rabboni]

一个简单版问题是，任意给n个人，排成圆圈，隔一杀人（跟上面一样），谁是最后温拿？这个是算术题，不需要编程。

[MrAnderson]

温拿index = ceiling(log₂n)

说是有n个码农（这个n可能很大，可能有几个亿），排成1个圆圈。现在从1开始1，2报数，报到2的人就被杀了，现在问第k（1<=k<=n)个被杀的码农原来的排号是多少？别想用链表或者有序数组做循环，因为码农太多，会超时的。

[Rabboni]

温拿index = ceiling(log₂n)

这题是奥数题，没那么容易。

[MrAnderson]

这个只是最后温拿的序号。要算第k个，还得动脑筋。

这题是奥数题，没那么容易。

[Rabboni]

这个只是最后温拿的序号。要算第k个，还得动脑筋。

我说的就是最后温拿。算第k个，必须编程解决。

[MrAnderson]

你觉得哪里不对呢？

我说的就是最后温拿。算第k个，必须编程解决。

[TheMatrix2]

你觉得哪里不对呢？

你验证过了？

[MrAnderson]

没，就看了5个人的例子，至少是对的。上班偷闲呢。

你验证过了？

[Jack12345]

这是 数学题，不用 编程 也可以解决

[TheMatrix2]

没，就看了5个人的例子，至少是对的。上班偷闲呢。

我验证了n=8，最后剩下的是1。所以你的不对。:)

[MrAnderson]

好，下班了再来搞搞。

我验证了n=8，最后剩下的是1。所以你的不对。:)

[Rabboni]

其实这就是个排序问题，k=1的时候就是简单意义下的顺排，k=2的时候，。。。

[MrAnderson]

2(n-2^{floor(log₂n)})
应该是这样吧，序号从0开始

其实这就是个排序问题，k=1的时候就是简单意义下的顺排，k=2的时候，。。。

[Rabboni]

2(n-2^{floor(log₂n)})
应该是这样吧，序号从0开始

差不多吧，虽然序列是从1开始的，所以应该减一。

如果用编程的话非常简单，就是把二进制的最高位移到最低位，譬如23，二进制是10111，高位移到低位就变成了1111，所以结果是15。

[TheMatrix2]

2(n-2^{floor(log₂n)})
应该是这样吧，序号从0开始

n=8是对的。