求解Josephus置换

Question

假设100个人站在一个1到100之间的圆圈里。一号有把剑。他杀死下一个人(即第2号)，并将剑交给下一个人(即第3号)。所有的人都这样做，直到只有一个人幸存下来。最后幸存的是哪个数字？

从1开始到100人有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

Answer 3

这让一个人活了下来，但我不确定问题的制约因素。

persons=rep("ALIVE",100)
for(i in 1:100) {
  if(i+1<101){
    if(persons[i+1]=="ALIVE"){
      persons[i]<-"DEAD"
    }
  }
  print(persons)
}