r - 解决约瑟夫斯排列

Question

Suppose if 100 people standing in a circle in an order 1 to 100. No. 1 has a sword. He kills the next person (i.e. No. 2) and gives the sword to the next (i.e. No. 3). All people do the same until only 1 survives. Which number survives at the last?

从 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 ，使用以下 solution

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

kill_fast(100)
#> [1] 73

kill_fast(100000)
#> [1] 68929