解决约瑟夫斯置换问题

Question

假设100个人以1到100的顺序站成一个圆圈.1号有一把剑.他杀死了下一个人(即第2号)并将剑交给下一个人(即第3号).所有人都这样做,直到只有1人幸存.最后一个幸存的是哪个号码？

有100人从1到100.

我试过了

persons <- c(1:100)
for (i in 1:100) {
  qu <- persons[seq_along(persons) %% 2 > 0]
  if (q2 == 2) {
    print(q2[2])
  }
}

还有这个

q=0
 while(q==0){ persons=persons[seq_along(persons) %% 2 > 0]
 if(length(persons)==2){ print(persons[2])
 q=1}}

但这给出了答案,因为65这是错误的,并没有解决目的.

如何做到这一点的任何解决方案？

Answer 1

在这个解决方案中,假设有剑的人是向量中的第一个人.那个人杀死了下一个人并移动到了行尾.

如果有一个人,那么那个人就是幸存者.

kill <- function(people = seq_len(100)) {
  if (length(people) == 1) return(people)

  kill(
    c(tail(people, -2), people[1]))
}


kill()
#> [1] 73

编辑:

对于大型n,请使用以下解决方案

kill_fast <- function(n) 2 * (n - 2 ^ (floor(log2(n)))) + 1

kill_fast(100)
#> [1] 73

kill_fast(100000)
#> [1] 68929

Answer 2

这是@Paul优雅的答案以非递归的方式重写,所以它可能更容易理解.

people <- 1:100
while (length(people) > 1) {
  people <- c(people[-(1:2)], people[1])
}
print(people)
# [1] 73