分页： 1 / 1
码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 08:45
由 Rabboni
说是有n个码农（这个n可能很大，可能有几个亿），排成1个圆圈。现在从1开始1，2报数，报到2的人就被杀了，现在问第k（1<=k<=n)个被杀的码农原来的排号是多少？别想用链表或者有序数组做循环，因为码农太多，会超时的。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 09:39
由 MrAnderson
条件不够吧？杀了一个之后，然后是从谁，从几开始数呢？
Rabboni 写了： 2022年 9月 2日 08:45
说是有n个码农（这个n可能很大，可能有几个亿），排成1个圆圈。现在从1开始1，2报数，报到2的人就被杀了，现在问第k（1<=k<=n)个被杀的码农原来的排号是多少？别想用链表或者有序数组做循环，因为码农太多，会超时的。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 10:14
由 Rabboni
只要活着就往下数。譬如5个人，12,3,4,5，第一轮2，4被杀，然后是1被杀，然后5被杀，3是最后温拿。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 10:27
由 Rabboni
一个简单版问题是，任意给n个人，排成圆圈，隔一杀人（跟上面一样），谁是最后温拿？这个是算术题，不需要编程。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 10:41
由 MrAnderson
温拿index = ceiling(log
2n)
Rabboni 写了： 2022年 9月 2日 08:45
说是有n个码农（这个n可能很大，可能有几个亿），排成1个圆圈。现在从1开始1，2报数，报到2的人就被杀了，现在问第k（1<=k<=n)个被杀的码农原来的排号是多少？别想用链表或者有序数组做循环，因为码农太多，会超时的。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 11:27
由 Rabboni
MrAnderson 写了： 2022年 9月 2日 10:41
温拿index = ceiling(log
2n)
这题是奥数题，没那么容易。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 11:32
由 MrAnderson
这个只是最后温拿的序号。要算第k个，还得动脑筋。
Rabboni 写了： 2022年 9月 2日 11:27
这题是奥数题，没那么容易。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 11:35
由 Rabboni
MrAnderson 写了： 2022年 9月 2日 11:32
这个只是最后温拿的序号。要算第k个，还得动脑筋。
我说的就是最后温拿。算第k个，必须编程解决。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 11:39
由 MrAnderson
你觉得哪里不对呢？
Rabboni 写了： 2022年 9月 2日 11:35
我说的就是最后温拿。算第k个，必须编程解决。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 11:42
由 TheMatrix2
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 11:47
由 MrAnderson
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 11:47
由 Jack12345
这是 数学题，不用 编程 也可以解决
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 11:48
由 TheMatrix2
MrAnderson 写了： 2022年 9月 2日 11:47
没，就看了5个人的例子，至少是对的。上班偷闲呢。
我验证了n=8，最后剩下的是1。所以你的不对。:)
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 12:04
由 MrAnderson
好，下班了再来搞搞。
TheMatrix2 写了： 2022年 9月 2日 11:48
我验证了n=8，最后剩下的是1。所以你的不对。:)
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 12:40
由 Rabboni
其实这就是个排序问题，k=1的时候就是简单意义下的顺排，k=2的时候，。。。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 20:27
由 MrAnderson
2(n-2
floor(log2n))
应该是这样吧，序号从0开始
Rabboni 写了： 2022年 9月 2日 12:40
其实这就是个排序问题，k=1的时候就是简单意义下的顺排，k=2的时候，。。。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 21:21
由 Rabboni
MrAnderson 写了： 2022年 9月 2日 20:27
2(n-2
floor(log2n))
应该是这样吧，序号从0开始
差不多吧，虽然序列是从1开始的，所以应该减一。
如果用编程的话非常简单，就是把二进制的最高位移到最低位，譬如23，二进制是10111，高位移到低位就变成了1111，所以结果是15。
Re: 码农们来做题吧：约瑟夫杀人事件
发表于 ： 2022年 9月 2日 22:24
由 TheMatrix2
MrAnderson 写了： 2022年 9月 2日 20:27
2(n-2
floor(log2n))
应该是这样吧，序号从0开始
n=8是对的。