将军们，再来做道题 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

将军们，再来做道题 (转载)

将军们，再来做道题 (转载)# JobHunting - 待字闺中

I*g2017-05-20 07:05

1 楼

【以下文字转载自 Military 讨论区】
发信人: IFloating (Floating Freely), 信区: Military
标题: 将军们，再来做道题
发信站: BBS 未名空间站 (Sat May 20 14:02:51 2017, 美东)
监狱长把一群犯人排成圆圈，假设有1000人，id分别为 1，2，..., 1000.
监狱长决定从1号开始，每隔两个人就杀掉一个人，杀完了尸体拖走，由于是首位相连
，这样一直杀下去
，直到最后一个人留下来不杀。
所以杀的顺序是3号， 6号， 9号。。。。。。
请问最后谁活下来啊？

c*e2017-05-20 07:05

2 楼

604 号。今天刚好在学Python，就拿它来练手：
myList = list(range(1,1001))
def reBuild(list):
"""This function rebuilds a new list after removing the elements that
meet
the condition"""
newList=[]
if len(list) % 3 == 2:
newList.append(list[len(list) -2])
newList.append(list[len(list)-1])
elif len(list) % 3 == 1:
newList.append(list[len(list) -1])
for i in range(1, len(list) - len(list) % 3 + 1 ):
if i%3 != 0:
newList.append(list[i-1])
list = newList
if len(list) > 2:
reBuild(list)
else:
print ("last left ", list[1])

reBuild(myList)

o*r2017-05-20 07:05

3 楼

OK.
f[1] = 0;
f[i] = (f[i - 1] + m) % i (i > 1)
所以：
public class Solution {
public int lastStand(int n, int m) {
int ret = 0;
for (int i = 2; i <= n; i++) {
ret = (ret + m) % i;
}
return (ret + 1);
}

public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.lastStand(1000, 3));
}
}
复杂度O(n).